Four programmers

Question: 

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 requires one minute, Sam requires two, Pat requires four, and Francis requires eight. What is the shortest time in which they can all cross?

.

.

C

A

P

T

A

I

N

I

N

T

E

R

V

I

E

W

.

.

Solution: The most obvious solution that occurs to most people after working on this problem for a bit is as follows:

Alex  +  Sam → far side (2 minutes)

Alex → near side (1 minute, total  3 minutes)

Alex  +  Pat → far side (4 minutes, total  7 minutes)

Alex → near side (1 minute, total  8 minutes)

Alex  +  Francis → far side (8 minutes, total  16 minutes)

This is a good solution because it uses Alex to ferry the flashlight back after each trip. Alex is the fastest, so this seems to make sense. Sam, Pat, and Francis each need to cross the bridge, so that’s 2 + 4 + 8 = 14 minutes, and Alex has to come back twice, so that’s 2 more minutes for a total of 16. How could that not be optimal?

Ole Eichorn, who has administered this puzzle to dozens of job candidates, analyzes the solution set at length on his blog The Critical Connection (http://w-uh.com/):

After giving a suboptimal answer to this problem, many people refuse to believe it is wrong. I love this problem for exactly this reason. If candidates work it out by themselves, terrific, they get full credit, but if they get the good-but-wrong answer and accept that it is wrong, and continue digging, I give them full credit for that, too. (There is a bit of an “aha!” involved.) Sometimes people don’t believe there’s a better answer, and start to argue with you; that’s a bad sign; it is good to have confidence, but not good to be closed to new ideas.

So, how could this be done any better? Let’s come back to Eichorn:

The optimal answer to this question is actually 15. (Yep, it is, I’ll tell you how in a moment.) Now if you were to ask: “How can the four programmers cross in 15 minutes,” you may very well stump candidates. This isn’t what you want. Ideally you want candidates to chew on the problem, work out a solution, and then defend it. This gives you a lot more insight into how candidates think, and they have a sense of accomplishment. Otherwise if they fail to get 15, they’ll feel bad, and you’ll feel like you tricked them.

The key insight—the thing which is a bit of an “aha!”—is to have Francis and Pat cross at the same time. They’re the two slowest, so essentially this gives you the second-slowest crossing for free. It isn’t obvious how to make this happen, though; here’s the most likely first attempt:

Francis + Pat → far side (8 minutes)

Pat → near side (4 minutes, total 12 minutes, already some-thing seems wrong)

Pat + Alex → far side (4 minutes, total 16 minutes, you know this won’t work . . . )

Pat had to come back with the flashlight. This made his 4 minutes far from free, because not only does he have to come back, he has to cross again. Not good. So what if Pat didn’t have to come back? What if a faster programmer were already on the far side and could bring the flashlight back instead? Aha!

Alex  +  Sam → far side (2 minutes)

Alex → near side (1 minute, total  3 minutes)

Francis +   Pat → far side (8 minutes, total   11 minutes)

Sam → near side (2 minutes, total 13 minutes, this is the key!)

Sam  +  Alex → far side (2 minutes, total  15 minutes)

Excellent, eh? And yet it is quite logical. An exhaustive analysis of all the possibilities in a relatively small solution space would find this easily.

Extra credit: Challenging another assumption yields another “aha!” moment that cuts minutes off the solution thought optimum. The insight—attributed to Ben Webman—is why assume that the illumination provided by the flashlight (the flashlight “carry”) is so poor that it can serve only the person holding it? Why not assume that the flashlight can illuminate part or even all of the bridge. In that case, it might not have to be carried at all. In Webman’s response, the flash-light’s beam carries all the way, and there’s no need to go back with it. For example, let’s assume the flashlight’s beam carries halfway. Now what’s the best solution? Let’s first see what this does to the original solution:

Alex  +  Sam → far side (2 minutes); Alex only goes halfway Alex → near side (1⁄2 minute, total 3 minutes)

Francis  +  Pat → far side (8 minutes, total   101⁄2 minutes)

Sam → middle of bridge (1 minute, total 111⁄2 minutes, this is the key!)

Sam  +  Alex → far side (1 minute, total   121⁄2 minutes)

So the total time is reduced from 15 minutes to 121⁄2 minutes.

Ole Eichorn comments:

How about that! With 100 percent 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.) “How can we be sure 10 minutes is really optimal? We do what all nerds do, we write a pro-gram! 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 percent carry is optimal.

[To see Eichorn’s code, go to http://w-uh.com/images/ progbridge.cpp.txt.]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

Powered by WordPress.com.

Up ↑

%d bloggers like this: