Bridge Crossing at Night

Difficulty: Medium, Asked-In: Google, Microsoft

Problem Statement

A group of four people, who have one torch, need to cross a bridge at night. A maximum of two people can cross the bridge at one time, and any pair that crosses (either one or two people) must have the torch with them. The torch must be walked back and forth and cannot be thrown. Person A takes 1 minute to cross the bridge, person B takes 2 minutes, person C takes 5 minutes, and person D takes 10 minutes. A pair must walk together at the rate of the slower person’s pace. Find the fastest way they can accomplish this task.

Solution Idea using Greedy Approach: 19 Minutes

Here we need to consider the following constraints:

• There is only one torch and the bridge cannot be crossed without it.
• There cannot be more than two persons on the bridge at any time.
• When two people cross the bridge together, they must move at a slower person’s pace.

So total time to cross the bridge will be the summation of the time taken to cross the bridge and the time taken by people to return with the torch. To find the shortest time, we need to minimize the time to cross the bridge and return time. Now during return, the person who takes the minimum time to cross the bridge would be the obvious choice.

• The greedy algorithm starts by sending to the other side the two fastest people, that is, persons A and B (it will take 2 minutes) and then return the torch with the fastest of the two, that is, person A (1 more minute).
• Then we will send the two fastest persons available i.e. persons A and C (5 minutes) and return the torch with the fastest person A (1 minute). 
• Finally, the two persons remaining will cross the river together (10 minutes). The total amount of time = (2 + 1) + (5 + 1) + 10 = 19

 Efficient Solution Idea: 17 minutes

To design a solution for this problem, three two-person trips and two one-person trips are needed for four people to get to the other side in a minimum amount of time. If the flashlight is returned by the fastest person on both back trips, the fastest person will have to participate in each pair going to the other side, for the total time of 2 + (1 + 10) + (1 + 5) = 19 minutes. 

In the above strategy, both slowest persons make a separate trip with the fastest person and take a total of 15 minutes combined. Can we think about reducing the time here? Can we think of sending the slowest people together? Insight is: the difference between the fastest people (1 and 2 minutes) is just 1 minute but the difference between the slowest people (5 and 10 minutes) is 5 minutes. 

Suppose one of the two back trips is not made by the fastest person. In other words, let's try the second best possibility: one back trip of the fastest person (1 minute) and one back trip of the second-fastest person (2 minutes). The return crossing times will be at least 1 + 2 = 3 minutes i.e. 1-minute return trip for the fastest person and 2 minutes return trip for the second-fastest person. 

Trips to the other side will be at least 2 + 10 + 2 = 14 minutes because the pair of slowest people (5, 10) will take 10 minutes to cross the bridge. At the same time, the other two pairs, i.e. the first and last trip of pairs (1, 2), will take at least 2 minutes each. Therefore, the total crossing time will take at least 17 minutes. 

Another insight: Person A and B can cross the bridge together, and A can return back with the torch. Now we have a choice to select two people out of A(1), C(5), and D(10). We want to reduce the time taken by the slowest person C & D here, and we already have a faster person B on the other side. So we can send C and D together, and B can return back with the torch. Now A and B can cross the bridge with the torch. Total time to cross the bridge = (A + B) + A + (C + D) + B + (A + B) = B + A + D + B + B = A + 3B + D = 17 Minutes

Critical ideas to think?

• Why greedy approach is not providing an efficient solution?
• Can we solve a general puzzle case where n people need to cross a bridge under the same constraints as described above with some given crossing times for each person?

Suggested puzzles to explore

The Königsberg Bridges Problem: is it possible, in a single traversal, to cross all seven bridges exactly once and return to the starting point? The figure shows a sketch of the river with its two islands and seven bridges.

Ferrying Soldiers: A detachment of 25 soldiers must cross a broad and deep river with no bridge in sight. They notice two 12-year-old boys playing in a rowboat by the shore. However, the boat is so tiny that it can only hold two boys or one soldier. How can the soldiers get across the river and leave the boys in joint possession of the boat? How many times does the boat pass from shore to shore in your algorithm?

Two Jealous Husbands: Two married couples need to cross a river. They have a boat that can hold no more than two people at a time. To complicate matters, both husbands are jealous and require that no wife can be in the other man's presence without her husband being present. Can they cross the river under such constraints?

A Wolf, a Goat, and a Cabbage: A man finds himself on a riverbank with a wolf, a goat, and a head of cabbage. He needs to transport all three to the other side of the river in his boat. However, the boat has room for only the man himself and one other item (either the wolf, the goat, or the cabbage). In his absence, the wolf would eat the goat, and the goat would eat the cabbage. Show how the man can get all these “passengers” to the other side.

Missionaries and Cannibals: Three missionaries and three cannibals must cross a river. Their boat can only hold two people, and it cannot cross the river by itself with no people on board. Each missionary and each cannibal can row the boat. If present, missionaries cannot be outnumbered by cannibals. How can all six get across the river with the fewest crossings?

Reference: Algorithmic Puzzles by Anany Levitin and Maria Levitin

Enjoy learning, Enjoy mathematics!