Wednesday, March 26, 2014

Two egg puzzle

Problem:

There is a building of 100 floors. If an egg drops from the Nth floor or above it will break. If it’s dropped from any floor below, it will not break. You’re given 2 eggs. Find N, while minimizing the number of drops for the worst case.

Solution

This is similar as binary search. If we have unlimited number of eggs, we only need 7 (log 100 to base 2) to find N i.e. we will first throw egg at midway say 50, and if it breaks we will see N between 1 and 49, otherwise between 51 to 100.

But we only have 2 eggs. We can then still do binary search until the egg breaks, then do a linear search. So, we can use binary search with one egg till it breaks. Use linear search with the second egg till it breaks. And you have the solution. If that’s not clear enough allow me to explain.


Let us assume N = 78. We then do as follows:
  1. Drop a egg from level 50. The egg does not break. We then know N is between 51 to 100.
  2. Drop the egg from level 75. The egg does not break. We then know N is between 76 to 100.
  3. Drop the egg from level 88. The egg breaks. We then know N is between 76 to 87.
  4. Drop the egg from level 76. The egg does not break. We then know N is between 77 to 87.
  5. Drop the egg from level 77. The egg does not break. We then know N is between 78 to 87.
  6. Drop the egg from level 78. The egg break. We then know N is exactly 78.
This works fine for some number. But assume N = 49. The first drop will break the egg. So we know N is between 1 to 49. We then need to drop the second egg for 49 times until we find N = 49.

Goal: 

Create a system for dropping Egg1 so that the most drops required is consistent, whether Egg1 breaks on the first drop or the last drop.
  1. A perfectly load balanced system would be one in which Drops of Egg1 + Drops of Egg2 is always the same, regardless of where Egg1 broke.
  2. For that to be the case, since each drop of Egg1 takes one more step, Egg2 is allowed one fewer step.
  3. We must, therefore, reduce the number of steps potentially required by Egg2 by one drop each time. For example, if Egg1 is dropped on Floor 20 and then Floor 30, Egg2 is potentially required to take 9 steps. When we drop Egg1 again, we must reduce potential Egg2 steps to only 8. That is, we must drop Egg1 at floor 39.
  4. We know, therefore, Egg1 must start at Floor X, then go up by X-1 floors, then X-2, …, until it gets to 100.
  5. Solve for X+(X-1)+(X-2)+…+1 = 100 i.e. X(X+1)/2 = 100 -> X = 14 (13.6 nearly)
Hence, We go to Floor 14, then 27, then 39, … This takes 14 steps maximum.

Note that we can have eggs replaced some other things like marble, but puzzle eventually remains same.

Extending it to n eggs with k floors

This can be handled by using dynamic programming. We know:

  • An egg that survives a fall can be used again.
  • A broken egg must be discarded.
  • The effect of a fall is the same for all eggs.
  • If an egg breaks when dropped, then it would break if dropped from a higher floor.
  • If an egg survives a fall then it would survive a shorter fall.
  • It is not ruled out that the first-floor windows break eggs, nor is it ruled out that the 36th-floor do not cause an egg to break.

Optimal Substructure:
When we drop an egg from a floor x, there can be two cases :
  1. The egg breaks - If the egg breaks after dropping from xth floor, then we only need to check for floors lower than x with remaining eggs; so the problem reduces to x-1 floors and n-1 eggs
  2. The egg doesn’t break - If the egg doesn’t break after dropping from the xth floor, then we only need to check for floors higher than x; so the problem reduces to k-x floors and n eggs.

Since we need to minimize the number of trials in worst case, we take the maximum of two cases. We consider the max of above two cases for every floor and choose the floor which yields minimum number of trials.

  k ==> Number of floors
  n ==> Number of Eggs
  eggDrop(n, k) ==> Minimum number of trails needed to find the critical
                    floor in worst case.
  eggDrop(n, k) = 1 + min{max(eggDrop(n - 1, x - 1), eggDrop(n, k - x)): 
                 x in {1, 2, ..., k}}

Recursive solution
Following is recursive implementation that simply follows the recursive structure mentioned above.
// Function to get minimum number of trails needed in worst
//  case with n eggs and k floors 
//n - eggs, k - floors
int eggDrop(int n, int k)
{
    // If there are no floors, then no trials needed. OR if there is
    // one floor, one trial needed.
    if (k == 1 || k == 0)
        return k;
 
    // We need k trials for one egg and k floors
    if (n == 1)
        return k;
 
    int min = Integer.MAX, x, res;
 
    // Consider all droppings from 1st floor to kth floor and
    // return the minimum of these values plus 1.
    for (x = 1; x <= k; x++)
    {
        res = Math.max(eggDrop(n-1, x-1), eggDrop(n, k-x));
        if (res < min)
            min = res;
    }
 
    return min + 1;
}

But there will be cases where same eggDrop(E) function will be called again and again.So, to overcome that we need DP.
Here is the program in java:

/* Function to get minimum number of trails needed in worst
  case with n eggs and k floors */
int eggDrop(int n, int k)
{
    // A 2D table where entry eggFloor[i][j] will represent minimum
    //   number of trials needed for i eggs and j floors. 
    int eggFloor[n+1][k+1];
    int res;
    int i, j, x;
 
    // We need one trial for one floor and 0 trials for 0 floors
    for (i = 1; i <= n; i++)
    {
        eggFloor[i][1] = 1;
        eggFloor[i][0] = 0;
    }
 
    // We always need j trials for one egg and j floors.
    for (j = 1; j <= k; j++)
        eggFloor[1][j] = j;
 
    // Fill rest of the entries in table using optimal substructure
    // property
    for (i = 2; i <= n; i++)
    {
        for (j = 2; j <= k; j++)
        {
            eggFloor[i][j] = Integer.MAX;
            for (x = 1; x <= j; x++)
            {
                res = 1 + Math.max(eggFloor[i-1][x-1], eggFloor[i][j-x]);
                if (res < eggFloor[i][j])
                    eggFloor[i][j] = res;
            }
        }
    }
 
    // eggFloor[n][k] holds the result
    return eggFloor[n][k];
}
 

Time Complexity: O(nk^2)
Auxiliary Space: O(nk)

Just for Fun

Refer here - http://datagenetics.com/blog/july22012/index.html, for the detailed data analysis and graph, which is really awesome. I have highlighted our case in blue color.

Here's a table showing the worst case number of drops it would take for a variety of floors with anywhere from 1 – 10 eggs.
 Eggs
 Building Height  1  2  3  4  5  6  7  8  9  10 
1 floor1111111111
2 floors2222222222
3 floors3222222222
4 floors4333333333
5 floors5333333333
6 floors6333333333
7 floors7433333333
8 floors8444444444
9 floors9444444444
10 floors10444444444
11 floors11544444444
12 floors12544444444
13 floors13544444444
14 floors14544444444
15 floors15554444444
16 floors16655555555
17 floors17655555555
18 floors18655555555
19 floors19655555555
20 floors20655555555
21 floors21655555555
22 floors22755555555
23 floors23755555555
24 floors24755555555
25 floors25755555555
30 floors30865555555
35 floors35866666666
40 floors40966666666
45 floors45976666666
50 floors501076666666
100 floors1001498777777
200 floors20020119888888
300 floors300241310999999
400 floors4002814111099999
500 floors50032151110109999
1,000 floors1000451913111111101010


 Hope you enjoyed.

Reference :

0 comments:

Post a Comment