Efficiently solution of bridge and torch problem
The Bridge and Torch problem is a classic puzzle that challenges people to figure out how to move a group of people across a bridge with only one torch, and with different people taking different amounts of time to cross. The goal is to get everyone across the bridge in the shortest amount of time possible.
The problem is usually presented as follows: there are four people who need to cross a bridge at night. They have only one torch, and the bridge is too dangerous to cross without it. The four people can cross the bridge at different speeds: one person can cross the bridge in 1 minute, another person in 2 minutes, a third person in 5 minutes, and the fourth person in 7 minutes. When two people cross the bridge together, they must move at the slower person's pace. What is the shortest amount of time it takes to get all four people across the bridge?.
The Bridge and Torch problem is a classic example of a problem that requires creative thinking and strategy. The solution to the problem involves making a series of carefully planned moves, and taking advantage of the different speeds of the people involved. There are different approaches to solving the problem, but the key is to optimize the use of time by minimizing the number of times the torch has to be carried across the bridge.
Bridge and Torch problem is a fun and challenging puzzle that requires careful thought and planning. It has become a classic example of a problem that requires creative thinking and strategy, and is often used as a teaching tool in mathematics, computer science, and other fields.
Code Example
// C Program for
// Efficiently solution of bridge and torch problem
// Time complexity O(n)
#include <stdio.h>
int minTime(int crossTimes[], int n)
{
if (n <= 0)
{
return 0;
}
if (n == 1)
{
// Case when have only one element
return crossTimes[0];
}
// Per Request
// ➀ Cross times must be positive 1..n
// ➁ Cross times must be ascending order.
// If second case false then first sort given crossTimes.
// it will take O(nlogn) time. But we assume time is in ascending order
// Auxiliary variables
int result = 0;
int min = 0;
// First two smallest time
int a = 0;
int b = 1;
// Use to find largest time
int c = -1;
int d = -1;
int left = 0;
for (int i = n - 1; i >= 2; --i)
{
if (c == -1)
{
c = i;
}
else if (d == -1)
{
d = i;
}
if (c != -1 && d != -1)
{
if (crossTimes[c] + crossTimes[d] + (crossTimes[a] *2) >
(crossTimes[b] *2) + crossTimes[a] + crossTimes[c])
{
// Here work 4 operation
// ab send
// [,...c,d.] --------------> [a,b...]
//
// a back
// [a,...c,d.] <-------------- [b...]
//
// cd send
// [a,...] ---------------> [b..,c,d]
//
// b back
// [a,b....] <-------------- [c,d]
result += (crossTimes[b] *2) + crossTimes[a] +
crossTimes[c];
}
else
{
// Here work 4 operation
// ac send
// [b...,d.] --------------> [a,c...]
//
// a back
// [a,b,..d.] <-------------- [c...]
//
// ad send
// [a,b,..d.] ---------------> [a,c,d...]
//
// a back
// [a,b....] <-------------- [c,d]
result += crossTimes[c] + crossTimes[d] +
(crossTimes[a] * 2);
}
// Reset
c = -1;
d = -1;
}
}
if (c != -1)
{
// When transmit remaining three element
result += crossTimes[a] + crossTimes[b] + crossTimes[c];
}
else
{
// Send pair of two smallest element
// Here add max value
result += crossTimes[b];
}
return result;
}
int main()
{
int crossTimes1[] = {
1 , 2 , 5 , 7
};
int crossTimes2[] = {
1 , 2 , 3 , 7 , 9 , 10
};
// Test A
int n = sizeof(crossTimes1) / sizeof(crossTimes1[0]);
//
// arr = [1, 2, 5, 7]
// [1,2]
// [ 5, 7] -----------> [1,2] Time 2
//
// [1]
// [1, 5, 7] <----------- [2] Time 3 (+1)
//
// [5,7]
// [1] -----------> [2,5,7] Time 10 (+7)
//
// [2]
// [1,2] <----------- [5,7] Time 12 (+1)
//
// [1,2]
// [] -----------> [1,2,5,7] Time 14 (+2)
int result = minTime(crossTimes1, n);
printf("\n %d", result);
// Test B
n = sizeof(crossTimes2) / sizeof(crossTimes2[0]);
// arr = [1,2,3,7,9,10]
//
// [1,2]
// [3,7,9,10] ---------------> [1,2] Time 2 (+2)
//
// [1]
// [1,3,7,9,10] <---------------- [2] Time 3 (+1)
//
// [9,10]
// [1,3,7] ----------------> [2,9,10] Time 13 (+10)
//
// [2]
// [1,2,3,7] <----------------- [9,10] Time 15 (+2)
//
// [1,2]
// [3,7] -----------------> [1,2,9,10] Time 17 (+2)
//
// [1]
// [1,3,7] <---------------- [2, 9,10] Time 18 (+1)
//
// [1,3]
// [7] ----------------> [1,2,3,9,10] Time 21 (+3)
//
// [1]
// [1,7] <------------------ [1,2,3,9,10] Time 22 (+1)
//
// [1,7]
// [] -------------------> [1,2,3,9,10] Time 29 (+7)
//
result = minTime(crossTimes2, n);
printf("\n %d", result);
return 0;
}Output
14
29// Java Program
// Efficiently solution of bridge and torch problem
// Time complexity O(n)
public class Puzzle
{
public int minTime(int[] crossTimes, int n)
{
if (n <= 0)
{
return 0;
}
if (n == 1)
{
// Case when have only one element
return crossTimes[0];
}
// Per Request
// ➀ Cross times must be positive 1..n
// ➁ Cross times must be ascending order.
// If second case false then first sort given crossTimes.
// it will take O(nlogn) time.
// But we assume time is in ascending order
// Auxiliary variables
int result = 0;
// First two smallest time
int a = 0;
int b = 1;
// Use to find largest time
int c = -1;
int d = -1;
for (int i = n - 1; i >= 2; --i)
{
if (c == -1)
{
c = i;
}
else if (d == -1)
{
d = i;
}
if (c != -1 && d != -1)
{
if (crossTimes[c] + crossTimes[d] + (crossTimes[a] * 2) >
(crossTimes[b] * 2) + crossTimes[a] + crossTimes[c])
{
// Here work 4 operation
// ab send
// [,...c,d.] --------------> [a,b...]
//
// a back
// [a,...c,d.] <-------------- [b...]
//
// cd send
// [a,...] ---------------> [b..,c,d]
//
// b back
// [a,b....] <-------------- [c,d]
result += (crossTimes[b] * 2) + crossTimes[a] +
crossTimes[c];
}
else
{
// Here work 4 operation
// ac send
// [b...,d.] --------------> [a,c...]
//
// a back
// [a,b,..d.] <-------------- [c...]
//
// ad send
// [a,b,..d.] ---------------> [a,c,d...]
//
// a back
// [a,b....] <-------------- [c,d]
result += crossTimes[c] +
crossTimes[d] + (crossTimes[a] * 2);
}
// Reset
c = -1;
d = -1;
}
}
if (c != -1)
{
// When transmit remaining three element
result += crossTimes[a] + crossTimes[b] + crossTimes[c];
}
else
{
// Send pair of two smallest element
// Here add max value
result += crossTimes[b];
}
return result;
}
public static void main(String args[])
{
Puzzle task = new Puzzle();
int[] crossTimes1 = {
1 , 2 , 5 , 7
};
int[] crossTimes2 = {
1 , 2 , 3 , 7 , 9 , 10
};
// Test A
int n = crossTimes1.length;
//
// arr = [1, 2, 5, 7]
// [1,2]
// [ 5, 7] -----------> [1,2] Time 2
//
// [1]
// [1, 5, 7] <----------- [2] Time 3 (+1)
//
// [5,7]
// [1] -----------> [2,5,7] Time 10 (+7)
//
// [2]
// [1,2] <----------- [5,7] Time 12 (+1)
//
// [1,2]
// [] -----------> [1,2,5,7] Time 14 (+2)
int result = task.minTime(crossTimes1, n);
System.out.print("\n " + result);
// Test B
n = crossTimes2.length;
// arr = [1,2,3,7,9,10]
//
// [1,2]
// [3,7,9,10] ---------------> [1,2] Time 2 (+2)
//
// [1]
// [1,3,7,9,10] <---------------- [2] Time 3 (+1)
//
// [9,10]
// [1,3,7] ----------------> [2,9,10] Time 13 (+10)
//
// [2]
// [1,2,3,7] <----------------- [9,10] Time 15 (+2)
//
// [1,2]
// [3,7] -----------------> [1,2,9,10] Time 17 (+2)
//
// [1]
// [1,3,7] <---------------- [2, 9,10] Time 18 (+1)
//
// [1,3]
// [7] ----------------> [1,2,3,9,10] Time 21 (+3)
//
// [1]
// [1,7] <------------------ [1,2,3,9,10] Time 22 (+1)
//
// [1,7]
// [] -------------------> [1,2,3,9,10] Time 29 (+7)
//
result = task.minTime(crossTimes2, n);
System.out.print("\n " + result);
}
}Output
14
29// Include header file
#include <iostream>
using namespace std;
// C++ Program
// Efficiently solution of bridge and torch problem
// Time complexity O(n)
class Puzzle
{
public: int minTime(int crossTimes[], int n)
{
if (n <= 0)
{
return 0;
}
if (n == 1)
{
// Case when have only one element
return crossTimes[0];
}
// Per Request
// ➀ Cross times must be positive 1..n
// ➁ Cross times must be ascending order.
// If second case false then first sort given crossTimes.
// it will take O(nlogn) time.
// But we assume time is in ascending order
// Auxiliary variables
int result = 0;
// First two smallest time
int a = 0;
int b = 1;
// Use to find largest time
int c = -1;
int d = -1;
for (int i = n - 1; i >= 2; --i)
{
if (c == -1)
{
c = i;
}
else if (d == -1)
{
d = i;
}
if (c != -1 && d != -1)
{
if (crossTimes[c] + crossTimes[d] + (crossTimes[a] *2) >
(crossTimes[b] *2) + crossTimes[a] + crossTimes[c])
{
// Here work 4 operation
// ab send
// [,...c,d.] --------------> [a,b...]
//
// a back
// [a,...c,d.] <-------------- [b...]
//
// cd send
// [a,...] ---------------> [b..,c,d]
//
// b back
// [a,b....] <-------------- [c,d]
result += (crossTimes[b] *2) + crossTimes[a] +
crossTimes[c];
}
else
{
// Here work 4 operation
// ac send
// [b...,d.] --------------> [a,c...]
//
// a back
// [a,b,..d.] <-------------- [c...]
//
// ad send
// [a,b,..d.] ---------------> [a,c,d...]
//
// a back
// [a,b....] <-------------- [c,d]
result += crossTimes[c] + crossTimes[d] +
(crossTimes[a] *2);
}
// Reset
c = -1;
d = -1;
}
}
if (c != -1)
{
// When transmit remaining three element
result += crossTimes[a] + crossTimes[b] + crossTimes[c];
}
else
{
// Send pair of two smallest element
// Here add max value
result += crossTimes[b];
}
return result;
}
};
int main()
{
Puzzle *task = new Puzzle();
int crossTimes1[] = {
1 , 2 , 5 , 7
};
int crossTimes2[] = {
1 , 2 , 3 , 7 , 9 , 10
};
// Test A
int n = sizeof(crossTimes1) / sizeof(crossTimes1[0]);
//
// arr = [1, 2, 5, 7]
// [1,2]
// [ 5, 7] -----------> [1,2] Time 2
//
// [1]
// [1, 5, 7] <----------- [2] Time 3 (+1)
//
// [5,7]
// [1] -----------> [2,5,7] Time 10 (+7)
//
// [2]
// [1,2] <----------- [5,7] Time 12 (+1)
//
// [1,2]
// [] -----------> [1,2,5,7] Time 14 (+2)
int result = task->minTime(crossTimes1, n);
cout << "\n " << result;
// Test B
n = sizeof(crossTimes2) / sizeof(crossTimes2[0]);
// arr = [1,2,3,7,9,10]
//
// [1,2]
// [3,7,9,10] ---------------> [1,2] Time 2 (+2)
//
// [1]
// [1,3,7,9,10] <---------------- [2] Time 3 (+1)
//
// [9,10]
// [1,3,7] ----------------> [2,9,10] Time 13 (+10)
//
// [2]
// [1,2,3,7] <----------------- [9,10] Time 15 (+2)
//
// [1,2]
// [3,7] -----------------> [1,2,9,10] Time 17 (+2)
//
// [1]
// [1,3,7] <---------------- [2, 9,10] Time 18 (+1)
//
// [1,3]
// [7] ----------------> [1,2,3,9,10] Time 21 (+3)
//
// [1]
// [1,7] <------------------ [1,2,3,9,10] Time 22 (+1)
//
// [1,7]
// [] -------------------> [1,2,3,9,10] Time 29 (+7)
//
result = task->minTime(crossTimes2, n);
cout << "\n " << result;
return 0;
}Output
14
29// Include namespace system
using System;
// Csharp Program
// Efficiently solution of bridge and torch problem
// Time complexity O(n)
public class Puzzle
{
public int minTime(int[] crossTimes, int n)
{
if (n <= 0)
{
return 0;
}
if (n == 1)
{
// Case when have only one element
return crossTimes[0];
}
// Per Request
// ➀ Cross times must be positive 1..n
// ➁ Cross times must be ascending order.
// If second case false then first sort given crossTimes.
// it will take O(nlogn) time.
// But we assume time is in ascending order
// Auxiliary variables
int result = 0;
// First two smallest time
int a = 0;
int b = 1;
// Use to find largest time
int c = -1;
int d = -1;
for (int i = n - 1; i >= 2; --i)
{
if (c == -1)
{
c = i;
}
else if (d == -1)
{
d = i;
}
if (c != -1 && d != -1)
{
if (crossTimes[c] + crossTimes[d] + (crossTimes[a] * 2) >
(crossTimes[b] * 2) + crossTimes[a] + crossTimes[c])
{
// Here work 4 operation
// ab send
// [,...c,d.] --------------> [a,b...]
//
// a back
// [a,...c,d.] <-------------- [b...]
//
// cd send
// [a,...] ---------------> [b..,c,d]
//
// b back
// [a,b....] <-------------- [c,d]
result += (crossTimes[b] * 2) + crossTimes[a] +
crossTimes[c];
}
else
{
// Here work 4 operation
// ac send
// [b...,d.] --------------> [a,c...]
//
// a back
// [a,b,..d.] <-------------- [c...]
//
// ad send
// [a,b,..d.] ---------------> [a,c,d...]
//
// a back
// [a,b....] <-------------- [c,d]
result += crossTimes[c] + crossTimes[d] +
(crossTimes[a] * 2);
}
// Reset
c = -1;
d = -1;
}
}
if (c != -1)
{
// When transmit remaining three element
result += crossTimes[a] + crossTimes[b] + crossTimes[c];
}
else
{
// Send pair of two smallest element
// Here add max value
result += crossTimes[b];
}
return result;
}
public static void Main(String[] args)
{
Puzzle task = new Puzzle();
int[] crossTimes1 = {
1 , 2 , 5 , 7
};
int[] crossTimes2 = {
1 , 2 , 3 , 7 , 9 , 10
};
// Test A
int n = crossTimes1.Length;
//
// arr = [1, 2, 5, 7]
// [1,2]
// [ 5, 7] -----------> [1,2] Time 2
//
// [1]
// [1, 5, 7] <----------- [2] Time 3 (+1)
//
// [5,7]
// [1] -----------> [2,5,7] Time 10 (+7)
//
// [2]
// [1,2] <----------- [5,7] Time 12 (+1)
//
// [1,2]
// [] -----------> [1,2,5,7] Time 14 (+2)
int result = task.minTime(crossTimes1, n);
Console.Write("\n " + result);
// Test B
n = crossTimes2.Length;
// arr = [1,2,3,7,9,10]
//
// [1,2]
// [3,7,9,10] ---------------> [1,2] Time 2 (+2)
//
// [1]
// [1,3,7,9,10] <---------------- [2] Time 3 (+1)
//
// [9,10]
// [1,3,7] ----------------> [2,9,10] Time 13 (+10)
//
// [2]
// [1,2,3,7] <----------------- [9,10] Time 15 (+2)
//
// [1,2]
// [3,7] -----------------> [1,2,9,10] Time 17 (+2)
//
// [1]
// [1,3,7] <---------------- [2, 9,10] Time 18 (+1)
//
// [1,3]
// [7] ----------------> [1,2,3,9,10] Time 21 (+3)
//
// [1]
// [1,7] <------------------ [1,2,3,9,10] Time 22 (+1)
//
// [1,7]
// [] -------------------> [1,2,3,9,10] Time 29 (+7)
//
result = task.minTime(crossTimes2, n);
Console.Write("\n " + result);
}
}Output
14
29package main
import "fmt"
// Go Program
// Efficiently solution of bridge and torch problem
// Time complexity O(n)
type Puzzle struct {}
func getPuzzle() * Puzzle {
var me *Puzzle = &Puzzle {}
return me
}
func(this Puzzle) minTime(crossTimes[] int, n int) int {
if n <= 0 {
return 0
}
if n == 1 {
// Case when have only one element
return crossTimes[0]
}
// Per Request
// ➀ Cross times must be positive 1..n
// ➁ Cross times must be ascending order.
// If second case false then first sort given crossTimes.
// it will take O(nlogn) time.
// But we assume time is in ascending order
// Auxiliary variables
var result int = 0
// First two smallest time
var a int = 0
var b int = 1
// Use to find largest time
var c int = -1
var d int = -1
for i := n - 1 ; i >= 2 ; i-- {
if c == -1 {
c = i
} else if d == -1 {
d = i
}
if c != -1 && d != -1 {
if crossTimes[c] + crossTimes[d] + (crossTimes[a] * 2) >
(crossTimes[b] * 2) + crossTimes[a] + crossTimes[c] {
// Here work 4 operation
// ab send
// [,...c,d.] --------------> [a,b...]
//
// a back
// [a,...c,d.] <-------------- [b...]
//
// cd send
// [a,...] ---------------> [b..,c,d]
//
// b back
// [a,b....] <-------------- [c,d]
result += (crossTimes[b] * 2) + crossTimes[a] +
crossTimes[c]
} else {
// Here work 4 operation
// ac send
// [b...,d.] --------------> [a,c...]
//
// a back
// [a,b,..d.] <-------------- [c...]
//
// ad send
// [a,b,..d.] ---------------> [a,c,d...]
//
// a back
// [a,b....] <-------------- [c,d]
result += crossTimes[c] + crossTimes[d] +
(crossTimes[a] * 2)
}
// Reset
c = -1
d = -1
}
}
if c != -1 {
// When transmit remaining three element
result += crossTimes[a] + crossTimes[b] + crossTimes[c]
} else {
// Send pair of two smallest element
// Here add max value
result += crossTimes[b]
}
return result
}
func main() {
var task * Puzzle = getPuzzle()
var crossTimes1 = [] int {
1,
2,
5,
7,
}
var crossTimes2 = [] int {
1,
2,
3,
7,
9,
10,
}
// Test A
var n int = len(crossTimes1)
//
// arr = [1, 2, 5, 7]
// [1,2]
// [ 5, 7] -----------> [1,2] Time 2
//
// [1]
// [1, 5, 7] <----------- [2] Time 3 (+1)
//
// [5,7]
// [1] -----------> [2,5,7] Time 10 (+7)
//
// [2]
// [1,2] <----------- [5,7] Time 12 (+1)
//
// [1,2]
// [] -----------> [1,2,5,7] Time 14 (+2)
var result int = task.minTime(crossTimes1, n)
fmt.Print("\n ", result)
// Test B
n = len(crossTimes2)
// arr = [1,2,3,7,9,10]
//
// [1,2]
// [3,7,9,10] ---------------> [1,2] Time 2 (+2)
//
// [1]
// [1,3,7,9,10] <---------------- [2] Time 3 (+1)
//
// [9,10]
// [1,3,7] ----------------> [2,9,10] Time 13 (+10)
//
// [2]
// [1,2,3,7] <----------------- [9,10] Time 15 (+2)
//
// [1,2]
// [3,7] -----------------> [1,2,9,10] Time 17 (+2)
//
// [1]
// [1,3,7] <---------------- [2, 9,10] Time 18 (+1)
//
// [1,3]
// [7] ----------------> [1,2,3,9,10] Time 21 (+3)
//
// [1]
// [1,7] <------------------ [1,2,3,9,10] Time 22 (+1)
//
// [1,7]
// [] -------------------> [1,2,3,9,10] Time 29 (+7)
//
result = task.minTime(crossTimes2, n)
fmt.Print("\n ", result)
}Output
14
29<?php
// Php Program
// Efficiently solution of bridge and torch problem
// Time complexity O(n)
class Puzzle
{
public function minTime($crossTimes, $n)
{
if ($n <= 0)
{
return 0;
}
if ($n == 1)
{
// Case when have only one element
return $crossTimes[0];
}
// Per Request
// ➀ Cross times must be positive 1..n
// ➁ Cross times must be ascending order.
// If second case false then first sort given crossTimes.
// it will take O(nlogn) time.
// But we assume time is in ascending order
// Auxiliary variables
$result = 0;
// First two smallest time
$a = 0;
$b = 1;
// Use to find largest time
$c = -1;
$d = -1;
for ($i = $n - 1; $i >= 2; --$i)
{
if ($c == -1)
{
$c = $i;
}
else if ($d == -1)
{
$d = $i;
}
if ($c != -1 && $d != -1)
{
if ($crossTimes[$c] + $crossTimes[$d] + ($crossTimes[$a] * 2) >
($crossTimes[$b] * 2) + $crossTimes[$a] + $crossTimes[$c])
{
// Here work 4 operation
// ab send
// [,...c,d.] --------------> [a,b...]
//
// a back
// [a,...c,d.] <-------------- [b...]
//
// cd send
// [a,...] ---------------> [b..,c,d]
//
// b back
// [a,b....] <-------------- [c,d]
$result += ($crossTimes[$b] * 2) +
$crossTimes[$a] + $crossTimes[$c];
}
else
{
// Here work 4 operation
// ac send
// [b...,d.] --------------> [a,c...]
//
// a back
// [a,b,..d.] <-------------- [c...]
//
// ad send
// [a,b,..d.] ---------------> [a,c,d...]
//
// a back
// [a,b....] <-------------- [c,d]
$result += $crossTimes[$c] +
$crossTimes[$d] + ($crossTimes[$a] * 2);
}
// Reset
$c = -1;
$d = -1;
}
}
if ($c != -1)
{
// When transmit remaining three element
$result += $crossTimes[$a] +
$crossTimes[$b] + $crossTimes[$c];
}
else
{
// Send pair of two smallest element
// Here add max value
$result += $crossTimes[$b];
}
return $result;
}
}
function main()
{
$task = new Puzzle();
$crossTimes1 = array(1, 2, 5, 7);
$crossTimes2 = array(1, 2, 3, 7, 9, 10);
// Test A
$n = count($crossTimes1);
//
// arr = [1, 2, 5, 7]
// [1,2]
// [ 5, 7] -----------> [1,2] Time 2
//
// [1]
// [1, 5, 7] <----------- [2] Time 3 (+1)
//
// [5,7]
// [1] -----------> [2,5,7] Time 10 (+7)
//
// [2]
// [1,2] <----------- [5,7] Time 12 (+1)
//
// [1,2]
// [] -----------> [1,2,5,7] Time 14 (+2)
$result = $task->minTime($crossTimes1, $n);
echo("\n ".$result);
// Test B
$n = count($crossTimes2);
// arr = [1,2,3,7,9,10]
//
// [1,2]
// [3,7,9,10] ---------------> [1,2] Time 2 (+2)
//
// [1]
// [1,3,7,9,10] <---------------- [2] Time 3 (+1)
//
// [9,10]
// [1,3,7] ----------------> [2,9,10] Time 13 (+10)
//
// [2]
// [1,2,3,7] <----------------- [9,10] Time 15 (+2)
//
// [1,2]
// [3,7] -----------------> [1,2,9,10] Time 17 (+2)
//
// [1]
// [1,3,7] <---------------- [2, 9,10] Time 18 (+1)
//
// [1,3]
// [7] ----------------> [1,2,3,9,10] Time 21 (+3)
//
// [1]
// [1,7] <------------------ [1,2,3,9,10] Time 22 (+1)
//
// [1,7]
// [] -------------------> [1,2,3,9,10] Time 29 (+7)
//
$result = $task->minTime($crossTimes2, $n);
echo("\n ".$result);
}
main();Output
14
29// Node JS Program
// Efficiently solution of bridge and torch problem
// Time complexity O(n)
class Puzzle
{
minTime(crossTimes, n)
{
if (n <= 0)
{
return 0;
}
if (n == 1)
{
// Case when have only one element
return crossTimes[0];
}
// Per Request
// ➀ Cross times must be positive 1..n
// ➁ Cross times must be ascending order.
// If second case false then first sort given crossTimes.
// it will take O(nlogn) time.
// But we assume time is in ascending order
// Auxiliary variables
var result = 0;
// First two smallest time
var a = 0;
var b = 1;
// Use to find largest time
var c = -1;
var d = -1;
for (var i = n - 1; i >= 2; --i)
{
if (c == -1)
{
c = i;
}
else if (d == -1)
{
d = i;
}
if (c != -1 && d != -1)
{
if (crossTimes[c] + crossTimes[d] + (crossTimes[a] * 2) >
(crossTimes[b] * 2) + crossTimes[a] + crossTimes[c])
{
// Here work 4 operation
// ab send
// [,...c,d.] --------------> [a,b...]
//
// a back
// [a,...c,d.] <-------------- [b...]
//
// cd send
// [a,...] ---------------> [b..,c,d]
//
// b back
// [a,b....] <-------------- [c,d]
result += (crossTimes[b] * 2) + crossTimes[a] +
crossTimes[c];
}
else
{
// Here work 4 operation
// ac send
// [b...,d.] --------------> [a,c...]
//
// a back
// [a,b,..d.] <-------------- [c...]
//
// ad send
// [a,b,..d.] ---------------> [a,c,d...]
//
// a back
// [a,b....] <-------------- [c,d]
result += crossTimes[c] + crossTimes[d] +
(crossTimes[a] * 2);
}
// Reset
c = -1;
d = -1;
}
}
if (c != -1)
{
// When transmit remaining three element
result += crossTimes[a] + crossTimes[b] + crossTimes[c];
}
else
{
// Send pair of two smallest element
// Here add max value
result += crossTimes[b];
}
return result;
}
}
function main()
{
var task = new Puzzle();
var crossTimes1 = [1, 2, 5, 7];
var crossTimes2 = [1, 2, 3, 7, 9, 10];
// Test A
var n = crossTimes1.length;
//
// arr = [1, 2, 5, 7]
// [1,2]
// [ 5, 7] -----------> [1,2] Time 2
//
// [1]
// [1, 5, 7] <----------- [2] Time 3 (+1)
//
// [5,7]
// [1] -----------> [2,5,7] Time 10 (+7)
//
// [2]
// [1,2] <----------- [5,7] Time 12 (+1)
//
// [1,2]
// [] -----------> [1,2,5,7] Time 14 (+2)
var result = task.minTime(crossTimes1, n);
process.stdout.write("\n " + result);
// Test B
n = crossTimes2.length;
// arr = [1,2,3,7,9,10]
//
// [1,2]
// [3,7,9,10] ---------------> [1,2] Time 2 (+2)
//
// [1]
// [1,3,7,9,10] <---------------- [2] Time 3 (+1)
//
// [9,10]
// [1,3,7] ----------------> [2,9,10] Time 13 (+10)
//
// [2]
// [1,2,3,7] <----------------- [9,10] Time 15 (+2)
//
// [1,2]
// [3,7] -----------------> [1,2,9,10] Time 17 (+2)
//
// [1]
// [1,3,7] <---------------- [2, 9,10] Time 18 (+1)
//
// [1,3]
// [7] ----------------> [1,2,3,9,10] Time 21 (+3)
//
// [1]
// [1,7] <------------------ [1,2,3,9,10] Time 22 (+1)
//
// [1,7]
// [] -------------------> [1,2,3,9,10] Time 29 (+7)
//
result = task.minTime(crossTimes2, n);
process.stdout.write("\n " + result);
}
main();Output
14
29# Python 3 Program
# Efficiently solution of bridge and torch problem
# Time complexity O(n)
class Puzzle :
def minTime(self, crossTimes, n) :
if (n <= 0) :
return 0
if (n == 1) :
# Case when have only one element
return crossTimes[0]
# Per Request
# ➀ Cross times must be positive 1..n
# ➁ Cross times must be ascending order.
# If second case false then first sort given crossTimes.
# it will take O(nlogn) time.
# But we assume time is in ascending order
# Auxiliary variables
result = 0
# First two smallest time
a = 0
b = 1
# Use to find largest time
c = -1
d = -1
i = n - 1
while (i >= 2) :
if (c == -1) :
c = i
elif (d == -1) :
d = i
if (c != -1 and d != -1) :
if (crossTimes[c] + crossTimes[d] + (crossTimes[a] * 2) >
(crossTimes[b] * 2) + crossTimes[a] + crossTimes[c]) :
# Here work 4 operation
# ab send
# [,...c,d.] --------------> [a,b...]
# a back
# [a,...c,d.] <-------------- [b...]
# cd send
# [a,...] ---------------> [b..,c,d]
# b back
# [a,b....] <-------------- [c,d]
result += (crossTimes[b] * 2) + crossTimes[a] + crossTimes[c]
else :
# Here work 4 operation
# ac send
# [b...,d.] --------------> [a,c...]
# a back
# [a,b,..d.] <-------------- [c...]
# ad send
# [a,b,..d.] ---------------> [a,c,d...]
# a back
# [a,b....] <-------------- [c,d]
result += crossTimes[c] + crossTimes[d] + (crossTimes[a] * 2)
# Reset
c = -1
d = -1
i -= 1
if (c != -1) :
# When transmit remaining three element
result += crossTimes[a] + crossTimes[b] + crossTimes[c]
else :
# Send pair of two smallest element
# Here add max value
result += crossTimes[b]
return result
def main() :
task = Puzzle()
crossTimes1 = [1, 2, 5, 7]
crossTimes2 = [1, 2, 3, 7, 9, 10]
# Test A
n = len(crossTimes1)
# arr = [1, 2, 5, 7]
# [1,2]
# [ 5, 7] -----------> [1,2] Time 2
# [1]
# [1, 5, 7] <----------- [2] Time 3 (+1)
# [5,7]
# [1] -----------> [2,5,7] Time 10 (+7)
# [2]
# [1,2] <----------- [5,7] Time 12 (+1)
# [1,2]
# [] -----------> [1,2,5,7] Time 14 (+2)
result = task.minTime(crossTimes1, n)
print("\n ", result, end = "")
# Test B
n = len(crossTimes2)
# arr = [1,2,3,7,9,10]
# [1,2]
# [3,7,9,10] ---------------> [1,2] Time 2 (+2)
# [1]
# [1,3,7,9,10] <---------------- [2] Time 3 (+1)
# [9,10]
# [1,3,7] ----------------> [2,9,10] Time 13 (+10)
# [2]
# [1,2,3,7] <----------------- [9,10] Time 15 (+2)
# [1,2]
# [3,7] -----------------> [1,2,9,10] Time 17 (+2)
# [1]
# [1,3,7] <---------------- [2, 9,10] Time 18 (+1)
# [1,3]
# [7] ----------------> [1,2,3,9,10] Time 21 (+3)
# [1]
# [1,7] <------------------ [1,2,3,9,10] Time 22 (+1)
# [1,7]
# [] -------------------> [1,2,3,9,10] Time 29 (+7)
result = task.minTime(crossTimes2, n)
print("\n ", result, end = "")
if __name__ == "__main__": main()Output
14
29# Ruby Program
# Efficiently solution of bridge and torch problem
# Time complexity O(n)
class Puzzle
def minTime(crossTimes, n)
if (n <= 0)
return 0
end
if (n == 1)
# Case when have only one element
return crossTimes[0]
end
# Per Request
# ➀ Cross times must be positive 1..n
# ➁ Cross times must be ascending order.
# If second case false then first sort given crossTimes.
# it will take O(nlogn) time.
# But we assume time is in ascending order
# Auxiliary variables
result = 0
# First two smallest time
a = 0
b = 1
# Use to find largest time
c = -1
d = -1
i = n - 1
while (i >= 2)
if (c == -1)
c = i
elsif (d == -1)
d = i
end
if (c != -1 && d != -1)
if (crossTimes[c] + crossTimes[d] + (crossTimes[a] * 2) >
(crossTimes[b] * 2) + crossTimes[a] + crossTimes[c])
# Here work 4 operation
# ab send
# [,...c,d.] --------------> [a,b...]
# a back
# [a,...c,d.] <-------------- [b...]
# cd send
# [a,...] ---------------> [b..,c,d]
# b back
# [a,b....] <-------------- [c,d]
result += (crossTimes[b] * 2) + crossTimes[a] +
crossTimes[c]
else
# Here work 4 operation
# ac send
# [b...,d.] --------------> [a,c...]
# a back
# [a,b,..d.] <-------------- [c...]
# ad send
# [a,b,..d.] ---------------> [a,c,d...]
# a back
# [a,b....] <-------------- [c,d]
result += crossTimes[c] + crossTimes[d] +
(crossTimes[a] * 2)
end
# Reset
c = -1
d = -1
end
i -= 1
end
if (c != -1)
# When transmit remaining three element
result += crossTimes[a] + crossTimes[b] + crossTimes[c]
else
# Send pair of two smallest element
# Here add max value
result += crossTimes[b]
end
return result
end
end
def main()
task = Puzzle.new()
crossTimes1 = [1, 2, 5, 7]
crossTimes2 = [1, 2, 3, 7, 9, 10]
# Test A
n = crossTimes1.length
# arr = [1, 2, 5, 7]
# [1,2]
# [ 5, 7] -----------> [1,2] Time 2
# [1]
# [1, 5, 7] <----------- [2] Time 3 (+1)
# [5,7]
# [1] -----------> [2,5,7] Time 10 (+7)
# [2]
# [1,2] <----------- [5,7] Time 12 (+1)
# [1,2]
# [] -----------> [1,2,5,7] Time 14 (+2)
result = task.minTime(crossTimes1, n)
print("\n ", result)
# Test B
n = crossTimes2.length
# arr = [1,2,3,7,9,10]
# [1,2]
# [3,7,9,10] ---------------> [1,2] Time 2 (+2)
# [1]
# [1,3,7,9,10] <---------------- [2] Time 3 (+1)
# [9,10]
# [1,3,7] ----------------> [2,9,10] Time 13 (+10)
# [2]
# [1,2,3,7] <----------------- [9,10] Time 15 (+2)
# [1,2]
# [3,7] -----------------> [1,2,9,10] Time 17 (+2)
# [1]
# [1,3,7] <---------------- [2, 9,10] Time 18 (+1)
# [1,3]
# [7] ----------------> [1,2,3,9,10] Time 21 (+3)
# [1]
# [1,7] <------------------ [1,2,3,9,10] Time 22 (+1)
# [1,7]
# [] -------------------> [1,2,3,9,10] Time 29 (+7)
result = task.minTime(crossTimes2, n)
print("\n ", result)
end
main()Output
14
29// Scala Program
// Efficiently solution of bridge and torch problem
// Time complexity O(n)
class Puzzle()
{
def minTime(crossTimes: Array[Int], n: Int): Int = {
if (n <= 0)
{
return 0;
}
if (n == 1)
{
// Case when have only one element
return crossTimes(0);
}
// Per Request
// ➀ Cross times must be positive 1..n
// ➁ Cross times must be ascending order.
// If second case false then first sort given crossTimes.
// it will take O(nlogn) time.
// But we assume time is in ascending order
// Auxiliary variables
var result: Int = 0;
// First two smallest time
var a: Int = 0;
var b: Int = 1;
// Use to find largest time
var c: Int = -1;
var d: Int = -1;
var i: Int = n - 1;
while (i >= 2)
{
if (c == -1)
{
c = i;
}
else if (d == -1)
{
d = i;
}
if (c != -1 && d != -1)
{
if (crossTimes(c) + crossTimes(d) + (crossTimes(a) * 2) >
(crossTimes(b) * 2) + crossTimes(a) + crossTimes(c))
{
// Here work 4 operation
// ab send
// [,...c,d.] --------------> [a,b...]
//
// a back
// [a,...c,d.] <-------------- [b...]
//
// cd send
// [a,...] ---------------> [b..,c,d]
//
// b back
// [a,b....] <-------------- [c,d]
result += (crossTimes(b) * 2) + crossTimes(a) +
crossTimes(c);
}
else
{
// Here work 4 operation
// ac send
// [b...,d.] --------------> [a,c...]
//
// a back
// [a,b,..d.] <-------------- [c...]
//
// ad send
// [a,b,..d.] ---------------> [a,c,d...]
//
// a back
// [a,b....] <-------------- [c,d]
result += crossTimes(c) + crossTimes(d) +
(crossTimes(a) * 2);
}
// Reset
c = -1;
d = -1;
}
i -= 1;
}
if (c != -1)
{
// When transmit remaining three element
result += crossTimes(a) + crossTimes(b) + crossTimes(c);
}
else
{
// Send pair of two smallest element
// Here add max value
result += crossTimes(b);
}
return result;
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Puzzle = new Puzzle();
var crossTimes1: Array[Int] = Array(1, 2, 5, 7);
var crossTimes2: Array[Int] = Array(1, 2, 3, 7, 9, 10);
// Test A
var n: Int = crossTimes1.length;
//
// arr = [1, 2, 5, 7]
// [1,2]
// [ 5, 7] -----------> [1,2] Time 2
//
// [1]
// [1, 5, 7] <----------- [2] Time 3 (+1)
//
// [5,7]
// [1] -----------> [2,5,7] Time 10 (+7)
//
// [2]
// [1,2] <----------- [5,7] Time 12 (+1)
//
// [1,2]
// [] -----------> [1,2,5,7] Time 14 (+2)
var result: Int = task.minTime(crossTimes1, n);
print("\n " + result);
// Test B
n = crossTimes2.length;
// arr = [1,2,3,7,9,10]
//
// [1,2]
// [3,7,9,10] ---------------> [1,2] Time 2 (+2)
//
// [1]
// [1,3,7,9,10] <---------------- [2] Time 3 (+1)
//
// [9,10]
// [1,3,7] ----------------> [2,9,10] Time 13 (+10)
//
// [2]
// [1,2,3,7] <----------------- [9,10] Time 15 (+2)
//
// [1,2]
// [3,7] -----------------> [1,2,9,10] Time 17 (+2)
//
// [1]
// [1,3,7] <---------------- [2, 9,10] Time 18 (+1)
//
// [1,3]
// [7] ----------------> [1,2,3,9,10] Time 21 (+3)
//
// [1]
// [1,7] <------------------ [1,2,3,9,10] Time 22 (+1)
//
// [1,7]
// [] -------------------> [1,2,3,9,10] Time 29 (+7)
//
result = task.minTime(crossTimes2, n);
print("\n " + result);
}
}Output
14
29import Foundation;
// Swift 4 Program
// Efficiently solution of bridge and torch problem
// Time complexity O(n)
class Puzzle
{
func minTime(_ crossTimes: [Int], _ n: Int) -> Int
{
if (n <= 0)
{
return 0;
}
if (n == 1)
{
// Case when have only one element
return crossTimes[0];
}
// Per Request
// ➀ Cross times must be positive 1..n
// ➁ Cross times must be ascending order.
// If second case false then first sort given crossTimes.
// it will take O(nlogn) time.
// But we assume time is in ascending order
// Auxiliary variables
var result: Int = 0;
// First two smallest time
let a: Int = 0;
let b: Int = 1;
// Use to find largest time
var c: Int = -1;
var d: Int = -1;
var i: Int = n - 1;
while (i >= 2)
{
if (c == -1)
{
c = i;
}
else if (d == -1)
{
d = i;
}
if (c != -1 && d != -1)
{
if (crossTimes[c] + crossTimes[d] + (crossTimes[a] * 2) >
(crossTimes[b] * 2) + crossTimes[a] + crossTimes[c])
{
// Here work 4 operation
// ab send
// [,...c,d.] --------------> [a,b...]
//
// a back
// [a,...c,d.] <-------------- [b...]
//
// cd send
// [a,...] ---------------> [b..,c,d]
//
// b back
// [a,b....] <-------------- [c,d]
result += (crossTimes[b] * 2) + crossTimes[a] +
crossTimes[c];
}
else
{
// Here work 4 operation
// ac send
// [b...,d.] --------------> [a,c...]
//
// a back
// [a,b,..d.] <-------------- [c...]
//
// ad send
// [a,b,..d.] ---------------> [a,c,d...]
//
// a back
// [a,b....] <-------------- [c,d]
result += crossTimes[c] + crossTimes[d] +
(crossTimes[a] * 2);
}
// Reset
c = -1;
d = -1;
}
i -= 1;
}
if (c != -1)
{
// When transmit remaining three element
result += crossTimes[a] + crossTimes[b] + crossTimes[c];
}
else
{
// Send pair of two smallest element
// Here add max value
result += crossTimes[b];
}
return result;
}
}
func main()
{
let task: Puzzle = Puzzle();
let crossTimes1: [Int] = [1, 2, 5, 7];
let crossTimes2: [Int] = [1, 2, 3, 7, 9, 10];
// Test A
var n: Int = crossTimes1.count;
//
// arr = [1, 2, 5, 7]
// [1,2]
// [ 5, 7] -----------> [1,2] Time 2
//
// [1]
// [1, 5, 7] <----------- [2] Time 3 (+1)
//
// [5,7]
// [1] -----------> [2,5,7] Time 10 (+7)
//
// [2]
// [1,2] <----------- [5,7] Time 12 (+1)
//
// [1,2]
// [] -----------> [1,2,5,7] Time 14 (+2)
var result: Int = task.minTime(crossTimes1, n);
print("\n ", result, terminator: "");
// Test B
n = crossTimes2.count;
// arr = [1,2,3,7,9,10]
//
// [1,2]
// [3,7,9,10] ---------------> [1,2] Time 2 (+2)
//
// [1]
// [1,3,7,9,10] <---------------- [2] Time 3 (+1)
//
// [9,10]
// [1,3,7] ----------------> [2,9,10] Time 13 (+10)
//
// [2]
// [1,2,3,7] <----------------- [9,10] Time 15 (+2)
//
// [1,2]
// [3,7] -----------------> [1,2,9,10] Time 17 (+2)
//
// [1]
// [1,3,7] <---------------- [2, 9,10] Time 18 (+1)
//
// [1,3]
// [7] ----------------> [1,2,3,9,10] Time 21 (+3)
//
// [1]
// [1,7] <------------------ [1,2,3,9,10] Time 22 (+1)
//
// [1,7]
// [] -------------------> [1,2,3,9,10] Time 29 (+7)
//
result = task.minTime(crossTimes2, n);
print("\n ", result, terminator: "");
}
main();Output
14
29// Kotlin Program
// Efficiently solution of bridge and torch problem
// Time complexity O(n)
class Puzzle
{
fun minTime(crossTimes: Array < Int > , n: Int): Int
{
if (n <= 0)
{
return 0;
}
if (n == 1)
{
// Case when have only one element
return crossTimes[0];
}
// Per Request
// ➀ Cross times must be positive 1..n
// ➁ Cross times must be ascending order.
// If second case false then first sort given crossTimes.
// it will take O(nlogn) time.
// But we assume time is in ascending order
// Auxiliary variables
var result: Int = 0;
// First two smallest time
val a: Int = 0;
val b: Int = 1;
// Use to find largest time
var c: Int = -1;
var d: Int = -1;
var i: Int = n - 1;
while (i >= 2)
{
if (c == -1)
{
c = i;
}
else if (d == -1)
{
d = i;
}
if (c != -1 && d != -1)
{
if (crossTimes[c] + crossTimes[d] + (crossTimes[a] * 2) >
(crossTimes[b] * 2) + crossTimes[a] + crossTimes[c])
{
// Here work 4 operation
// ab send
// [,...c,d.] --------------> [a,b...]
//
// a back
// [a,...c,d.] <-------------- [b...]
//
// cd send
// [a,...] ---------------> [b..,c,d]
//
// b back
// [a,b....] <-------------- [c,d]
result += (crossTimes[b] * 2) +
crossTimes[a] + crossTimes[c];
}
else
{
// Here work 4 operation
// ac send
// [b...,d.] --------------> [a,c...]
//
// a back
// [a,b,..d.] <-------------- [c...]
//
// ad send
// [a,b,..d.] ---------------> [a,c,d...]
//
// a back
// [a,b....] <-------------- [c,d]
result += crossTimes[c] +
crossTimes[d] + (crossTimes[a] * 2);
}
// Reset
c = -1;
d = -1;
}
i -= 1;
}
if (c != -1)
{
// When transmit remaining three element
result += crossTimes[a] + crossTimes[b] + crossTimes[c];
}
else
{
// Send pair of two smallest element
// Here add max value
result += crossTimes[b];
}
return result;
}
}
fun main(args: Array < String > ): Unit
{
val task: Puzzle = Puzzle();
val crossTimes1: Array < Int > = arrayOf(1, 2, 5, 7);
val crossTimes2: Array < Int > = arrayOf(1, 2, 3, 7, 9, 10);
// Test A
var n: Int = crossTimes1.count();
//
// arr = [1, 2, 5, 7]
// [1,2]
// [ 5, 7] -----------> [1,2] Time 2
//
// [1]
// [1, 5, 7] <----------- [2] Time 3 (+1)
//
// [5,7]
// [1] -----------> [2,5,7] Time 10 (+7)
//
// [2]
// [1,2] <----------- [5,7] Time 12 (+1)
//
// [1,2]
// [] -----------> [1,2,5,7] Time 14 (+2)
var result: Int = task.minTime(crossTimes1, n);
print("\n " + result);
// Test B
n = crossTimes2.count();
// arr = [1,2,3,7,9,10]
//
// [1,2]
// [3,7,9,10] ---------------> [1,2] Time 2 (+2)
//
// [1]
// [1,3,7,9,10] <---------------- [2] Time 3 (+1)
//
// [9,10]
// [1,3,7] ----------------> [2,9,10] Time 13 (+10)
//
// [2]
// [1,2,3,7] <----------------- [9,10] Time 15 (+2)
//
// [1,2]
// [3,7] -----------------> [1,2,9,10] Time 17 (+2)
//
// [1]
// [1,3,7] <---------------- [2, 9,10] Time 18 (+1)
//
// [1,3]
// [7] ----------------> [1,2,3,9,10] Time 21 (+3)
//
// [1]
// [1,7] <------------------ [1,2,3,9,10] Time 22 (+1)
//
// [1,7]
// [] -------------------> [1,2,3,9,10] Time 29 (+7)
//
result = task.minTime(crossTimes2, n);
print("\n " + result);
}Output
14
29
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment