Solving algorithmic puzzles is one of the most effective ways to sharpen your optimization skills. Among these puzzles, the Bridge and Torch Problem (often referred to as the bridge crossing puzzle) stands out. It looks simple at first, but it quickly reveals the limits of a simple greedy strategy. It serves as an excellent model for learning how to compare multiple mathematical strategies to find a globally optimal solution. Let's break down this classic puzzle and look at how we can implement its solution in Java.

The Scenario Explained

Imagine a group of people standing on one side of a narrow bridge in the middle of the night. They all need to cross to the safe side, but they must work around a strict set of real-world constraints:

  • Strict Capacity: The bridge can only support a maximum of two people at any given time.
  • The Only Torch: It is pitch black, and the group has only one flashlight. Anyone crossing the bridge—in either direction—must hold the flashlight to cross safely.
  • Varying Speeds: Everyone walks at a different pace. When two people cross the bridge together, they must walk at the pace of the slower person.
  • Returning the Torch: Since the flashlight cannot be thrown across, someone who has already crossed must walk back across the bridge to bring it to the remaining group.

The objective is to get the entire group across the bridge in the shortest total time possible.

The Strategy

To find the absolute minimum crossing time, we start by sorting the group by their individual crossing speeds in ascending order. Once sorted, the key to the solution is a greedy choice. At each step, we look at the two slowest remaining people and evaluate two distinct strategies to send them across:

Strategy 1: The Shuttle Partnering (Using the two fastest people)

This strategy is highly effective when the two slowest people are exceptionally slow. By sending them across the bridge together, we only pay for the slowest person's time once:

  1. The two fastest people (let's call them Speed[0] and Speed[1]) cross the bridge first. Time: Speed[1]
  2. The fastest person (Speed[0]) returns alone with the flashlight. Time: Speed[0]
  3. The two slowest remaining people (Speed[n-1] and Speed[n-2]) cross together. Time: Speed[n-1]
  4. The second-fastest person (Speed[1]), who is already on the other side, returns alone with the flashlight. Time: Speed[1]

Total Time for this round: 2 * Speed[1] + Speed[n-1] + Speed[0]

Strategy 2: The Fast Escort (Using only the single fastest person)

This strategy works best when the fastest person is so fast that it's cheaper to use them as a dedicated courier to walk the slower people across one by one:

  1. The fastest person (Speed[0]) escorts the slowest person (Speed[n-1]) across, then runs back alone with the flashlight. Time: Speed[n-1] + Speed[0]
  2. The fastest person (Speed[0]) escorts the next-slowest person (Speed[n-2]) across, then runs back alone with the flashlight. Time: Speed[n-2] + Speed[0]

Total Time for this round: 2 * Speed[0] + Speed[n-1] + Speed[n-2]

In each round, the code calculates the cost of both strategies, picks the cheaper option, and marks the two slowest people as successfully crossed. We repeat this loop until three or fewer people remain, which we then handle as simple base cases.

How This Looks in Java Code

Here is the complete Java implementation of this optimization problem. It uses a Map to represent the people and their speeds, sorts them, and iterates through the group dynamically comparing both crossing strategies.

package io.practise.accolite;
 
import java.util.*;
 
public class CalculateMinPossibleTime {
 
    public static int calculateMinTime(HashMap<String, Integer> personTimeMap) {
        List<Map.Entry<String, Integer>> people = new ArrayList<>(personTimeMap.entrySet());
        
        // Sort people by their individual crossing times
        people.sort(Map.Entry.comparingByValue());
 
        int n = people.size();
        int totalTime = 0;
 
        // While there are more than 3 people remaining, send the two slowest across
        while (n > 3) {
            int firstPersonTimer = people.get(0).getValue();
            int secondPersonTimer = people.get(1).getValue();
            int timeN = people.get(n - 1).getValue();
            int timeNMinus1 = people.get(n - 2).getValue();
 
            // Cost of Strategy 1 vs Strategy 2
            totalTime += Math.min(
                2 * secondPersonTimer + timeN + firstPersonTimer, 
                2 * firstPersonTimer + timeN + timeNMinus1
            );
 
            n -= 2; // Two slowest are now safely across
        }
 
        // Handle the remaining 1, 2, or 3 people
        if (n == 3) {
            totalTime += people.get(0).getValue() + people.get(1).getValue() + people.get(2).getValue();
        } else if (n == 2) {
            totalTime += people.get(1).getValue();
        } else if (n == 1) {
            totalTime += people.get(0).getValue();
        }
 
        return totalTime;
    }
 
    public static void main(String[] args) {
        HashMap<String, Integer> personTimeMap = new HashMap<>();
 
        personTimeMap.put("A", 1);
        personTimeMap.put("B", 3);
        personTimeMap.put("G", 48);
        personTimeMap.put("E", 50);
        personTimeMap.put("F", 75);
        personTimeMap.put("C", 200);
        personTimeMap.put("D", 150);
 
        int minTime = calculateMinTime(personTimeMap);
        System.out.println("Minimum time to cross the bridge: " + minTime);
    }
}

Walkthrough of the Main Method Scenario

Let's trace the algorithm step-by-step using the exact dataset from the main method:

  • A: 1 min (fastest)
  • B: 3 min (second fastest)
  • G: 48 min
  • E: 50 min
  • F: 75 min
  • D: 150 min
  • C: 200 min (slowest)
Round 1: Sending C (200) and D (150) across

We compare the two strategies for sending the two slowest people across the bridge:

  • Strategy 1 (Two-Car Shuttle): A & B cross (3m) → A returns (1m) → C & D cross (200m) → B returns (3m).
    Total time: 3 + 1 + 200 + 3 = 207 mins.
  • Strategy 2 (Solo Escort): A & C cross (200m) → A returns (1m) → A & D cross (150m) → A returns (1m).
    Total time: 200 + 1 + 150 + 1 = 352 mins.

The algorithm picks Strategy 1 because it's much faster (207 mins). C and D are now safely across.

Round 2: Sending F (75) and E (50) across

Now the two slowest remaining people are F and E:

  • Strategy 1 (Two-Car Shuttle): A & B cross (3m) → A returns (1m) → F & E cross (75m) → B returns (3m).
    Total time: 3 + 1 + 75 + 3 = 82 mins.
  • Strategy 2 (Solo Escort): A & F cross (75m) → A returns (1m) → A & E cross (50m) → A returns (1m).
    Total time: 75 + 1 + 50 + 1 = 127 mins.

The algorithm picks Strategy 1 again (82 mins). F and E are now safely across.

Round 3: The Base Case (A, B, and G remaining)

With only three people left (A:1, B:3, G:48), we hit the base case:
A & B cross (3m) → A returns (1m) → A & G cross (48m).
Total time: 3 + 1 + 48 = 52 mins.

Final Combined Time: 207 + 82 + 52 = 341 minutes. This matches the program output exactly!

Final Thoughts

The Bridge and Torch problem shows how making a greedy choice at each step requires checking multiple paths. Rather than sticking to a single rule of thumb, comparing the costs of two different strategies in each iteration guarantees we find the absolute minimum crossing time for any distribution of speeds!