Enigmatic Code
Programming Enigma Puzzles
Enigma 152: The highways of Genoland
Posted by on 9 December 2013
From New Scientist #1297, 18th March 1982 [link] [link]
The five cities of Genoland are interconnected by four national highways A, B, C and D. They are also independently linked by four provincial highways 1, 2, 3 and 4. Each highway connects two cities and Geno is the only city which can be directly reached from every other city. A round trip of the five cities involves the five highways 1, 3, 4, B and C or 1, 2, A, C and D or 2, 3, A, B and C (not necessarily in the order given).
Which of the highways reach Geno?
[enigma152]
Enigmatic Code 
I found this puzzle trickier than I was expecting, but I came up with this Python program that finds the solution in 36ms.
from itertools import permutations from enigma import irange, diff, printf # combine highways (or route fragments) into routes def combine(fs, rs): if not fs: return rs else: # link in the next fragment f = fs[0] # look for a route that can be extended by it for (i, r) in enumerate(rs): # can it be added at the front of r j = f.find(r[0]) if j != -1: rs = list(rs) rs[i] = f[j ^ 1] + r return combine(fs[1:], rs) # can it be added at the end of r j = f.find(r[-1]) if j != -1: rs = list(rs) rs[i] = r + f[j ^ 1] return combine(fs[1:], rs) else: # add a new route fragment return combine(fs[1:], rs + [f]) # suppose the cities are a, b, c, d, e # since 1, 3, 4, B, C (in some order) form a round trip, # let's assume C goes from a to b (and bc < ea to remove duplicate solutions) # and the remaining 4 highways (in some order) are bc, cd, de, ea for (bc, cd, de, ea) in permutations('134B'): if not(bc < ea): continue h1 = { 'C': 'ab', bc: 'bc', cd: 'cd', de: 'de', ea: 'ea' } # now: 2, 3, A, B, C also form a round trip, and we've already # allocated 3, B, C, so combine them: c = combine([h1['3'], h1['B'], h1['C']], []) # and determine possible routes for 2 and A if len(c) == 1: c0 = c[0] x = diff('abcde', c0)[0] hs = [(c0[-1] + x, x + c0[0])] elif len(c) == 2: (c0, c1) = c hs = [(c0[-1] + c1[0], c1[-1] + c0[0]), (c0[-1] + c1[-1], c1[0] + c0[0])] # now allocate the possibilities for p in hs: for (p1, p2) in permutations(p): h2 = dict(h1) h2['2'] = p1 h2['A'] = p2 # 1234 should link all 5 cities if len(set(h2['1'] + h2['2'] + h2['3'] + h2['4'])) < 5: continue # but: 1, 2, A, C, D also form a round trip, and we've already # allocated 1, 2, A and C, so combine them to find D c = combine([h2['1'], h2['2'], h2['A'], h2['C']], []) # there should be a single route if len(c) != 1: continue c0 = c[0] # and it should visit all five cities if diff('abcde', c0): continue # and D completes the round trip h2['D'] = c0[-1] + c0[0] # ABCD should link all 5 cities if len(set(h2['A'] + h2['B'] + h2['C'] + h2['D'])) < 5: continue # find the roads from each city for c in 'abcde': r = sorted(k for (k, v) in h2.items() if c in v) if len(r) == 4: print(h2) printf("Geno = {c}: roads = {r}", r=' '.join(r))Solution: The highways that go to Geno are A, B, D and 4.
The following diagram shows the two road systems. Blue for the national highways (A, B, C and D), and red for the provincial highways (1, 2, 3 and 4).
Another possible solution (?) is the four other cities in a rectangle and Geno is in the center of the rectangle the roads D 2,3 and 4 to Geno solves the requirements of the enigma.
W X G Y ZC between W and X ; A between X and Z; 1 Y and Z; B between W and Y.
D between W and G; 4 between X and G; 3 between Z and G; 2 between Y and G.
Sorry for my crude illustration but I am doing this from an I phone.
I’ve drawn out my original solution (left) and your solution (right) in the same style, so there are no overlapping roads, and it’s easier to see the round trips (you follow the perimeter of the square, except for one of the sides you travel to Geno at the centre of the square, and then back out to the perimeter again).
I think the subtlety that disallows this second solution is that the cities should be interconnected/linked by the two different highway systems (blue and red). In the diagram on the right the top right hand city is not on the red highway system, only the blue one.
This condition is ensured in my code by the line under the comment [[
# 1234 should link all 5 cities]] (and similarly for the blue roads: [[# ABCD should link all 5 cities]]). If these checks are removed then my program finds 4 solutions: B D 2 4; A B D 4; A D 3 4; D 2 3 4. This last one is the solution you found.As Jim has demonstrated, this is quite an intricate puzzle to program, so I have produced a “pencil and paper” solution, which is also quite intricate. As the solution involves numerous diagrams, I have placed it on a blog entry
Nice.
Although I realised only after I’d redrawn my diagram using the “crossed square” approach suggested by Jim Olsen, that there are, in fact, 4 ways of doing a round trip. You choose two adjacent “spokes” from Geno, and then complete the circuit by following the perimeter of the square the long way round. And you end up with 1, 2, 3, 4 and D also making a round trip that is not mentioned by the setter.
I think the puzzle could have been worded a little more carefully, because it seems to me that saying “a round trip of the five cities involves the five highways …”, implies that there isn’t a way to make a round trip that doesn’t use one of the sets mentioned. But I don’t think it’s possible make a solution that only has three possible round trips on it.
I think this makes it a bit trickier to initially place highway C on the diagram. Although the fact it is in 3 circuits means it must be in the perimeter of the square. Likewise 4 and D only appear in 1 of the given circuits, so they must appear on the “spokes” going to Geno.
It turns out that the solution can be deduced much more easily if the fourth round trip is included. Geno is reached by all the highways that are involved in exactly two round trips, as illustrated in this follow-up blog entry
Yes, it’s much easier if you’re given the highways in all four circuits. The four “spokes” (that lead to Geno) are all included on exactly 2 of the circuits, and the four highways that make up the perimeter of the square will appear in exactly 3 of the circuits.