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:

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:

• Your trip through town is taxed based on the route you take.
• You are not allowed to use the same street twice in a trip, but you are allowed to cross an intersection multiple times.
• Walking one block from west to east increases your tax bill by 2 silver.
• Walking one from east to west decreases your bill by 2.
• Walking one from north to south doubles you tax bill.
• Walking one from south to north halves your tax bill.

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'] = TrueCode language: Python (python)

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_costCode language: Python (python)

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)]Code language: Python (python)

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)Code language: Python (python)

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:

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:

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