Enigmatic Code

Programming Enigma Puzzles

Enigma 203: Round walk

From New Scientist #1349, 17th March 1983 [link]

Enigma 203

The plan shows the layout of paths in our local park. At each of the six junctions of paths there is a statue. The shortest route (on the paths) from Disraeli to Victoria is bound to take you past George V only. From Disraeli it is the same distance to Eros as it is to the Unknown Warrior.

I usually choose a walk which starts and finishes at Churchill and passes each of the other statues only once, but I choose it so that the is no other shorter “round walk”.

Last week one stretch of path was closed for repair. This meant that the shortest distance (on paths) from George V to Disraeli was over twice what it was previously. Also, I could not go on any of my usual “round walks” so I chose a new shortest route in the circumstances. As usual it visited each statue just once except for starting and finishing at Churchill. Also I chose the walk and the direction which ensured I passed Eros as soon as possible.

What was the order in which I passed the statues? (C – – – – – C)

[enigma203]

Advertisements

6 responses to “Enigma 203: Round walk

  1. Jim Randell 1 July 2014 at 7:11 am

    This Python 3 program runs in 103ms.

    from itertools import permutations
    from math import cos, pi
    from enigma import irange, first, printf
    
    d1 = 6 * (1 - cos(1)) / pi
    d2 = 6 * cos(1) / pi
    
    # graph of the diagram: source -> dest -> dist
    graph = {
      0: { 1: d2, 2: 2, 3: 2 },
      1: { 0: d2, 2: 1, 3: 1, 4: d1 },
      2: { 0: 2, 1: 1, 4: 1, 5: 2 },
      3: { 0: 2, 1: 1, 4: 1, 5: 2 },
      4: { 1: d1, 2: 1, 3: 1, 5: d2 },
      5: { 2: 2, 3: 2, 4: d2 },
    }
    
    # paths from s to t, visiting vs
    # g - graph
    # s - source
    # t - target
    # vs - nodes to visit
    # ns - current path (list of nodes)
    # d - current distance
    def paths(g, s, t, vs, ns, d):
      # are we done?
      if s == t and vs.issubset(ns):
        yield (ns, d)
      else:
        # consider possible paths
        for (k, v) in g[s].items():
          if k not in ns:
            yield from paths(g, k, t, vs, ns + [k], d + v)
    
    # shortest routes from s to t, visiting vs
    # return (<distance>, <paths>)
    def shortest(g, s, t, vs=set()):
      (m, ss) = (1000, None)
      for (ns, d) in paths(g, s, t, vs, [], 0):
        if d < m:
          (m, ss) = (d, [])
        if d == m:
          ss.append([s] + ns)
      return (m, ss)
    
    # return just the distance
    def shortest_distance(g, s, t, vs=set()):
      (m, _) = shortest(g, s, t, vs)
      return m
    
    # return just the paths
    def shortest_paths(g, s, t, vs=set()):
      (_, ss) = shortest(g, s, t, vs)
      return ss
    
    # find shortest circuits on the original graph
    cs1 = shortest_paths(graph, 0, 0, set(graph.keys()))
    
    # assign the statues to the nodes
    for statue in permutations('CDEGUV'):
      (C, D, E, G, U, V) = (statue.index(x) for x in 'CDEGUV')
    
      # remove symmetrical solutions
      if not(statue[0] < statue[5] and statue[2] < statue[3]): continue
    
      # shortest route from D to V must only pass G
      if any(not(len(ns) == 3 and G in ns) for ns in shortest_paths(graph, D, V)): continue
    
      # from D it is the same distance to E and U
      if shortest_distance(graph, D, E) != shortest_distance(graph, D, U): continue
    
      # original G/D distance
      gd = graph[G][D]
    
      # make a new graph with the path from G/D removed
      graph2 = graph.copy()
      graph2[D] = graph[D].copy()
      del graph2[D][G]
      graph2[G] = graph[G].copy()
      del graph2[G][D]
    
      # new G/D distance, must be more than twice the old one
      if not(shortest_distance(graph2, G, D) > gd * 2): continue
    
      # find shortest circuits on the new graph
      cs2 = shortest_paths(graph2, 0, 0, set(graph2.keys()))
    
      # none of these can be the same as the original circuits
      if any(c in cs2 for c in cs1): continue
    
      # transform the circuits to start/finish at C (instead of 0)
      cs3 = list()
      for cs in cs2:
        c = cs.index(C)
        cs3.append(list(cs[(c + i) % 6] for i in irange(0, 6)))
    
      # find circuits with the earliest E
      i = min(cs.index(E) for cs in cs3)
      for cs in cs3:
        if cs.index(E) != i: continue
        path = list(statue[x] for x in cs)
        printf("path={path} [statue={statue}]", path=' '.join(path), statue=' '.join(statue))
    

    Solution: The order in which the statues were passed was: Churchill, Eros, Disraeli, the Unknown Warrior, George V, Victoria, and back to Churchill (C E D U G V C).

    There must be a path between G and D as the the shortest route from D to V takes you only past G, hence must be D → G → V. So the only way that removing a path would increase the distance between G and D is if the path removed is between G and D.

    I assumed the circles intersected such that the longer curved paths all have length 2 and the shorter curved paths have length 1. Which means the longer straight paths have length of slightly more than 1 (≈ 1.03) and the shorter straight path has length less than 1 (≈ 0.88). If you don’t trust Python’s floats to be accurate enough you can import pi and cos from SymPy to make all the distances symbolic. It runs a bit slower, but comes up with the same answer.

    • Hugh Casement 14 August 2015 at 9:00 am

      Is the diagram to scale, or does each circle pass through the centre of the other?
      Which statue is at which node?

      • Jim Randell 14 August 2015 at 12:24 pm

        I don’t think the diagram needs to be exactly to scale.

        Revisiting my code it didn’t make sense to me, so I’ve changed it to suppose that the circles have a circumference of 6 units. Then the curved paths are all of length 1 (in the middle) or 2 (around the outside), and the middle straight path is a bit less than 1 and the other two straight paths are a bit more than 1 (d1 and d2 in the program).

        If you change the program such that d1 and d2 are both exactly 1 then the program still produces the same output, suggesting that if the diagram was drawn out on a equilateral triangular grid with all paths of length 1 unit or 2 units then the answer is the same.

        The crux of the puzzle is working out which statues are at which nodes, in order to satisfy the conditions in the text. But I’ll add a diagram to my solution that shows the arrangement.

        • Jim Randell 14 August 2015 at 2:10 pm

          Here’s a diagram that shows the layout of the statues found by my program:

          Enigma 203 - Solution

          • Hugh Casement 14 August 2015 at 6:37 pm

            Thanks Jim: one picture is worth a thousand words.
            I’d been wondering whether the clue to it was to have all the straight segments the same length, or the central one the same length as the adjacent curved segments.  Evidently not.

            I’m gradually catching up with these older puzzles.  I’d collected many of them even before you started this web site, but was often not able to see how the published solution was arrived at.  Your insights and explanations are much appreciated.

  2. Brian Gladman 3 July 2014 at 3:53 pm
    from math import pi, cos
    from operator import itemgetter
    from itertools import combinations, product
    
    statues = ('Disraeli', 'George V', 'Victoria', 'Eros', 
               'Unknown Warrior', 'Churchill')
    
    # label points from left to right and then top top bottom and assume
    # that the circles have unit radii with the smallest arc of a circle
    # between the inner points as beta radians
    beta, tc_beta = pi / 3, 2 * cos(pi / 3)
    t, u, v, w = tc_beta, 2 - tc_beta, beta, pi - beta
    
    # map the network connectivity: node -> node -> distance
    net = { 0: { 1: t, 2: w, 3: w },
            1: { 0: t, 2: v, 3: v, 4: u },
            2: { 0: w, 1: v, 4: v, 5: w },
            3: { 0: w, 1: v, 4: v, 5: w },
            4: { 1: u, 2: v, 3: v, 5: t },
            5: { 2: w, 3: w, 4: t } }
    
    # find the set of adjacent nodes
    adj = set()
    for m, d in net.items():
      for n in d:
        adj.add(tuple(sorted((m, n))))
    
    # return the paths between 'start' and 'end' with
    # the network connectivity given by'net'
    def paths(start, end, net, nodes=(), lnth=0):
      if start == end:
        yield nodes + (end,), lnth
      else:
        nodes += (start,)
        for node, ln in  net[start].items():
          if node not in nodes:
            yield from paths(node, end, net, nodes, lnth + ln)
    
    # return the minimum length paths between 'start' and 'end' 
    # with the network connectivity given by'net'
    def min_paths(start, end, net, nodes=(), lnth=0):
      pths = sorted(paths(start, end, net), key=itemgetter(1))
      for p, l in pths:
        if l != pths[0][1]:
          break
        yield p, l
    
    # return the circuits for 'start' with the network 
    # connectivity given by 'net'
    def circuits(start, net, nodes=(), lnth=0):
      for node, ln in net[start].items():
        for p, l in paths(node, start, net, (), ln):
          if len(p) == 6:
            yield (start,) + p, l
    
    # return the minimum length circuits for 'start' with the
    # network connectivity given by 'net'
    def min_circuits(start, net, nodes=(), lnth=0):
      pths = sorted(circuits(start, net), key=itemgetter(1))
      for p, l in pths:
        if l != pths[0][1]:
          break
        yield p, l
    
    # find all paths of length three in the network (for D, G, V)
    dgv = []
    for start in range(6):
      for end in range(6):
        if start != end:
          for p, l in paths(start, end, net):
            # avoid duplicates resulting from symmetry
            if len(p) == 3 and p[0] < p[2] and p[1] < 3:
              dgv += [(p, l)]
    # sort on path length and only keep those of minimum length
    dgv = sorted(dgv, key=itemgetter(1))
    dgv = tuple(x for x, l in dgv if l == dgv[0][1])
    
    maps = set()
    # map Disraeli, George V and Victoria onto these paths
    for D, G, V in dgv:
      # now map Eros and the Unknown Warrior provided that
      # they are the same distance from Disraeli
      s = set(range(6)).difference((D, G, V))
      for E, U in combinations(s, 2):
        for p_d2e, l_d2e in min_paths(D, E, net):
          for p_d2u, l_d2u in min_paths(D, U, net):
            if l_d2e == l_d2u:
              C, = s.difference((E, U))
              maps.add((D, G, V, E, U, C))
    
    # compile a list of network connectivities when
    # one of the paths between the nodes is removed
    l_con2 = []
    for ip in adj:
      u = dict()
      for m, d in net.items():
        t = dict()
        for n, l in d.items():
          if (m, n) != ip and (n, m) != ip:
            t[n] = l
        u[m] = t
      l_con2 += [u]
    
    # the minimum length circuits for C before path removal
    p_c2c = list(x for x, l in min_circuits(C, net))
    # the minimum distance from G to D before path removal
    l_g2d = min(l for x, l in min_paths(G, D, net))
    
    # for each set of statue positions with each removed path
    for m, con2 in product(maps, l_con2):
      D, G, V, E, U, C = m
      # find the minimum length paths from G to D in the new network
      _, l = min(min_paths(G, D, con2), key=itemgetter(1))
      # if this length is now more than double what it was
      if l > 2 * l_g2d:
        # find the minimum length circuits for Churchill in the new
        # network that are different from what they were (sort them
        # in order of the position of Eros on the path)
        p = min((x for x, l in min_circuits(C, con2) 
                  if x not in p_c2c), key=lambda x:x.index(E))
        # output the statue order on this circuit
        print('Statues passed in the order:', tuple(statues[(D, G, V, E, U, C).index(x)] for x in p))
        # show the statues at nodes 1 .. 6
        p = [' '] * 6    
        for i, l in enumerate(m):
          p[l] = statues[i]
        print('Statues at nodes 1 .. 6 are:', tuple(p))
    

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: