I was reading Introduction to the Design and Analysis of Algorithms book and found a neat puzzle.
Problem:
There are four people who want to cross a bridge; they all begin on the same side. You have 17 minutes to get them all across the other side. It is night, and they have one flashlight. A maximum of two people can cross the bridge at one time. Any party that crosses either 1 or 2 people must have a flashlight. The flashlight must be walked back and forth, cannot be thrown. Person 1 takes 1 minute to cross. Person 2 takes 2 minutes. Person 3 takes 5 min. Person 4 takes 10 min. A pair must walk together at the slower person’s pace. For example if person 1 walks with person 4 it takes 10 minutes for both of them to cross. If person 4 takes the flashlight back, a total of 20 minutes has elapsed and the mission failed.
Solution:
The most interesting part to me is the concept. You want to minimize the impact of the two slowest walkers, you try to avoid having either of them make more then one trip. You can mitigate the 5 min walker by sending him with the 10 min walker. The second optimization you try to do is decrease the “bringing-the-flashlight-back” time, so the fastest people should bring it back.
----------- symbolizes the bridge the bridge
0) ----------- 1 min 2 min 5 min 10 min
1) 1 min 2 min ----------- 5 min 10 min
Time: 2
2) 2 min ----------- 1 min 5 min 10 min
Time: 3
3) 2 min 5 min 10 min ----------- 1 min
Time: 13
4) 5 min 10 min ----------- 1 min 2 min
Time: 15
5) 5 min 10 min 1 min 2 min -----------
Time: 17