Remember the bridge of the four programmers? An interesting technical interview problem, with an unexpected answer. It turns out there is more complexity in this problem than I had thought. Yay!
Here's the problem again, to refresh your memory...
I received an interesting email from Ben Webman (now that is a great name for a blogger, eh?):
I like it! There is a new factor to consider, the "carry" of the flashlight beam.
In the original solution, there was an assumption that the beam did not carry at all, and hence each programmer had to go all the way to the other side with the flashlight. In Ben's version, the flashlight's beam carries all the way, and there's no need to go back with it. Intermediate versions are possible, for additional complexity.
For example, let's assume the flashlight beam carries halfway. Now what's the best solution?
Let's first see what this does to our original solution. Here it is (changes in red):
So the total time is reduced from 15 minutes to 12½ minutes. That's pretty good. However, I'm not sure this is really optimal. I'm troubled by the fact that the Francis + Pat trip is not shortened at all by consideration of the beam carry, because this is the longest single component of the whole operation. Perhaps there is a way to optimize further? Anyone have any good ideas?