# Enigmatic Code

Programming Enigma Puzzles

## Enigma 56: Sore spots

From New Scientist #1199, 20th March 1980 [link]

Sam Sorebottom has just spent his weekend cycling around part of the Fens. He arrived at one of the 16 towns by rail and thereafter cycled madly from town to town, until worn out.

The towns have names starting, conveniently, with the letters A to P and he visited each exactly twice (counting his train arrival at A as his first visit to A). His final destination was M and he used only the roads you see on the map.

He told a friend today that he did the towns in this precise order:

A J N H K G B M I E P F C L D O C G N H O K D L P E I F B J A M.

“That cannot be quite right,” said the friend, after a little thought. “No,” Sam replied, having reconsidered, “I see that I have carelessly transposed two successive towns at exactly one point in the order.”

Even without knowing which town is where on the map, can you name the transposed towns?

[enigma56]

### 2 responses to “Enigma 56: Sore spots”

1. Jim Randell 11 February 2013 at 11:21 am

Note that the map is topologically identical to a 3×3 grid with the towns at the corners of the squares. Which means in any single journey an individual town can only appear in either all odd positions or all even positions in the journey. This gives us the quick way to find the transposed towns in the journey itinerary.

This Python program then goes on to fix up the journey itinerary, and compute the map of the towns. It runs in 46ms.

```from enigma import printf

# original route
s = 'AJNHKGBMIEPFCLDOCGNHOKDLPEIFBJAM'

even = s[::2]
odd = s[1::2]

t = set(even).intersection(odd)
assert len(t) == 2 # there is exactly one transposition of letters
(a, b) = sorted(t)
printf("transposed: {a} / {b}")

# fix up the route
(ab, ba) = (a + b, b + a)
s = s.replace(ab, ba) if ab in s else s.replace(ba, ab)
printf("corrected route: {s}")

# recursively apply the route to the grid
# g - grid we are working on
# p - current position in the grid
# s - route we are working with
# i - current position in the route
# qs - possible next positions on grid
def solve(g, p, s, i, qs=None):
# are we done?
if i == len(s):
for i in range(0, 16, 4):
print(''.join(g[i:i + 4]))
return
# possible next steps
if qs == None:
qs = set()
(y, x) = divmod(p, 4)
if x > 0: qs.add(p - 1)
if x < 3: qs.add(p + 1)
if y > 0: qs.add(p - 4)
if y < 3: qs.add(p + 4)
# is the next letter placed?
if s[i] in g:
q = g.index(s[i])
# is it in an adjacent position?
if q not in qs: return
# move to it
solve(g, q, s, i + 1)
else:
# try to place it
for q in qs:
if g[q]: continue
g[q] = s[i]
solve(g, q, s, i + 1)
g[q] = None

# make a 4x4 grid
g = [None] * 16

# possible initial starting and next positions
for (p, qs) in ((0, [1]), (1, None), (5, [1, 9])):
g[p] = s[0]
solve(g, p, s, 1, qs)
```

Solution: The transposed towns are K and O.

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