Enigmatic Code

Programming Enigma Puzzles

Enigma 108: Longest journey

notableFrom New Scientist #1252, 7th May 1981 [link]

Enigma 108Here we have uniform square grid of roads, each 6 miles long, intersecting at 49 junctions. I want a route, starting at any junction and ending at any junction, and not going twice along any stretch of road, which meets two requirements: (1) It is as long as possible; (2) subject to that, it consists of as few “legs” as possible. In addition I should prefer a route which includes every junction, if that is possible without making the route shorter or leggier.

How many miles, and how few legs, in a route which best meets my requirements and my preferences?

[enigma108]

Advertisements

One response to “Enigma 108: Longest journey

  1. Jim Randell 16 July 2013 at 9:17 am

    I found this one quite challenging to solve. I would have liked to write a program that avoids some of the specific analysis for the 6×6 case, but it was taking long enough as it is. So if anyone has any ideas for speeding up a more generic solution then let me know.

    I started by considering the graph of an n×n grid. Let’s divide the vertices (junctions) into three kinds: (1) the 4 at the corners of the grid (corner vertices), (2) those along the sides of the grid (side vertices); (3) those interior to the grid (interior vertices).

    We note that there are no edge vertices or interior vertices if n = 1, and if n ≥ 2 then the side vertices (of which there are 4(n – 1)) all have odd degree (there are 3 roads that meet at them). The corner vertices always have degree 2 and the interior vertices always have degree 4.

    In the case of a 6×6 grid we have 20 side vertices.

    A path that traverses every edge of a graph exactly once is known as a Eulerian path [ http://en.wikipedia.org/wiki/Eulerian_path ] and is only possible in graphs that have two vertices of odd degree, and these are the start and finish vertices of the path. And every connected graph with two vertices of odd degree has a Eulerian path, and this will give us a maximum length journey on the grid. So we need to find the maximal subgraphs (i.e. with the minimum number of edges removed) of our original grid that have only two vertices of odd degree, and examine them to find paths with the fewest number of legs.

    Looking at the 5 side vertices along each side of the grid, we can reduce the number of odd degree vertices along the side from 5 to 1 by removing two of the edges (as shown in the diagram below).

    Enigma 108 - Sides

    Hence with the removal of 8 edges from the graph we can reduce the number of vertices of odd degree from 20 to 4. Now, if two of the remaining vertices of odd degree are positioned such that they are adjacent to a corner vertex, then we can remove two edges that form a path between them to turn them into vertices of even degree.

    Enigma 108 - Corners

    However the first of these (C1) leaves a disconnected vertex, so although it will be possible to create a Eulerian path on the grid it won’t include all the junctions (as requested in the problem statement). But we must still consider such grids, as they may give the fewest number of legs in the journey (a requirement which is more important than visiting all the junctions).

    So we consider the grids where the bottom-left corner is one of (C1) or (C2) and the top and right sides of the grid are some combination of (S1), (S2) and (S3). Giving us 2 × 3! = 12 subgraphs to consider.

    The following program examines the 12 subgraphs to find Eulerian paths with the minimal number of legs. It runs in 48m48s – although it finds the solution pretty much straight away – most of the time is spent completing the exhaustive search. With the pruning away of paths longer than the best we’ve found the run time varies depending on the order in which the subgraphs are considered.

    from collections import defaultdict
    from itertools import product, combinations, count
    from enigma import irange, Accumulator, printf
    
    # generate subgraphs of an NxN grid by removing edges in rs
    def subgraphs(N, rs):
    
      # make the grid
      (edges, degree) = (set(), defaultdict(int))
      for y in irange(0, N):
        for x in irange(0, N - 1):
          e = ((x, y), (x + 1, y))
          edges.add(e)
          for i in e: degree[i] += 1
        if y < N:
          for x in irange(0, N):
            e = ((x, y), (x, y + 1))
            edges.add(e)
            for i in e: degree[i] += 1      
    
      printf("grid has {n} edges", n=len(edges))
    
      # count the odd vertices
      odd = set(k for (k, v) in degree.items() if v % 2 == 1)
      printf("{n} vertices have odd degree", n=len(odd))
    
      def remove(e, edges, degree, odd):
        e2 = edges.difference([e])
        d2 = dict(degree)
        o2 = set(odd)
        for i in e:
          d2[i] -= 1
          if i in odd: o2.remove(i)
          else: o2.add(i)
        return (e2, d2, o2)
    
      # generate Eulerian subgraphs
      for s in rs:
        (e2, d2, o2) = (edges, degree, odd)
        for e in s[0] + s[1]:
          (e2, d2, o2) = remove(e, e2, d2, o2)
        yield (e2, d2, o2)
    
    # the 12 subgraphs we need for a 6x6 grid are generated by removing edges in r1 x r2
    
    r1 = (
      [((1, 0), (1, 1)), ((0, 1), (1, 1)), ((2, 0), (3, 0)), ((4, 0), (5, 0)), ((0, 2), (0, 3)), ((0, 4), (0, 5))], # C2
      [((0, 0), (1, 0)), ((0, 0), (0, 1)), ((2, 0), (3, 0)), ((4, 0), (5, 0)), ((0, 2), (0, 3)), ((0, 4), (0, 5))], # C1
    )
          
    r2 = (
      [((6, 1), (6, 2)), ((6, 4), (6, 5)), ((1, 6), (2, 6)), ((3, 6), (4, 6))], # S2 + S3
      [((6, 1), (6, 2)), ((6, 4), (6, 5)), ((1, 6), (2, 6)), ((4, 6), (5, 6))], # S2 + S2
      [((6, 1), (6, 2)), ((6, 3), (6, 4)), ((1, 6), (2, 6)), ((3, 6), (4, 6))], # S3 + S3
      [((6, 2), (6, 3)), ((6, 4), (6, 5)), ((1, 6), (2, 6)), ((3, 6), (4, 6))], # S1 + S3
      [((6, 2), (6, 3)), ((6, 4), (6, 5)), ((1, 6), (2, 6)), ((4, 6), (5, 6))], # S1 + S2
      [((6, 2), (6, 3)), ((6, 4), (6, 5)), ((2, 6), (3, 6)), ((4, 6), (5, 6))], # S1 + S1
    )
    
    N = 6
    r = Accumulator(fn=min)
    for (edges, degree, odd) in subgraphs(N, product(r1, r2)):
    
      M = len(edges)
      printf("subgraph has {M} edges, odd={odd}")
    
      r.accumulate(M + 1)
    
      # vertices and edges are encoded as integers
      def vertex(x, y):
        return x + (N + 1) * y
    
      (H, V) = (0, (N + 1) ** 2)
    
      def edge(x, y, d):
        return vertex(x, y) + d
    
      def bits(n):
        return bin(n).count('1')
    
      def i2v(x):
        return tuple(reversed(divmod(x, N + 1)))
    
      # for each vertex we create a list of possible legs:
      # v -> (v, edges, edge count, direction)
    
      # generate possible legs
      legs = defaultdict(list)
    
      # consider each point
      for (x, y) in degree.keys():
        p = vertex(x, y)
        # consider each direction
        # east...
        m = 0
        for x0 in irange(x, N - 1):
          if ((x0, y), (x0 + 1, y)) not in edges: break
          m |= (1 << edge(x0, y, H))
          legs[p].append((vertex(x0 + 1, y), m, bits(m), 'E'))
        # west...
        m = 0
        for x0 in irange(x - 1, 0, -1):
          if ((x0, y), (x0 + 1, y)) not in edges: break
          m |= (1 << edge(x0, y, H))
          legs[p].append((vertex(x0, y), m, bits(m), 'W'))
        # south...
        m = 0
        for y0 in irange(y, N - 1):
          if ((x, y0), (x, y0 + 1)) not in edges: break
          m |= (1 << edge(x, y0, V))
          legs[p].append((vertex(x, y0 + 1), m, bits(m), 'S'))
        # north...
        m = 0
        for y0 in irange(y - 1, 0, -1):
          if ((x, y0), (x, y0 + 1)) not in edges: break
          m |= (1 << edge(x, y0, V))
          legs[p].append((vertex(x, y0), m, bits(m), 'N'))
    
      # longest legs first
      for (p, v) in legs.items():
        legs[p] = sorted(v, key=lambda x: x[2], reverse=True)
        #print(i2v(p), list((x[3], i2v(x[0]), x[2]) for x in legs[p]))
    
      # next directions
      nd = { '*': 'NSEW', 'N': 'EW', 'S': 'EW', 'E': 'NS', 'W': 'NS' }
    
      # implement a depth first search (with pruning)
    
      # p - paths
      # ds - directions
      # es - visited edges
      # ec - count of visited edges
      # r - accumulator for results (by fewest legs)
      def solve(p, ds, es, ec, r):
        # count the legs
        n = len(p[0]) + len(p[1]) - (3 if (ds[0][-1] + ds[1][-1]) in ('NS', 'SN', 'EW', 'WE') else 2)
        if ec == M:
          if p[0][-1] == p[1][-1]:
            r.accumulate(n)
            if n == r.value: printf("legs={n} {p}", p=list(i2v(x) for x in p[0] + p[1][-2::-1]))
        elif n < r.value and not(ec + (r.value - n) * N < M):
          # add a leg from the current vertex
          for (v, e, b, d) in legs[p[0][-1]]:
            # in an allowable direction, and not reusing an edge
            if d in nd[ds[0][-1]] and not(es & e):
              solve([p[1], p[0] + [v]], [ds[1], ds[0] + d], es | e, ec + b, r)
    
      (s, f) = tuple(odd)
      printf("trying {s} <-> {f}")
      solve([[vertex(*s)], [vertex(*f)]], ['*', '*'], 0, 0, r)
    
    printf("SOLUTION: {M} edges, {n} legs", n=r.value)
    

    Solution: The longest possible journey is 74 miles. There are 22 legs in the journey. It is possible to visit every junction.

    Enigma 108 - Solution

    There are two more solutions that are equally long and have the same number of legs, but omit one junction (although I think they are more pleasing on the eye).

    Enigma 108 - Solutions

    The maximum path length on an n×n grid is given by the OEIS sequence A049486 [ http://oeis.org/A049486 ], although this doesn’t tell you what the minimum number of legs required is.

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: