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...

Four programmers must cross a rickety bridge at night. The bridge can only hold two of them at a time, and they have one flashlight between them. The four programmers cross at different speeds, Alex only requires one minute, Sam requires two, Pat requires four, and Francis requires eight. What is the shortest time in which they can all cross?

I received an interesting email from Ben Webman (now that is a great name for a blogger, eh?):

"If the bridge is very short and we have a good flashlight -- nobody has to carry the flashlight back over!  So -- there is a "different" and faster way -- (maybe not better)."

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):

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)

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?

[ Later: the bridge has been revisited again...  and again... ]