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

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