Table of Contents
Problem Statement
The “Bridge and Torch” problem states that you are given an array of time a person needs to cross the bridge. Since it is time, it comprises positive integers. Along with the time we are given a bridge, which a person needs to cross. The bridge allows only two people at a time to cross. They carry a torch while crossing. And since there is a single torch. One of the people from the other side should return and take the torch back to the starting side. When two people cross the bridge, they can cross at the speed of a slower person. Find the minimum total time in which all persons can cross the bridge.
Example
timeToCross = {1, 2, 3}6
Explanation: First, person 1 and 2 cross the bridge. So, until now 2s have passed. Now person 1 crosses or returns back to the starting side. Then person 2 and 3 cross the bridge. Thus the total time taken is = 2 + 1 + 3 = 6.
Approach for Bridge and Torch Problem
Naive Approach
We can use recursion to write a program for bridge and torch problem, to find all the permutations of the time to cross array. Then first we move two persons from one side to another with the torch. Then the fastest person from another(destination) side returns back to the initial side. Doing this, we can find the minimum time required to send all the persons from one side to another satisfying all the conditions.
But this algorithm requires exponential time to run. Thus an efficient approach is required.
Efficient Approach
We can write a program for bridge and torch problem using an efficient approach will be using dynamic programming since we can divide the initial problem into smaller subproblems which can be further subdivided into smaller subproblems. So, instead of calculating or solving the smaller subproblems multiple times. We will store the result and afterward combine those results to find our answer.
There are some things to note while solving this problem. When two persons cross the bridge, the speed of the slower person is used. Torch needs to be returned back to the initial side. Now, we need to represent the persons on the left side and the right side. We can also say the persons on the initial side and destination side.
We will use bitmask to represent one of the sides and the other side can be easily found using some bit manipulations. Considering we have three people, we use a bitmask of size ‘3’ to represent 3 people. If one person(2nd) is on the destination side. The bitmask which represents the initial side will be 101, the bitmask for destination side = (1<<n) XOR(bitmask representing initial side). Thus (2^n-1)XOR(5) = 7 XOR 5 = 2.
Now, we will use 2-dimensional Dynamic Programming dp[mask][direction of movement], where mask represents the minimum time required to move person representing the mask from left to right(direction of movement = 0) or right to left(direction of movement = 1),
Code
C++ code for Bridge and Torch Problem
#include <bits/stdc++.h>
using namespace std;
int solveBridgeAndTorchProblem(int mask, bool direction, vector<int> &timeToCross, vector<vector<int>> &dp)
{
int n = timeToCross.size();
// if nobody is left to transfer
if (!mask)
return 0;
if(dp[mask][direction]!=-1)
return dp[mask][direction];
int transferredMask = ((1<<n)-1)^mask;
int res = 0;
// transfer people from left to right (from destination to start)
if (direction == 1) {
int minRow = INT_MAX, person;
for (int i = 0; i < n; ++i) {
// choose the person with smallest time to cross bridge
if (transferredMask & (1 << i)) {
if (minRow > timeToCross[i]) {
person = i;
minRow = timeToCross[i];
}
}
}
// now send this person to let and solve for smaller problem
res = timeToCross[person] + solveBridgeAndTorchProblem(mask|(1 << person),direction^1, timeToCross, dp);
}
else {
// __builtin_popcount() counts the bits in mask
if (__builtin_popcount(mask) == 1) {
for (int i=0;i<n;++i) {
// since there is only a single person on starting side, return him
if (mask&(1<<i)) {
res = timeToCross[i];
break;
}
}
}
else {
// find the minimum time by solving for each pair
res = INT_MAX;
for(int i=0;i<n;++i) {
// if ith person is not on right side, then do nothing
if(!(mask&(1<<i)))
continue;
// else find another person and try to cross the bridge
for(int j=i+1;j<n;++j) {
if(mask&(1<<j)){
// time to cross the bridge for current pair
int val = max(timeToCross[i], timeToCross[j]);
// solve for smaller subproblems
val += solveBridgeAndTorchProblem(mask^(1<<i)^(1<<j), direction^1,timeToCross,dp);
// update the answer
res = min(res, val);
}
}
}
}
}
return dp[mask][direction] = res;
}
int main()
{
int n;cin>>n;
vector<int> timeToCross(n);
for(int i=0;i<n;i++)cin>>timeToCross[i];
vector<vector<int>> dp(1<<20, vector<int>(2,-1));
int mask = (1<<n)-1;
cout << solveBridgeAndTorchProblem(mask, 0, timeToCross, dp);
return 0;
}
5 25 6 5 8 4
54
Java code for Bridge and Torch Problem
import java.util.*;
class Main{
static int countBits(int n){
int nn = n;
int cnt = 0;
while(n>0){
if((n&1) == 1)
cnt++;
n = n/2;
}
n = nn;
return cnt;
}
static int solveBridgeAndTorchProblem(int mask, int direction, int timeToCross[], int dp[][])
{
int n = timeToCross.length;
// if nobody is left to transfer
if (mask==0)
return 0;
if(dp[mask][direction]!=-1)
return dp[mask][direction];
int transferredMask = ((1<<n)-1)^mask;
int res = 0;
// transfer people from left to right (from destination to start)
if(direction == 1) {
int minRow = Integer.MAX_VALUE, person=0;
for(int i = 0; i < n; ++i) {
// choose the person with smallest time to cross bridge
if((transferredMask & (1 << i)) > 0) {
if (minRow > timeToCross[i]) {
person = i;
minRow = timeToCross[i];
}
}
}
// now send this person to let and solve for smaller problem
res = timeToCross[person] + solveBridgeAndTorchProblem(mask|(1 << person),direction^1, timeToCross, dp);
}
else {
// countBits() counts the bits in mask
if (countBits(mask) == 1) {
for (int i=0;i<n;++i) {
// since there is only a single person on starting side, return him
if((mask&(1<<i))!=0) {
res = timeToCross[i];
break;
}
}
}
else {
// find the minimum time by solving for each pair
res = Integer.MAX_VALUE;
for(int i=0;i<n;++i) {
// if ith person is not on right side, then do nothing
if((mask&(1<<i))== 0)
continue;
// else find another person and try to cross the bridge
for(int j=i+1;j<n;++j) {
if((mask&(1<<j))>0){
// time to cross the bridge for current pair
int val = Math.max(timeToCross[i], timeToCross[j]);
// solve for smaller subproblems
val += solveBridgeAndTorchProblem(mask^(1<<i)^(1<<j), direction^1,timeToCross,dp);
// update the answer
res = Math.min(res, val);
}
}
}
}
}
return dp[mask][direction] = res;
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] timeToCross = new int[n];
for(int i=0;i<n;i++)
timeToCross[i] = sc.nextInt();
int dp[][] = new int[1<<20][2];
for(int i=0;i<(1<<20);i++){
dp[i][0] = -1;
dp[i][1] = -1;
}
int mask = (1<<n)-1;
int answer = solveBridgeAndTorchProblem(mask, 0, timeToCross, dp);
System.out.println(answer);
}
}
5 25 6 5 8 4
54
Complexity Analysis
Time Complexity: O(2^N * N^2)
We are using bitmask to represent N numbers, which contributes to 2^n. And then we check for each pair using two nested loops which give us a factor of N^2. Thus the time complexity is O(2^N * N^2).
Space Complexity: O(2^N)
We are using Dp over bitmask here. And since our DP array is dependent on direction and bitmask, where there are only 2 directions. We have exponential space complexity of O(2^N).