Posted on by Kalkicode
Code Puzzle

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
 29
package 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
 29
import 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

Comment

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