puzzles

The Penniless Pilgrim

Brought to you by yet another aimless YouTube browse:

Dan Finkel's ‘Penniless Pilgrim’ puzzle in the TED Ed video above is, on the surface, quite simple:

You're a traveller, without a penny to your name. You enter a town with a simple grid-based street layout, like this:

Street layout

You enter the town at the north-west gate, and walk two blocks to the tourist information office. Your goal is to reach the temple at the far (south-east) corner of town. At the tourist information, you learn that the town has a curious system of tolls levied on all trips along the town's streets:

As you've already walked to tourist information, two blocks east of the gate, you currently owe 4 silver. You want to get to the temple, and you have no money. Can you get to the temple without ending up in debtors' prison?

One of the more direct routes, going due south and turning east at the southern wall, would cost 68 silver. A lot more than you have!

I must admit that I didn't spend a lot of time trying to figure out a solution before giving up and watching the rest of the video, which gives a nice and elegant path that end up costing you nothing.

Python to the rescue

After the fact, I couldn't help but wonder if there are other free routes to the temple. If so, how many? Are there any on which you make money?

Thankfully, this is fairly easy to brute force on a capable computer.

If we describe the town layout as a graph g using (way overpowered) networkx, edges being streets and nodes, labelled chessboard-style, being intersections, we mark the paths we've already taken as “trodden”.

AA = 'ABCDE'
BB = '12345'

def make_graph():
    g = nx.Graph()
    g.add_nodes_from(a + b for a in AA for b in BB)
    g.add_edges_from(((a+b1, a+b2)
                      for a in AA
                      for (b1, b2) in zip(BB[:-1], BB[1:])),
                     direction='EW')
    g.add_edges_from(((a1+b, a2+b)
                      for (a1, a2) in zip(AA[:-1], AA[1:])
                      for b in BB),
                     direction='NS')
    return g

g = make_graph()

g['A1']['A2']['trodden'] = True
g['A2']['A3']['trodden'] = True

and without too much effort we can figure out where we could go next from our current position, and what that would cost us. Add a bit of housekeeping to produce a new graph for every route with the trodden streets properly marked:

def possible_steps(g, pos, cost):
    for dest, props in g[pos].items():
        if not props.get('trodden'):
            if props['direction'] == 'NS':
                new_cost = cost * 2 if dest[0] > pos[0] else cost / 2
            else:
                new_cost = cost + 2 if dest[1] > pos[1] else cost - 2
            new_g = g.copy()
            new_g[pos][dest]['trodden'] = True
            yield new_g, dest, new_cost

Given the starting position, this will give us the two options of going east (cost: 6) or going south (cost: 8).

>>> list(possible_steps(g, 'A3', 4))
[(<networkx.classes.graph.Graph at 0x7f1d943382b0>, 'A4', 6),
 (<networkx.classes.graph.Graph at 0x7f1d98455438>, 'B3', 8)]

Now all we have to do is walk the graph, step by step, and see what happens!

I'll be doing this depth-first, as it were, as there's no easy way to discard partial routes that I can be bothered to think of.

def walk_on(g, steps, cost, dest=AA[-1]+BB[-1]):
    for next_g, next_step, next_cost in possible_steps(g, steps[-1], cost):
        new_steps = [*steps, next_step]
        if next_step == dest:
            yield (next_g, new_steps, next_cost)
        else:
            yield from walk_on(next_g, new_steps, next_cost)

If we get to the destination (AA[-1]+BB[-1] == 'E5'), we produce a resulting solution (graph, path and cost); if we're not there yet, we continue walking – and backtracking as needed.

If you let this solution generator iterate all the way through (which takes just under 10 minutes on my PC), it produces 58192 possible ways to get to the temple. Most are fairly expensive, but 6 are either free, or better!

The ‘canonical’ solution, shown in the video, is of course among the options found:

canonical good-pilgrim path

This is, also, the shortest route we can afford. However, it's not the best. The best route involves a minor detour down the pub at C2:

greedy-pilgrim path

The rest of the code is, of course, available in this notebook on GitHub.