|
On a UAL flight to Denver...
Okay, you remember the programmers crossing the bridge with the flashlight, right? The other day I revisited the bridge, and we considered a factor missing from the original problem: the "carry" of the flashlight beam. The original problem assumed a carry of zero, only the flashlight bearer and anyone traveling with him could see. If we postulate a carry of 100%, the entire bridge can be lit at once, and the problem becomes trivial:
Alex + Sam -> far side, with flashlight (2 minutes)
Francis + Pat -> far side, lit from far side (8 minutes, total = 10 minutes)
How about a carry of 50%? During the revisit I showed that the "carry 0" solution would be reduced from 15 minutes to 12½ (changes from carry 0 solution in red):
Alex + Sam -> far side (2 minutes); Alex only goes halfway
Alex -> near side (½ minute, total = 3 minutes)
Francis + Pat -> far side (8 minutes, total = 10½ minutes)
Sam -> middle of bridge (1 minute, total = 11½ minutes, this is the key!)
Sam + Alex -> far side (1 minute, total = 12½ minutes)
Is this optimal? Well, no. Mark Smith emailed the following solution:
Francis -> middle + Pat -> far side (4 minutes)
Sam -> far side, lit by Francis (2 minutes, total = 6 minutes)
Alex -> middle, lit by Francis (½ minute, total = 6½ minutes)
Francis + Alex -> far side from middle (4 minutes, total = 10½ minutes)
That looks pretty good! It is only ½ minute slower than the 100% carry solution. Is this optimal? No! Here's a slight improvement (changes in red):
Francis -> middle + Pat -> far side (4 minutes)
Alex -> far side, lit by Francis (1 minute, total = 5 minutes)
Sam -> middle, lit by Francis (1 minute, total = 6 minutes)
Francis + Sam -> far side from middle (4 minutes, total = 10 minutes)
Amazingly, this 50% carry solution is as good as the best 100% solution. Or is it? Maybe we have to check back on that 100% solution... It sure seemed simple, like it couldn't be improved upon. But check this out:
Francis -> middle + Pat -> far side, lit from near side (4 minutes)
Francis -> 3/4 + Sam -> far side, lit from near side (2 minutes, total = 6 minutes)
Francis -> 7/8, lit by Alex from near side (1 minute, total = 7 minutes)
Francis -> far side + Alex -> far side (1 minute, total = 8 minutes)
How about that! With 100% carry all the programmers can cross in the time it takes Francis to cross the bridge by himself, with only two on the bridge at any one time. That is optimal. (In fact, the carry need only be 7/8 for the same solution.)
Now let's go back to the 50% solution. How can we be sure 10 minutes is really optimal? We do what all nerds do, we write a program! In such a small solution space it is possible to stochastically examine all possible combinations of movement, seeking a minimum. I did this - modeling the flashlight beam is a little tricky - and sure enough the 10 minute solution for 50% carry is optimal. (Please click here if you want to see my code - and sure, you're welcome to do anything you want with it...)
Armed with this program, we can investigate other possibilities as well. For example, what about 25% carry? There's a non-obvious optimal solution, which I'll publish "soon"... I don't know about you, but I don't think I'd expect a technical interview candidate to be able to solve this!
[ Later: Here's the 25% solution... ]
So adding one little factor - the flashlight carry - made the problem way more complicated (and even more interesting). Want another factor? What if you're allowed to throw the flashlight? We'll consider the implications of flashlight "throw" on my next flight :)
| 
