Home » Technical Interview Questions » Dynamic Programming Interview Questions » Program for Bridge and Torch problem

Program for Bridge and Torch problem


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

Program for Bridge and Torch problem

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).

READ  Alien Dictionary

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).

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup