Critical Section

More Bridgework

Wednesday,  07/16/03  09:28 AM

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

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