Rather than navel gaze for my 1000th 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
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.
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.