ISourceCode

Make the frequent cases fast and the rare case correct

U2 Crossing the Bridge

One thing that excited me while reading “How would you move Mount Fuji?” was stepping upon question 42 about a bunch of people crossing a bridge. But they are no ordinary people they are band members of U2.This reminded me of U2 performance of “city of blinding lights” at Brooklyn bridge where Bono becomes nostalgic and talks about arriving in US , crossing the bridge blah blah.Anyways i guess i am trying to connect unnecessary dots here.

So music apart, zeroing on the problem:
A group of N people wishes to cross a rickety bridge with only one torch,bridge can hold only 2 people. A mechanism must be devised to get to other side of the bridge as fast as possible, You do not want your fans to be pissed with you.

Solution: Firstly this is a famous problem with answers floating around over the Internet. To be more specific this particular question with 4 people and speeds of 1 ,2 ,5 and 10 has been asked frequently in interviews.

The solution for the question 42 of the book is simple

Step 1
a: 1+2 cross bridge = Total time = 2
b: 1 returns = Total time = 3

Step2
a: 5+10 cross bridge = Total time = 13
b: 2 return = Total time = 15

Step 3
a: 1+2 cross bridge = Total time = 17

That was quickest possible way for the band to get to other side

import java.util.Arrays;
import java.util.Scanner;

public class bridge {

	private static int sum;

	public static int TotalTime(int[] band, int n) {
		
		if (n < 3) {
			 return band[n-1];
		} else if (n == 3) {
			return band[0] + band[1] + band[2];
		} else {
			int temp1 = band[n-1] + band[0] + band[n - 2] + band[0];
			int temp2 = band[1] + band[0] + band[n-1] + band[1];
			
			if (temp1 < temp2){
				return  temp1 + TotalTime(band, n - 2);
			}
			else if (temp2 < temp1){
				return  temp2 + TotalTime(band, n - 2); 
			}else{
				return  temp2 + TotalTime(band, n - 2); 
			}
		}
	}

	public static void main(String[] args) {
		System.out.println("Enter the number of band members");        	
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		int[] band = new int[n];
		System.out.println("Enter the time each member needs to cross the bridge");
		for(int member = 0; member < n ; member++)
		{
			band[member] = input.nextInt();
		}
		Arrays.sort(band);
		System.out.println("The total time take to cross the bridge is: ");
		System.out.println(bridge.TotalTime(band, n));
          
	}

}

OUTPUT:

labuser@ubuntu:~$ java bridge
Enter the number of band members
4
Enter the time each member needs to cross the bridge
1
2
5
10
The total time take to cross the bridge is:
17

labuser@ubuntu:~$ java bridge
Enter the number of band members
5
Enter the time each member needs to cross the bridge
1
2
5
10
12
The total time take to cross the bridge is:
25

Thanks for reading !

One response to “U2 Crossing the Bridge

  1. adn October 24, 2012 at 3:48 pm

    Can you please give some explanation about your implementation?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: