Most puzzles are fun in their own right. Some puzzles are so fun that they have the added benefit that they are likely to come up in unexpected places, like maybe in a job interview. I was recently reading a paper by Günter Rote entitled “Crossing the Bridge at Night” where Rote analyzes such a puzzle. Upon finishing the paper, I decided to write a script so that users could see the general form of this puzzle.
The problem can be stated as follows: There is a set of people, lets make the set finite by saying that there are exactly n people, who wish to cross a bridge at night. There are a few restrictions that make crossing this bridge somewhat complicated.
- Each person has a travel time across the bridge.
- No more than two people can cross the bridge at one time.
- If two people are on the bridge together, they must travel at the pace of the slower person.
- There is only one flashlight and no party (of one or two people) can travel across the bridge without the flashlight.
- The flashlight cannot be thrown across the bridge, and nobody can go to the store to purchase another flashlight
The image above shows the optimal solution when the 4 people have travel times of 1, 2, 5, and 10. The script I have written allows users to work with different numbers of people with random travel times. Give it a try and see if you can spot the patterns in the solution.