Enigmatic Code

Programming Enigma Puzzles

Enigma 56: Sore spots

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

Enigma 56Sam 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]

Advertisements

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.

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: