# Enigmatic Code

Programming Enigma Puzzles

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:

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
'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

# calculate the paths between any two nodes
paths = list()
ps = list(nodes)
while ps:
p = ps.pop(0)
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:
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.')
```

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