Some time ago, during a job interview, I was asked to solve a classic puzzle (Later, when at home, I discovered it being known as the “Four men on a rickety bridge” puzzle).
Here's is the interview version:
Four speleologists are left with one torch in a cave; the exit is a long, dark corridor, so tight that only two people at once can walk through it.
Not all speleologists can walk at the same speed; it takes them respectively 1, 2, 4 and 7 minutes to cover the distance to freedom.
The torch must be walked back and forth by one of the people since the corridor is really dangerous. It’s cold, the speleologists are tired and the torch battery’s is running out.
You are urged to find the fastest way to get everybody to safety.
As many do, I initially thought to pivot the fastest person and let him guide all his friends out by carrying the torch.
The total time would be then:
- 7 and 1 get out, total time: 7
- 1 goes back, total time: 1
- 4 and 1 go out, total time: 4
- 1 goes back, total time: 1
- 2 and 1 get out, total time: 2
- Total time: 6 + 1 + 4 + 1 +2 = 15 Right?
The trick is to have the slowest and the fastest people get out together:
- 2 and 1 get out, total time: 2
- 2 goes back, total time: 2
- 7 and 4 get out, total time: 7
- 1 goes back, total time: 1
- 2 and 1 get out, total time: 2
- Total time: 2 + 2 + 7 + 1 + 2 = 14
Non-geeks readers can stop here, we talk about NP-Completeness and euristic.
As a side note, this particular set might be solved using a greedy algorithm by grouping walking times and finding each time the minimum of the previous resulting subsets.For a subset of 2 people walking in the tunnel, given n speleologists {1..n} with walking times t(1) < t(2) < … < t(n)
Total time: t(1) + t(n) + Min(2*t(2), t(1) + t(n-1))
However such an approach might not converge for a generalized case, you need dynamic programming and backtracking to guarantee a solution that works with every number of people and different subsets.
No comments:
Post a Comment