Enigmatic Code

Programming Enigma Puzzles

Tantalizer 427: Pub crawl

From New Scientist #978, 4th December 1975 [link]

Peter Pickle has drawn up this handy map of the twenty pubs in his town. On crawling nights he starts with a pint at The Swan and then moves off along the lines stopping at each pub he passes. (He may visit the same pub more than once).

He follows a formula on stepping out of The Swan: P, Q, R, Q, P, Q, P, S, S, P, S, P, Q, R, Q. In the formula P, Q, R and S stand for north, east, south and west (not necessarily in that order). The final Q brings him to The Bull (the red dot on the map) for the first and only time.

Can you mark the Swan on the map?

[tantalizer427]

One response to “Tantalizer 427: Pub crawl

  1. Jim Randell 12 June 2019 at 8:07 am

    This Python program considers all the possible assignments for the directions, and then traverses the path backwards to the starting point.

    It runs in 92ms.

    Run: [ @repl.it ]

    from enigma import subsets, join, printf
    
    # possible moves
    delta = dict(N=(0, 1), S=(0, -1), E=(1, 0), W=(-1, 0)) 
    
    # find where path p starts, if it finishes at (x, y)
    # return ((x, y), <visited nodes>)
    def solve(x, y, p, s=[]):
      # are we done?
      if not p:
        yield ((x, y), s)
      else:
        # retrace the last step
        (dx, dy) = delta[p[-1]]
        x -= dx
        y -= dy
        if not(x < 0 or x > 4 or y < 0 or y > 3):
          yield from solve(x, y, p[:-1], [(x, y)] + s)
    
    # peter's path
    path = "PQRQPQPSSPSPQRQ"
    
    # assign the directions
    for vs in subsets('NEWS', size=4, select='P'):
      # translate the path
      d = dict(zip('PQRS', vs))
      p = join(d[x] for x in path)
      # find a possible starting point
      for ((x, y), s) in solve(3, 1, p):
        # we only visit the end once
        if (3, 1) in s: continue
        # output solution
        printf("start = ({x}, {y}), path = {p}")
    

    Solution: The Swan is shown as the green dot on the diagram below:

    The path Peter takes is indicated with the blue arrows. P = East, Q = South, R = West, S = North.

    The pub immediately north of The Bull is visited twice.

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: