Bridge crossing puzzle

Question

Four men have to cross a bridge at night.Any party who crosses, either one or two men, must carry the flashlight with them. The flashlight must be walked back and forth; it cannot be thrown, etc. Each man walks at a different speed. One takes 1 minute to cross, another 2 minutes, another 5, and the last 10 minutes. If two men cross together, they must walk at the slower man's pace. There are no tricks--the men all start on the same side, the flashlight cannot shine a long distance, no one can be carried, etc.

And the question is What's the fastest they can all get across. I am basically looking for some generalized approach to these kind of problem. I was told by my friend, that this can be solved by Fibonacci series, but the solution does not work for all.

Please note this is not a home work.

Answer 1

17 minutes - this is a classic MS question.

1,2 => 2 minutes passed.
1 retuns => 3 minutes passed.
5,10 => 13 minutes passed.
2 returns => 15 minutes passed.
1,2 => 17 minute passed.

In general the largest problem / slowest people should always be put together, and sufficient trips of the fastest made to be able to bring the light back each time without using a slow resource.

Answer 2

I would solve this problem by placing a fake job ad on Dice.com, and then asking this question in the interviews until someone gets it right.

Answer 3

There is an entire PDF (alternate link) that solves the general case of this problem (in a formal proof).

Answer 4

As per Wikipedia

The puzzle is known to have appeared as early as 1981, in the book Super Strategies For Puzzles and Games. In this version of the puzzle, A, B, C and D take 5, 10, 20, and 25 minutes, respectively, to cross, and the time limit is 60 minutes

This question was however popularized after its appearance in the book "How Would You Move Mount Fuji?"

the question can be generalized for N people with varying individual time taken to cross the bridge.

The below program works for a generic N no of people and their times.

class Program
{
    public static int TotalTime(List<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);
            }
        }
    }

    static void Main(string[] args)
    {
        // change the no of people crossing the bridge
        // add or remove corresponding time to the list
        int n = 4; 

        List<int> band = new List<int>() { 1, 2, 5, 10 };

        band.Sort();

        Console.WriteLine("The total time taken to cross the bridge is: " + Program.TotalTime(band, n));
        Console.ReadLine();
    }
}

OUTPUT:

The total time taken to cross the bridge is: 17

For,

int n = 5; 
List<int> band = new List<int>() { 1, 2, 5, 10, 12 };

OUTPUT:

The total time taken to cross the bridge is: 25

For,

int n = 4; 
List<int> band = new List<int>() { 5, 10, 20, 25 };

OUTPUT The total time taken to cross the bridge is: 60

Answer 5

17 -- a very common question

-> 1-2 = 2
<- 2 = 2
-> 5,10 = 10 (none of them has to return)
<- 1 = 1
-> 1,2 = 2

all on the other side
total = 2+2+10+1+2 = 17

usually people get it as 19 in the first try