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 floor	1	1	1	1	1	1	1	1	1	1
2 floors	2	2	2	2	2	2	2	2	2	2
3 floors	3	2	2	2	2	2	2	2	2	2
4 floors	4	3	3	3	3	3	3	3	3	3
5 floors	5	3	3	3	3	3	3	3	3	3
6 floors	6	3	3	3	3	3	3	3	3	3
7 floors	7	4	3	3	3	3	3	3	3	3
8 floors	8	4	4	4	4	4	4	4	4	4
9 floors	9	4	4	4	4	4	4	4	4	4
10 floors	10	4	4	4	4	4	4	4	4	4
11 floors	11	5	4	4	4	4	4	4	4	4
12 floors	12	5	4	4	4	4	4	4	4	4
13 floors	13	5	4	4	4	4	4	4	4	4
14 floors	14	5	4	4	4	4	4	4	4	4
15 floors	15	5	5	4	4	4	4	4	4	4
16 floors	16	6	5	5	5	5	5	5	5	5
17 floors	17	6	5	5	5	5	5	5	5	5
18 floors	18	6	5	5	5	5	5	5	5	5
19 floors	19	6	5	5	5	5	5	5	5	5
20 floors	20	6	5	5	5	5	5	5	5	5
21 floors	21	6	5	5	5	5	5	5	5	5
22 floors	22	7	5	5	5	5	5	5	5	5
23 floors	23	7	5	5	5	5	5	5	5	5
24 floors	24	7	5	5	5	5	5	5	5	5
25 floors	25	7	5	5	5	5	5	5	5	5
30 floors	30	8	6	5	5	5	5	5	5	5
35 floors	35	8	6	6	6	6	6	6	6	6
40 floors	40	9	6	6	6	6	6	6	6	6
45 floors	45	9	7	6	6	6	6	6	6	6
50 floors	50	10	7	6	6	6	6	6	6	6
100 floors	100	14	9	8	7	7	7	7	7	7
200 floors	200	20	11	9	8	8	8	8	8	8
300 floors	300	24	13	10	9	9	9	9	9	9
400 floors	400	28	14	11	10	9	9	9	9	9
500 floors	500	32	15	11	10	10	9	9	9	9
1,000 floors	1000	45	19	13	11	11	11	10	10	10

 Hope you enjoyed.

Reference :

• http://tianrunhe.wordpress.com/2012/03/12/drop-egg-to-find-the-threshold-for-breaking/
• http://www.geeksforgeeks.org/dynamic-programming-set-11-egg-dropping-puzzle/