Albert, Bob, Carl, and Doug are hiking together and come to a bridge which they need to cross. The bridge holds at most 2 people at once. It is night, so anyone crossing needs to have or be near a flashlight, but the group has only 1 working flashlight. The 4 people don’t walk at the same speed. Albert can cross the bridge in 1 minute, Bob can cross the bridge in 2 minutes, Carl can cross the bridge in 5 minutes, and Doug can cross the bridge in 10 minutes. It follows that when a pair is crossing, the pair travels at the speed of the slower one. What is the least amount of time the group needs to entirely cross the bridge?
Whoever wants a hint should read the next paragraph. Whoever wants to solve it on their own should stop reading now.
Let’s go over the “naive” approach and get a feel for the problem. We want to send 2 people across with the flashlight, then 1 back with the flashlight, and repeat that 3 times so that all 4 will be across the bridge. Seems like if we make Albert ferry the flashlight back and forth, you’d get a pretty fast time. Let’s have Albert go with Bob, come back, go with Carl, come back, and go with Doug. The total time is 2+1+5+1+10=19 minutes.
Only, here’s the thing. That’s not the fastest answer. Doug’s time is always going to show up in the final sum, but we haven’t taken advantage of the fact that Doug can hide Carl’s time. We want to have Doug and Carl go at the same time, but if we do that first, we have to send one back and that’s bad news. So maybe we want Albert or Bob waiting on the other side to ferry back the flashlight. We’ll try sending Albert and Bob, have Albert come back, send Carl and Doug, have Bob come back, and finally send Albert and Bob. The total time is 2+1+10+2+2=17 minutes. This is the “smart” answer.
Only, here’s the thing. Why? Whoever wants to figure it out on their own should stop reading now.
Let’s use letters instead of numbers so we can get to the heart of the problem. Let be the time it takes Albert to cross the bridge, be the time it takes Bob to cross the bridge, be the time it takes Carl to cross the bridge, and be the time it takes for Doug to cross the bridge. Let’s also use shorthand for the names of the people: a, b, c, and d. And let’s constrain it so .
I want to define the "state" of the situation. Let's say the group is crossing the bridge to go North. At the beginning, everyone and the flashlight is on the South side of the bridge. This is the state. If we send a and b across, the state is "c and d are on the South side, a and b and the flashlight are on the North side". Let's invent a shorthand for the state. We'll simply shorten "flashlight" to F, and write whoever is on the South side of the bridge, a comma, and then whoever is on the North side of the bridge. If no one is on a side of the bridge, we'll write a 0. So the initial state would be abcdF,0. If a and b cross, we'd be at cd,abF.
Now we can restate the problem in this new language: how do you get from abcdF,0 to 0,abcdF in the least amount of time? Well, there's only so many states. We can put a naive upper limit at 32 because there are 5 entities involved and each can only be in 2 positions. So we'll start from the initial state, and move to every possible next state at once. From each of those new states, we'll move to every possible next state at once. And then we'll repeat until we're sure we're not going to get any new information. While we're doing this, we'll keep track of the shortest time it took to get to each state. If it's ambiguous, we'll keep track of multiple times. We do this by appending a long dash and the shortest time to each state. Let's try it out. We start with the initial state, and 0 time to get there.
Now we visit each possible state from here and write them down as well.
From each of these new states we visit every possible next state. But we notice the first 4 new states are useless. The only way to go is back to the initial state, and we already know how to get there in 0 time. We can go from cd,abF to abcdF,0 but again we know how to get to abcdF,0 in 0 time, so we don't write it down. We can get from bd,acF to abdF,c but only after finding we can get there faster from cd,abF. So we don't write it down. Remember that . We continue working like this until we have
Only 4 new states! Well that makes sense, after 2 trips it only makes sense for 3 people and the flashlight to be South and 1 person to be North, so there can only be 4 states; one for each person. We continue.
Only 4 new states, because this time there's only 1 person South. Except one of the states is repeated because we can't tell which is smaller: or . We continue.
7 new states. With 2 people on each side, and the flashlight following its inescapable South, North, South, North path, there are only 6 ways to distribute everything. But abF,cd is duplicated because we can't don't know which is smaller: or . We can only get to the destination state from here, so this is the last step.
Well, there are two ways to get from start to finish, and we can't tell which is better. Let's see what determines which path is better in its simplest form.
Let's quickly find out what the two paths are. I never simplified the sums until the end so that we could read them backward to reconstruct the paths. The first path is send a and b, send a back, send c and d, send b back, send a and b, which corresponds to the "smart" answer above. By process of elimination, the second path must correspond to the "naive" answer. You can trace it to check. At this point we appreciate that the problem was doctored against us. The "naive" answer isn't really naive; it works sometimes, but whoever made the problem thought "I'll make it so that the obvious answer isn't right!" and made sure . And we are also sure now that there are only two possible solutions.
Some of you might have realized we were using Dijkstra's algorithm to solve the puzzle. Some of you might not know what Dijkstra's algorithm is, so maybe you are interested to know that problems like these often end up in computer science land. Finally, some of you might have heard of Dijkstra's algorithm in school and not really understood it. When it was explained to me, there were costs and stacks or queues and flags needed to ensure the thing ever stopped, so I didn't get it right away. It's not hard. It's pretty much the simplest (correct) way you can come up with for finding the shortest path between two things, and the rest is implementation.