Archive: July 11, 2003

<<< July 9, 2003

Home

July 13, 2003 >>>

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

 

Friday,  07/11/03  09:43 AM

Think there isn't a downside to affirmative action?  Aside from the impact on the "majority" students who are discriminated against, consider the affect on the "minority" students who are "helped"...  Stanford Law Professor Marcus Cole wrote a letter to Eugene Volokh about his experience: "...there is nothing that any American of African descent can do that can separate himself or herself from the unspoken accusation that he or she is the beneficiary of more than they deserve.  I am willing to bet that I am the only member of this list who feels compelled to put his standardized test scores and National Merit award on his CV." Marcus is black, and he was legitimately qualified, but he feels his qualifications come under question because of affirmative action.  Not good! RFID is taking over the world.  CNN reports the tiny transmitters will someday replace UPC bar codes.  They are certainly getting traction for business applications.  Someday every product you buy will have one, and you will be watched...  as you walk through a mall all your clothing choices, your personal electronics, everything, will be recorded. Ottmar Liebert likes his Line 6 amp.  The CEO of Line 6 is Mike Muench, my next-door neighbor.  What a small world! The RIAA is such a target, and this hits dead center: Sue all the world.  A terrific animated skewer from Bob Cesca and Camp Chaos.  I wonder if the RIAA will ever get tired of being "wrong" and fix themselves?  Nah. The market for illicit music CDs is now $4.6B annually, according to the BBC.  Seems like these are the real pirates, not consumers using file sharing networks. Yippee - SETI has received a five-year NASA grant.  I can't think of a better use of my tax dollars, actually. You know the phrase "older than dirt"?  (I like that phrase.)  Well here's some really old dirt: NASA announced the Hubble Space Telescope has found a planet 12.7B years old.  That's about three times older than Earth... Want to know if there's WiFi around?  Then you need this device from Kensington.  Isn't is amazing how WiFi has just absolutely become ubiquitous, in just a couple of years? Anyone try MyIE2?  Apparently this is a new web browser which uses the IE engine, but provides a better GUI, including pop-up blocking and tabbed windows.  I'll have to check it out...  [ via Robert McLaws ] Another thing to try: Oddpost.  This combination email client / RSS aggregator requires no download, it runs right in your web browser.  Very cool.  Here's an interesting interview with Ethan Diamond, Oddpost's creator, about how the thing works...

Return to the archive.