Critical Section

Revisiting the Bridge of the Programmers

Friday,  07/11/03  09:11 AM

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

this date in:
About Me

Greatest Hits
Correlation vs. Causality
The Tyranny of Email
Unnatural Selection
On Blame
Try, or Try Not
Books and Wine
Emergent Properties
God and Beauty
Moving Mount Fuji
The Nest
Rock 'n Roll
IQ and Populations
Are You a Bright?
Adding Value
The Joy of Craftsmanship
The Emperor's New Code
Toy Story
The Return of the King
Religion vs IQ
In the Wet
solving bongard problems
visiting Titan
unintelligent design
the nuclear option
estimating in meatspace
second gear
On the Persistence of Bad Design...
Texas chili cookoff
almost famous design and stochastic debugging
may I take your order?
universal healthcare
triple double
New Yorker covers
Death Rider! (da da dum)
how did I get here (Mt.Whitney)?
the Law of Significance
Holiday Inn
Daniel Jacoby's photographs
the first bird
Gödel Escher Bach: Birthday Cantatatata
Father's Day (in pictures)
your cat for my car
Jobsnotes of note
world population map
no joy in Baker
vote smart
exact nonsense
introducing eyesFinder
to space
where are the desktop apps?
still the first bird
electoral fail
progress ratches
2020 explained