**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]

### Like this:

Like Loading...

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