Enigmatic Code

Programming Enigma Puzzles

Enigma 152: The highways of Genoland

From New Scientist #1297, 18th March 1982 [link]

The five cities of Genoland are interconnected by four national highways ABC 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, AC and D or 2, 3, AB and C (not necessarily in the order given).

Which of the highways reach Geno?

[enigma152]

Advertisements

7 responses to “Enigma 152: The highways of Genoland

  1. Jim Randell 9 December 2013 at 9:11 am

    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).

    Enigma 152 - Solution

  2. Jim Olson 10 December 2013 at 1:33 am

    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          Z

    C 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.

    • Jim Randell 10 December 2013 at 9:44 am

      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).

      Enigma 152 - Solution 2

      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.

  3. arthurvause 13 December 2013 at 2:22 pm

    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

    • Jim Randell 13 December 2013 at 3:32 pm

      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.

      • arthurvause 14 December 2013 at 11:20 am

        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

        • Jim Randell 15 December 2013 at 9:26 pm

          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.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: