1000th Post — The correct solution to a pesky interview riddle

Rather than navel gaze for my 1000^th post, the answer one should really give to the tired old interview chestnut about the guys who take 1,2,5 and 10 minutes to cross a bridge, no more than two at a time, needing a torch to light their way.

The answer is -- “It's a simple shortest path traversal for a graph, where the nodes are the 30 possible states (5 entities, 4 people and a torch, with the two torch-by-itself states not allowed). So use the A* algorithm to traverse the graph. You can even deduce the links in the graph algorithmically.”

Here's the Python code:

which outputs one of the two symmetrically equivalent shortest paths

>pythonw -u "torch.py"
    2+1 -->
<-- 1
    10+5 -->
<-- 2
    2+1 -->
Time taken = 17 minutes
>Exit code: 0

Fortunately, it seems that MSFT have long given up this interview habit -- just that the rest of the world may not yet have caught up.

Doing it programmatically also allows you to investigate how stable the solution is vis-à-vis the naïve strategy of using the 1-minute guy as escort, which is only 1 minute slower than the optimum.

Later

A little refactoring to put the times into one place (the new crossing_time function) and deduce everything from there. The use of the bits (which bits) is still a little dispersed, being there in display as well. Also changed the shortest possible distance heuristic h_score to be strictly monotonic (never overestimating the distance to the goal). Also play the path in the correct order.