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:
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):
Is this optimal? Well, no. Mark Smith emailed the following solution:
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):
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:
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!
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 :) |
Home Greatest Hits |