How to solve the bridge crossing puzzle in Java ?

In this blog we are going solve an interesting puzzle of bridge crossing in Java. The bridge crossing puzzle is also referred to as the Bridge and Torch problem.We will first understand what the puzzle is all about, come with different logical solutions and finally we will write the code for the same in Java. As always, I will approach the code step by step so that you get a complete understanding of the solution.

What is the bridge crossing problem ?

It is night time and 4 people come to a river. There is a bridge and one torch. They need to get to the other side of the river using the bridge. This bridge is narrow and hence only 2 people can cross the bridge at a time. Since it is night time, the torch has to be used.

Each person takes a certain amount of time to cross the bridge. Person A can cross the bridge in 1 minute, B in 2 minutes, C in 5 minutes and D in 8 minutes. When 2 people cross the bridge, they walk at the slower person’s pace. The question is – Can we get them across the bridge in 15 or fewer minutes since the torch only lasts for 15 minutes ?

A quick solution that comes to mind

If A and B were to start crossing the bridge with the torch, they would take 2 minutes to get to the other side. Person A takes 1 minute and B takes 2 but A has to walk at B’s speed. Person ‘A’ seems to be the fastest among them. So common logic says, let’s get ‘A’ back. So ‘A’ comes back with the torch, now the total time is 3, 2 from earlier one and 1 for ‘A’ to come back. We had 2 journeys so far, 1 forward and 1 backward.

We would assume that since ‘A’ is the fastest, ‘A’ should be the torchbearer and help everyone cross one by one. So ‘A’ and ‘C’ start crossing the bridge. They walk at C’s speed. Now the total time is 3 + 5 = 8. 3 from the earlier journeys and the 5 from C’s speed. Now, our fastest, the torchbearer needs to come back. So 8 + 1 = 9. So we have had 2 more journeys, 4 in all. 2 forward and 2 backward.

Finally, person ‘D’ remains. Our great torchbearer,’A’, and ‘D’ start walking, taking a time of 8 minutes which is D’s speed. The total time is 9 + 8 = 17 minutes. This was one more journey, so we have a total of 4 + 1 = 5 journeys. This was a forward journey. So for 4 people, we had 3 forward and 2 backward journeys and a total time of 17 when A, the fastest among all does the torch bearing activity.

Well, well, well – this is not the optimum solution although it seems like it is. The torch only works for 15 minutes !

The right logical solution

It seems that since A takes the least amount of time to cross the bridge, we must send everyone else with A. In the solution above, C and D are crossing separately. If we made them cross together, we could actually do better. Let’s try that solution.

This is definitely a better solution and in fact the right solution given the condition. All 4 people have crossed the bridge in 15 minutes. The key here is that in step 3, C and D, the slowest among the 4, travelled together rather than individual trips across the bridge.

Technical analysis

We have 4 people, let us represent this using ‘n’, we have n = 4.

We will be receiving the time taken by each person to cross the bridge as an input. How can we store this ? The simplest is an array. Note that we will sort this array in ascending order.

If we were to sort the array in descending order and started the journey with ‘C’ or ‘D’ , we would have made ‘C’ to travel back with the torch and then ‘C’ has to go to the other side at some point in time. So ‘C’ would have travelled thrice increasing the overall time which would not be a feasible solution.

int [] timeToCross =  { 1, 2, 5, 8};

So, timeToCross[0] indicates the time taken by A which is 1 minute. In the logical steps shown above, Step 1 shows ‘A’ and ‘B’ starting off their journey, followed by ‘A’ coming back. How can we represent that using the array we just created ?

Step 1 and 2

timeToCross[1] + timeToCross[0]

Let’s break it up. timeToCross[1] indicates time taken by ‘B’. The first step is ‘A’ and ‘B’ crossing together. The time taken is the time taken by ‘B’ to cross since ‘B’ is slower than ‘A’ and that is the reason why the array is also sorted. So the first logical step of ‘A’ and ‘B’ crossing is represented as timeToCross[1].

The timeToCross[0] is the time taken by ‘A’. Why do we have this ? Well, step 2 is ‘A’ coming back. So we have combined logical steps of 1 and 2 in one line of code.

Step 3

Step 3 is ‘C’ and ‘D’ crossing together. The time taken will be time taken by ‘D’ since ‘D’ is slowest among ‘C’ and ‘D’. How can we represent that using the array?

timeToCross[n-1]

Since, n =4, we refer to it with index, n-1, the index starts from 0. n-1 =3 which is the index of ‘D’.

Step 4

We have managed to get ‘C’ and ‘D’ , the slowest among all 4 to cross the bridge. Now, the next step is ‘B’ coming back with the torch. This can be shown as

timeToCross[1]

At the end of this step 4, we have managed to get 2 people among 4 to the other side of the bridge. What is the total time so far ? Let combine the code from steps 1, 2, 3 and 4.

timeToCross[1] + timeToCross[0] + timeToCross[n-1] + timeToCross[1];

Let’s add all this code into a function

public static int totalTime(int[] timeToCross , int n)
{
            int time = timeToCross[1] + timeToCross[0] + timeToCross[n-1] + timeToCross[1];

}

Extending the problem to have ‘n’ people crossing the bridge

We have 2 people left out of 4. This is 4 -2. We represented this number 4 by ‘n’. If we were to generalize this puzzle for ‘n’ persons, at this point, we would always have ‘n-2’ persons left for crossing. So with ‘A’,’B’,’C’,’D’, we have ‘A’ and ‘B’ left.

What if we have more than 4 persons ? What if we had ‘n’ persons ? We apply the same logic for the remaining n-2 people. It looks like we have solved a part of the problem, a subproblem. When we need to apply the same logic for the remaining data, recursion can be a good idea. The input to this function will be the time that we have calculated so far and the second input will be 2 fewer persons.

public static int totalTime(int[] timeToCross , int n)
{
            int time = timeToCross[1] + timeToCross[0] + timeToCross[n-1] + timeToCross[1];

            return time + totalTime(timeToCross, n - 2)
}

What if the actual input supplied to this function had only 2 or 3 people instead of 4 ? What if we had just 1 person to cross the bridge ? This can be solved with the following conditions –

public static int totalTime(int[] timeToCross , int n)
{
        if (n < 3)
        {
            //as the elements are sorted.
            return timeToCross[n - 1];
        }
        //3 people will be addition of all.
        else if (n == 3)
        {
            return timeToCross[0] + timeToCross[1] + timeToCross[2];
        }
        //n>=4
        int time = timeToCross[1] + timeToCross[0] + timeToCross[n-1] + timeToCross[1];

        return time + totalTime(timeToCross, n - 2)
}

When there are 1 or 2 people to cross the bridge, n = 1 or 2

If the total number of persons who want to cross the bridge is either 1 or 2, we simply return the time taken by n – 1. For 1 person, n = 1 , timeToCross[n-1] will be timeToCross[0] which will be the only input to the problem. For 2 persons, n = 2 , the array is sorted, hence timeToCross[n – 1] = timeToCross[2 -1] = timeToCross[1]. This is the slowest of the 2 persons and the input is also 2 people. The first ‘if’ condition in the code takes care of this scenario.

When there are 3 people to cross the bridge, n =3

If n=3 , time taken will be addition of all 3. How is that ? If A, B and C were to cross the bridge, A and B start the journey, time taken will be the addition of: time taken by ‘B’ , followed by ‘A’ returning with the torch and finally time taken by ‘A’ and ‘C’ which is time taken by ‘C’. So time taken by A +B + C. This is handled with 2nd if condition.

Back to our puzzle where we have 4 people, the final step , step 5

At the end of step 4, C and D are on the other side of the bridge. We are left with A and B. When A and B start crossing the bridge, time taken by them is 2 minutes, since B, the slower one takes 2 minutes. The total time upto step 4 was calculated by code on line 2 below.

     //n>=4
     int time = timeToCross[1] + timeToCross[0] + timeToCross[n-1] + timeToCross[1];

     return time + totalTime(timeToCross, n - 2)

For final step 5, last line above is executed. When called recursively, n < 3, so we return timeToCross[1]. So when ‘A ‘ and ‘B’ are left, timeToCross[1] will be time taken by ‘B’ which is 2. This final step 5 gets handled in the condition: if(n < 3).

public static int totalTime(int[] timeToCross , int n)
{
        if (n < 3)
        {
            //as the elements are sorted.
            return timeToCross[n - 1];
        }
        //3 people will be addition of all.
        ...
        //n >= 4
        ...
}

Does it work for all scenarios ?

Scenario 2

From a logical perspective –

1. A and B start their journey and take a total time of 2.
2. ‘A’ returns which means the total time is now 2+1 = 3.
3. ‘C’ and ‘D’ walk across, this means, 3 + 10 = 13.
4. ‘B’ returns with the torch, 13 + 2 = 15.
5. Finally, ‘A’ and ‘B’ walk across, 15 + 2 = 17.

In short, it is {A,B} + {A} + {C,D} + {B} + {A,B}

From the code perspective, n >=4 , so what is executed first is

int time = timeToCross[1] + timeToCross[0] + timeToCross[n-1] + timeToCross[1];

return time + totalTime(timeToCross, n - 2)

timeToCross [] = {1, 2, 5, 10}. So, substituting these values in the code above results in: 2 + 1 + 10 + 2 = 15. See the trace of the logical step above, that is what we get at end of step 4. Finally, the 2nd line in the code snippet above is executed, the recursive call. This will result in 15 + recursive call with n-2.

When this recursive call is executed, n =2. So the first ‘if ‘ condition is satisfied, this returns 15 + timeToCross[n-1] , n = 2, so it returns 15 + timeToCross[1] which is 15 + 2, that is 17. So we get 15 +2 = 17. Looks like the code works fine.

Scenario 3

Well, let us apply the same approach like the earlier scenarios.

1. A+ B travel together, they take 20 minutes.
2. ‘A’ returns with the torch, 20 + 1 = 21.
3. ‘C’ and ‘D’ travel. This results in a total time of 21 + 22. 21 from earlier one and 22 from current. Total so far is 43.
4. Now ‘B’ comes back with the torch, 43 + 20 = 63.
5. Finally, ‘A ‘ and ‘B’ cross, 63 + 20 = 83.

Unfortunately, this is not the optimum solution.

We need another approach here. Let’s try to get C and D to the other end but this time with A, the one taking the least duration to cross.

1. A + D travel together, time taken is 22.
2. Then ‘A’ returns, total time is 22 + 1 = 23.
3. Then ‘A’ and ‘C’ travel. This results in , 23 + 21 , 23 from earlier one and 21 from current. The total so far is 44. Note that, at the end of this step, ‘C’ and ‘D’, the slowest among all are on other side of the bridge.
4. Now ‘A’ comes back, 44 + 1 = 45.
5. Finally, ‘A ‘ and ‘B’ cross, 45 + 20 = 65.

From the code perspective, we need to make changes to handle this scenario as well. So the sequence here is – {A , D} ,{ A } , {A , C} , {A } , {A , B}. Since, n =4, we get :

timeToCross[n-1] + timeToCross[0] + timeToCross[n-2] +timeToCross[0]

The n -1 indicates the index of ‘D’, n -2 indicates index of ‘C’. After this, we have the recursive call which will handle the last part of A+B travelling together.

Two cases for all scenarios

We have seen 2 cases now. How do we choose between them ? Well, we take the minimum from both and solve the subproblem at hand. Then the recursive calls will solve the rest of the problem.

int timeTakenCaseOne = timeToCross[1] + timeToCross[0] + timeToCross[n-1] + timeToCross[1];
int timeTakenCaseTwo  = timeToCross[n-1] + timeToCross[0] + timeToCross[n-2] + timeToCross[0];

public static int totalTime(int[] timeToCross , int n){
    	//Either 2 people or 1 person.
        if (n < 3)
        {
        	//as the elements are sorted.
            return timeToCross[n - 1];
        }
        //3 people will be addition of all.
        else if (n == 3)
        {
            return timeToCross[0] + timeToCross[1] + timeToCross[2];
        }
        // n >= 4
        else
        {
            int timeTakenCaseOne = timeToCross[1] + timeToCross[0] + timeToCross[n-1] + timeToCross[1];
            int timeTakenCaseTwo  = timeToCross[n-1] + timeToCross[0] + timeToCross[n-2] + timeToCross[0];

            if (timeTakenCaseOne < timeTakenCaseTwo)
            {
                return timeTakenCaseOne + totalTime(timeToCross, n - 2);
            }
            else if (timeTakenCaseTwo < timeTakenCaseOne)
            {
                return timeTakenCaseTwo + totalTime(timeToCross, n - 2);
            }
            return timeTakenCaseTwo + totalTime(timeToCross, n - 2);
        }
}

The are no changes in the code when n < 2 or when n = 3. Only changes are when n >= 4. We need to handle 2 scenarios and take the minimum from them. The calculation, timeTakenCaseOne has been calculated like before. timeTakenCaseTwo is the calculation which we had to consider for a scenario that failed. We simply consider the minimum value and recursively solve the subproblem.

Conclusion

We considered multiple scenarios and finally we came up with 2 paths out of which we considered the optimum path. The code can handle all scenarios now and is generic enough for ‘n’ persons wanting to cross the bridge. This was done using recursion which can be a very effective technique to solve problems like the bridge and torch.

The bridge and torch puzzle is an interesting one, the code is really not that difficult but one needs to be aware of all scenarios. As a quick tip, we find optimum time between the 2 cases mentioned below and then apply recursion.

1. ‘C’ and ‘D’ (the slowest) cross together.
2. ‘C’ and ‘D’ (slowest) cross with ‘A’, the fastest among all.

I would request you to solve one scenario on paper to get a much better understanding of the same. A good scenario would be the following input {1,6,10,13,15,16,17}. The output of this should be 75.

Happy bridge crossing !

References

Wiki has a good description about the problem which can help you get started.

A very interesting paper by Rote on this puzzle which does a deep dive.

R-Bloggers has a very good read on the same problem, the code is in R language.