Thursday, October 02, 2008

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

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

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.

No comments :