October 12, 2004
crossing a bridge at night
Came across this puzzle:
Four people begin on the same side of a bridge. You must send them across to the other side in the fastest time possible. It is night. There is one flashlight. A maximum of two people can cross at a time. Any party who crosses, either one or two people, must have the flashlight to see. The flashlight must be walked back and forth, it cannot be thrown, etc. Each person walks at a different speed. A pair must walk together at the rate of the slower person’s pace, based on this information: Person 1 takes t1 = 1 minutes to cross, and the other persons take t2 = 2 minutes, t3 = 5 minutes, and t4 = 10 minutes to cross, respectively.
The obvious solution is to let the fastest guy cross with every other person and bring the flashlight back. But this wouldn't be a very good puzzle if you couldn't do better than that.
Here's a page that shows a general solution with n people and k subsets allowed to cross at the same time. It uses dynamic programming and has exponential running time.
This guy has collected a large set of emails and usenet articles about the puzzle.
But the coolest solution (I love this stuff :-) ) comes from here. Günter Rote presents in an elegant way how to map this problem to a subgraph in a graph problem (for the case of at most two people crossing). It has a greedy algorithm solution in polynomial time.
Posted by Uwe Hoffmann at October 12, 2004 12:02 AM