Make delicious recipes!

Egg-dropping Puzzle

Given 2 eggs and 100 floors such that eggs always break if dropped from floors above a particular floor, find that particular floor in minimum number of egg droppings.


If we had only 1 egg, then it would need to be dropped 100 times.

But with 2 eggs, some optimization can be done.

Example: Let's say we drop one egg from floor 50.

If it breaks, we are left with 1 egg and 50 floors and we have to try 50 times.

If it does not break, we can drop the same egg from floor 75 and recurse on same logic.


Note that the starting floor ‘k’ (from where we begin recursion) should have worst case order of ‘k’ if the egg breaks and some other order ‘g’ (determined by higher floors’ dropping strategy) if the egg does not break.


Minimum droppings would be obtained when ‘k’ and ‘g’ would be equal else it would be greater of ‘k’ and ‘g’


If we begin dropping from floor ‘k’ and egg breaks, then max droppings needed = 1 + (k-1) = k

If egg does not break, then max droppings for 100-k floors should also be k if we want minimum no of droppings.


Suppose after floor ‘k’, we choose floor ‘x’ to test first egg again.

If egg breaks here, then max droppings needed = 1 + (x-k)

This quantity should also be equal to k

k = 1 + x-k

=> x = 2k-1 i.e. k-1 floors above floor k


This implies, that for minimum droppings, egg should be dropped after ‘k’ floors, then ‘k-1’ floors, then ‘k-2’ floors and so on.

The sum of this series should equal 100 and last entry in this series should be 1

=> k + (k-1) + (k-2) ... + 1 = 100

=> k(k+1)/2 = 100

=> k2 + k - 200 = 0;


Solving the above, k = (-1 + (1 - 4x(-200))0.5)/2

= (8010.5 - 1)/2

= 2000.5 - 0.5

= 14.1 - 0.5

= 13.6 which is 14 floors rounded off

Hence, we should begin from floor 14, then move to 14+13=27, then 27+12=39 and so on.

Max no of droppings required = 14


For 3 eggs, the starting floor can be increased beyond 14 because we know
that even if the egg breaks on this floor, we still have two eggs for the remaining below floors.

Increasing the starting floor is helpful even if the egg does not break on this starting floor, because
then the number of remaining floors above will be lesser.


Programatically, every floor presents us with 2 choices: egg breaks and egg does not break.

If egg breaks, then we are left with 1 less egg and k-1 floors.

If egg does not break, then we are left with 2 eggs and 100-k floors.

Maximum among these 2 choices is the no of droppings required if we begin at that floor.


So, we can find max droppings on each floor and find minimum among them to arrive programatically at our answer.

Interestingly, this approach works well for any number of eggs.

int maxDroppingsRequired (int numEggs, int numFloors)
{
    // With just one egg, we have to test each floor
    if (numEggs == 1)
        return numFloors;

    // For very few floors too, every floor has to be tested
    if (numFloors <= 2)
        return numFloors;

    int minDroppings = -1;
    int floorForMinDroppings = -1;
    for (int floorK=1; floorK < numFloors; floorK++)
    {
        int maxDroppingsBelow = maxDroppingsRequired(numEggs-1, floorK-1); // egg broke at floorK
        int maxDroppingsAbove = maxDroppingsRequired(numEggs, numFloors-floorK); // egg did not break at floorK

        // We have to choose the worst of the cases becuase we do not know
        // whether the egg will break or not
        int maxDroppingsAtFloorK = Math.max(maxDroppingsBelow, maxDroppingsAbove);

        // But we have the freedom to choose that floor for which the above worse-case number is minimum
        if (minDroppings == -1 || minDroppings > maxDroppingsAtFloorK)
        {
            minDroppings = maxDroppingsAtFloorK;
            floorForMinDroppings = floorK;
        }
    }
    // Add 1 because whatever floor we choose, one egg must be dropped on that floor
    return minDroppings + 1;
}

It's easy to spot in the above that it is very much suited to dynamic programming.

Lookup table can be made between number of eggs and number of floors.


Dynamic Programming Solution

int maxDropsRequiredDP(int numEggs, int numFloors)
{
    int lookup[][] = new int[numEggs+1][numFloors+1];

    // For a single egg, Drops required = numFloors
    for (int floorsK=0; floorsK<=numFloors; floorsK++)
    {
        lookup[1][floorsK] = floorsK;
    }

    // For 0, 1 and 2 floors, no of Drops is fixed as well
    // regardless of the number of eggs
    for (int eggsK=1; eggsK<=numEggs; eggsK++)
    {
        lookup[eggsK][0] = 0; // For 0 floors, 0 Drops
        lookup[eggsK][1] = 1; // For 1 floor, 1 Drop
        lookup[eggsK][2] = 2; // For 2 floors, 2 Drops
    }

    for (int eggsK=2; eggsK<=numEggs; eggsK++)
    {
        for (int floorsK=3; floorsK<=numFloors; floorsK++)
        {
            int minDrops = -1;
            for (int x=1; x<=floorsK; x++)
            {
                int maxDropsAtFloorK = 1 + Math.max(
                        lookup[eggsK-1][x-1],
                        lookup[eggsK][floorsK-x]
                    );
                if (minDrops == -1 || minDrops > maxDropsAtFloorK)  
                {
                    minDrops = maxDropsAtFloorK;
                    lookup[eggsK][floorsK] = minDrops;
                }
            }
        }
        printLookup (lookup);
    }
    return lookup[numEggs][numFloors];
}

void printLookup(int[][] lookup)
{
    System.out.println ();
    for (int i=0; i<lookup.length; i++)
    {
        for (int j=0; j<lookup[i].length; j++)
        {
            System.out.print (String.format("%3d", lookup[i][j]));
        }
        System.out.println();
    }
}
numEggs = 7, numFloors = 30

Lookup for 2 eggs:
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
  0  1  2  2  3  3  3  4  4  4  4  5  5  5  5  5  6  6  6  6  6  6  7  7  7  7  7  7  7  8  8
  0  1  2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  1  2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  1  2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  1  2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  1  2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0

Lookup for 3 eggs:
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
  0  1  2  2  3  3  3  4  4  4  4  5  5  5  5  5  6  6  6  6  6  6  7  7  7  7  7  7  7  8  8
  0  1  2  2  3  3  3  3  4  4  4  4  4  4  4  5  5  5  5  5  5  5  5  5  5  5  6  6  6  6  6
  0  1  2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  1  2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  1  2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  1  2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0

Lookup for 4 eggs:
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
  0  1  2  2  3  3  3  4  4  4  4  5  5  5  5  5  6  6  6  6  6  6  7  7  7  7  7  7  7  8  8
  0  1  2  2  3  3  3  3  4  4  4  4  4  4  4  5  5  5  5  5  5  5  5  5  5  5  6  6  6  6  6
  0  1  2  2  3  3  3  3  4  4  4  4  4  4  4  4  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
  0  1  2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  1  2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  1  2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0

Lookup for 5 eggs:
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
  0  1  2  2  3  3  3  4  4  4  4  5  5  5  5  5  6  6  6  6  6  6  7  7  7  7  7  7  7  8  8
  0  1  2  2  3  3  3  3  4  4  4  4  4  4  4  5  5  5  5  5  5  5  5  5  5  5  6  6  6  6  6
  0  1  2  2  3  3  3  3  4  4  4  4  4  4  4  4  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
  0  1  2  2  3  3  3  3  4  4  4  4  4  4  4  4  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
  0  1  2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  1  2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0

Lookup for 6 eggs:
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
  0  1  2  2  3  3  3  4  4  4  4  5  5  5  5  5  6  6  6  6  6  6  7  7  7  7  7  7  7  8  8
  0  1  2  2  3  3  3  3  4  4  4  4  4  4  4  5  5  5  5  5  5  5  5  5  5  5  6  6  6  6  6
  0  1  2  2  3  3  3  3  4  4  4  4  4  4  4  4  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
  0  1  2  2  3  3  3  3  4  4  4  4  4  4  4  4  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
  0  1  2  2  3  3  3  3  4  4  4  4  4  4  4  4  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
  0  1  2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0

Lookup for 7 eggs:
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
  0  1  2  2  3  3  3  4  4  4  4  5  5  5  5  5  6  6  6  6  6  6  7  7  7  7  7  7  7  8  8
  0  1  2  2  3  3  3  3  4  4  4  4  4  4  4  5  5  5  5  5  5  5  5  5  5  5  6  6  6  6  6
  0  1  2  2  3  3  3  3  4  4  4  4  4  4  4  4  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
  0  1  2  2  3  3  3  3  4  4  4  4  4  4  4  4  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
  0  1  2  2  3  3  3  3  4  4  4  4  4  4  4  4  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
  0  1  2  2  3  3  3  3  4  4  4  4  4  4  4  4  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5


Minimum-Droppings for 7 eggs and 30 floors = 5



One of the most important things to note above is that there are a total of 3 loops, one iterating on eggs and other 2 loops iterating on floors.

The innermost loops is required to find minDrops for floorK

To find minDrops for any floor, we have to find maxDrops on all it's lower floors and choose minimum among them.

So outer 2 loops find min-Drops for all eggs and all floors, while the innermost loop has to find maxDrops on each floor so that we can choose minimum among them.


The above solution used tabulation approach.

However, memoization solution is much easier to visualize as it mimics the recursive solution very closely (by just saving result in lookup table at the end of each recursive call and using this lookup table before beginning recursion).

Memoization solution is as follows:





Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal