Efficiently solution of bridge and torch problem
Here given code implementation process.
// 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