Enigmatic Code

Programming Enigma Puzzles

Enigma 479: Road island

From New Scientist #1630, 15th September 1988 [link]

On the faraway island of Roadio, the quaint villages with the curious one letter names A, B, C, …, S are joined by a network of roads as shown:

Enigma 479

The numbers indicate distances between villages in miles. I have written on all the distances I remember, however I also recall that, by road, no village is more than 20 miles from D and no village is more than 29 miles from P. What is the maximum distance between any two villages on the island?

[enigma479]

2 responses to “Enigma 479: Road island

  1. Jim Randell 17 December 2018 at 7:52 am

    The map is structured in such a way that there is only one sensible route between any two destinations, so this makes our task a little easier.

    This Python 3 program calculates the longest known path, and then determines maximum possible values for unknown segments. It then examines possible lengths for all unknown paths to find the maximum possible.

    It runs in 85ms.

    Run: [ @repl.it ]

    from enigma import tuples, irange, Accumulator, printf
    
    # the adjacency matrix for the graph
    adj = {
      'A': 'B',
      'B': 'ACD',
      'C': 'B',
      'D': 'BFH',
      'E': 'F',
      'F': 'DEG',
      'G': 'F',
      'H': 'DJM',
      'I': 'J',
      'J': 'HIK',
      'K': 'J',
      'L': 'M',
      'M': 'HLO',
      'N': 'O',
      'O': 'MNPR',
      'P': 'O',
      'Q': 'R',
      'R': 'OQS',
      'S': 'R',
    }
    
    # given distances
    distance = dict(AB=6, DH=4, FG=6, HJ=8, HM=3, JK=5, LM=10, MO=8, OP=5, QR=2)
    
    # nodes
    nodes = sorted(adj.keys())
    
    # calculate the paths between any two nodes
    paths = list()
    ps = list(nodes)
    while ps:
      p = ps.pop(0)
      for t in adj[p[-1]]:
        if t not in p:
          x = p + t
          ps.append(x)
          if p[0] < t:
            paths.append(x)
    
    key = lambda x, y: (x + y if x < y else y + x)
    
    # extract known and unknown values
    def path(p, d):
      (vs, us) = (list(), list())
      for (x, y) in tuples(p, 2):
        k = (x + y if x < y else y + x)
        x = d.get(k, None)
        (us if x is None else vs).append(k)
      return (tuple(sorted(vs)), tuple(sorted(us)))
    
    # recorded maximum possible distance for combinations of unknowns
    ms = dict()
    # no village is more than 20 miles from D, or 29 miles from P
    for (t, z) in [('D', 20), ('P', 29)]:
      for p in paths:
        if p[0] == t or p[-1] == t:
          (vs, us) = path(p, distance)
          m = z - sum(distance[k] for k in vs)
          printf("path = {p}: vs={vs} us={us}, z={z} m={m}")
          if us:
            if us not in ms or m < ms[us]:
              ms[us] = m
    
    # record maximum path
    r = Accumulator(fn=max)
    
    # find undetermined paths
    uns = list()
    for p in paths:
      (vs, us) = path(p, distance)
      t = sum(distance[k] for k in vs)
      if us:
        uns.append((p, vs, us, t))
      else:
        r.accumulate_data(t, p)
    
    printf("max known path {r.data} = {r.value}")
    
    # find possible distances for unknown segments
    def dists(us, t=0):
      # are we done?
      if not us:
        yield t
      else:
        # find the best fit unknowns
        k = max(ms.keys(), key=lambda k: (len(us.intersection(k)), -len(set(k).difference(us))))
        # choose a value for the unknowns
        for v in irange(len(us.intersection(k)), ms[k] - len(set(k).difference(us))):
          # solve for the remaining unknowns
          yield from dists(us.difference(k), t + v)
    
    # find maximum possible undetermined path
    for (p, vs, us, t) in uns:
      v = max(dists(set(us), t))
      r.accumulate_data(v, p)
      if v == r.value: printf("path {p} = {v}")
    
    printf("max path {r.data} = {r.value}")
    

    Solution: The maximum distance between any two villages is 29 miles.

    The path from K to P has a known length of 29 miles, and this is longest of any known path.

    While there are several paths of unknown length, none of them can exceed 29 miles. However any of the paths from (A, C, E, G, I, K) to (N, P, Q, S) can equal 29 miles.

    For instance if K to S was greater than 29, then O to S would have to be greater than 5. But then D to S would be greater than 20 miles, which is not possible.

  2. Brian Gladman 20 December 2018 at 1:33 pm
    # lists of the villages that are adjacent to each village
    adj = { 'A':'B', 'B':'ACD', 'C':'B', 'D':'BFH', 'E':'F', 'F':'DEG', 
            'G':'F', 'H':'DJM', 'I':'J', 'J':'HIK', 'K':'J', 'L':'M',
            'M':'HLO', 'N':'O', 'O':'MNPR', 'P':'O', 'Q':'R', 'R':'OQS', 
            'S':'R' }
    
    # the known lengths of the roads between villages
    mxy = dict(AB = 6, DH =  4, FG = 6, HJ = 8, JK = 5, 
               HM = 3, LM = 10, MO = 8, OP = 5, QR = 2 )
    
    # the set of villages served by only one road ('leaf' villages)
    end_nodes = tuple(''.join(k) for k, v in adj.items() if len(v) == 1)
    
    # find paths between village <x> and leaf villages, returning 
    # the combined length of known segments, the set of segments
    # of unknown length and the path
    def findpath(x, d, m=0, u=(), p=()):
      if p and adj[x] == p[-1]:
        yield m, frozenset(tuple(sorted(u))), ''.join(p + (x,))
      else:
        for n in adj[x]:
          if not p or n != p[-1]:
            seg = ''.join(sorted(x + n))
            mm, uu = (m + mxy[seg], u) if seg in mxy else (m, u + (seg,)) 
            yield from findpath(n, d, mm, uu, p + (x,))
    
    # find the maximum lengths of each combination of unknown
    # segments given that the maximum distances of any leaf 
    # village from villages D and P are 20 and 29 respectively
    v2l = dict()
    for s, l in zip('DP', (20, 29)):
      for m, u, _ in findpath(s, mxy):
        v2l[u] = min(l - m, v2l.get(u, l - m))
    
    # find the maximum length of any single segment that is still unknown 
    # from the maximum length of segment pairs that include this segment
    for u, m in list(v2l.items()):
      if len(u) > 1:
        for x in u:
          fx = frozenset((x,))
          v2l[fx] = min(m - 1, v2l.get(fx, m - 1))
    
    # arrange the lengths with those having more unknown segments first
    v2l = {k:v2l[k] for k in sorted(v2l.keys(), key=lambda x:-len(x))}
    
    mx, pths = 0, dict()
    # for each leaf village
    for s in end_nodes:
      # find the known miles and the unknown segments in
      # each path to other leaf villages 
      for m, u, p in findpath(s, mxy):
        # avoid covering the paths twice
        if p[-1] > s:
          op = '=='
          if u:
            op = '<='
            # add in the maximum lengths of segments of unknown length 
            for v, l in v2l.items():
              if v <= u:
                m += l
                u -= v
          print(f'path {p} {op} {m}')
          # and save the overall maximum distance
          if m > mx:
            mx = m
    
    print(f'The maximum distance between any two villages is {mx} miles.')
    

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: