Generalised Two-Egg Puzzle

问题:

Here is the Problem Description :

Suppose that we wish to know which stories in a N-story building are safe to drop eggs from, and which will cause the eggs to break on landing. We make a few assumptions: 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 window.
• 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 Nth-floor windows do not cause an egg to break.

Given an N story building and a supply of d eggs, find the strategy which minimizes (in the worst case) the number of experimental drops required to determine the breakfloor.

---

I have seen and solved this problem for 2 eggs where answer comes out to be 14 for N=100. I tried to understand the generalized solution from wiki using DP but couldn't Understand what are they trying to do. Please tell how they arrived at the DP and how it is working ?

EDIT :

The Recurrence given in this Article for the The highest floor that can be tested with d drops and e eggs is as follows :

f[d,e] = f[d-1,e] + f[d-1,e-1] + 1

The recurrence is fine but i not able to understand how it is derived ?

The explanation is not clear to me....i just want someone to explain this recurrence to me in more clear words.

回答1:

(1) Consider the case that the first drop breaks the egg. Then you can determine the breakfloor if and only if it is at most f[d-1, e-1]. Therefore you can't start higher than f[d-1, e-1] + 1 (and shouldn't start lower, of course).

(2) If your first drop doesn't breaks the egg, you are in the case of f[d-1, e], just starting at the floor of your first drop + 1, instead of floor 1.

So, the best you can do is to start dropping eggs at floor f[d-1, e-1] + 1 (because of (1)), and you can get up to f[d-1, e] floors higher than that (because of (2)). That's

f[d, e] = f[d-1, e-1] + 1 + f[d-1, e]

回答2:

From Wiki Egg Dropping puzzle we know that the the state transfer equation is:

W(n,k) = 1 + min{ max(W(n − 1, x − 1), W(n,k − x)) } , x = 1, 2, ..., k

W(n,1)=1, W(1,k)=k

n = number of test eggs available

k = number of (consecutive) floors yet to be tested

Below is my understanding.

We have k floors, n eggs, assume we use an egg to test in x floor. there are only two possible results:

1. it breaks, so the problem recursively come to: x-1 floors, n-1 eggs, which reflects to W(n-1,x-1)
2. it doesn't break, so the problem recursively come to: k-x floors, n eggs, which reflects to W(n,k-x)

Since the problem requires the worst case, we have to choose the bigger one to ensure the worst case works, that's why we add an max between W(n-1,x-1) and W(n,k-x).

Besides, as we just assumed testing in x floor, x can be from 1 to k, in this situation, we definitely need to choose the minimum to ensure the min experimental drops to find out N, that's why we add an min between {max(W(n − 1, x − 1), W(n,k − x)): x = 1, 2, ..., k}

Finally, as we have used 1 drop in x floor, so the equation must add 1, which reflects to the first part of the equation.

Hope that solves your puzzle :-)

回答3:

dynamic programming based solution available here - http://algohub.blogspot.in/2014/05/egg-drop-puzzle.html

I believe it is self-explanatory..please feel free to ask if any part is not clear..will be happy to explain

回答4:

This problem can be solved with following 3 approaches (that I am know) :

1. Dynamic Programming
2. Solution using Binary Search Tree
3. Solution by obtaining the direct mathematical formula for maximum number of floors that can be tested or covered with given number of eggs and given number of drops

Let me first define some symbols that are used in analysis done afterwards :

e = number of eggs
f = number of floors in building
n = number of egg drops 
Fmax(e, n) = maximum number of floors that can be tested or covered with e eggs and n drops

The crux for dynamic programming approach lies in following recursive formula for Fmax:

Fmax(e, n) = 1 + Fmax(e-1, n-1) + fmax(e, n-1)

And the crux for obtaining the direct mathematical formula for Fmax lies in following recursive formula for Fmax:

Fmax(e, n) = { ∑Fmax(e-1,i) for i = 1 to n } - Fmax(e-1, n) + n 

Alternative solution using Binary Search Tree (BST) is also possible for this problem. In order to facilitate our analysis, let us draw BST with slight modifications as follows:

1.    If egg breaks then child node is drawn on left down side
2.    If egg does not break then child node is drawn straight down side

If we draw BST with above kind of representation then width of the BST represents the number of eggs.

Any BST with f number of nodes, drawn with above kind of representation and subjected to the constraint width of BST <= e (number of eggs) is a solution but it may not be the optimal solution.

Hence obtaining the optimal solution is equivalent to obtaining the arrangement of nodes in BST with minimum height subjected to the constraint: width of BST <= e

For more details about all the above 3 approaches, check my blog at: 3 approaches for solving generalized egg drop problem

回答5:

This problem is not above from which floor eggs should be dropped, its about to minimize number of drops.

• Suppose, we have n eggs and k floors then,
• Base Case:
  • When floor is 1 then, MinNoOfDrops(n, 1)=1
  • And when egg is 1 the, MinNoOfDrops(1, k)=k
• Generailsed Solution:
• MinNoOfDrops(n, k) = 1 + min{ max(MinNoOfDrops(n − 1, x − 1),
  MinNoOfDrops(n,k − x)) } , x = 1, 2, ..., k

---

Dynamic Programming Algorithm:

• Create dp table of (totalEggs + 1) X (totalFloors + 1)

• Base Case: When egg is zero or one then, set for floor i, table[0][i] = 0; and table[1][i] = i

• Base Case: Floor is zero or one then, set for egg j, table[j][0] = 0 and table[j][1] = 1

• Iterate egg i from 2 to total_eggs

  • Iterate floor j from 2 to total_floors
    • Set table[i][j] = INFINITY
    • Iterate floor k from 1 to j
    • Set maxDrop = 1 + max(table[i-1][k-1], table[i][j-k])
    • If table[i][j] > maxDrop then
      • Set table[i][j] = maxDrop

---

public class EggDroppingPuzzle {

    /** Not efficient  **/
    public static int solveByRecursion(int totalEggs, int totalFloors) {

        /** Base Case: When no floor **/
        if (totalFloors == 0) {
            return 0;
        }

        /** Base case: When only one floor **/
        if (totalFloors == 1) {
            return 1;
        }

        /** Base case: When only one eggs, then we have to try it from all floors **/
        if (totalEggs == 1) {
            return totalFloors;
        }

        int minimumDrops = Integer.MAX_VALUE;
        /** Now drop a egg from floor 1 to totalFloors **/
        for (int k = 1; k <= totalFloors; k++) {

            /** When an egg breaks at kth floor **/
            int totalDropWhenEggBreaks = solveByRecursion(totalEggs - 1, k - 1);

            /** When egg doesn't break at kth floor **/
            int totalDropWhenEggNotBreaks = solveByRecursion(totalEggs, totalFloors - k);

            /** Worst between above conditions **/
            int maxDrop = Math.max(totalDropWhenEggBreaks, totalDropWhenEggNotBreaks);


            /** Minimum drops for all floors **/
            if (minimumDrops > maxDrop) {
                minimumDrops = maxDrop;
            }
        }

        return minimumDrops + 1;
    }

    public static int solveByByDP(int totalEggs, int totalFloors) {
        int[][] table = new int[totalEggs + 1][totalFloors + 1];

        /** Base Case: When egg is zero or one **/
        for (int i = 0; i < totalFloors + 1; i++) {
            table[0][i] = 0;
            table[1][i] = i;
        }

        /** Base case: Floor is zero or one **/
        for (int j = 0; j < totalEggs + 1; j++) {
            table[j][0] = 0;
            table[j][1] = 1;
        }

        /** For floor more than 1 and eggs are also more than 1 **/
        for (int i = 2; i < totalEggs + 1; i++) {
            for (int j = 2; j < totalFloors + 1; j++) {

                table[i][j] = Integer.MAX_VALUE;
                for (int k = 1; k <= j; k++) {

                    /** When an egg breaks at kth floor **/
                    int totalDropWhenEggBreaks = table[i - 1][k - 1];

                    /** When egg doesn't break at kth floor **/
                    int totalDropWhenEggNotBreaks = table[i][j - k];

                    /** Worst between above conditions **/
                    int maxDrop = 1 + Math.max(totalDropWhenEggBreaks, totalDropWhenEggNotBreaks);

                    /** Minimum drops for all floors **/
                    if (maxDrop < table[i][j]) {
                        table[i][j] = maxDrop;
                    }
                }
            }
        }

        return table[totalEggs][totalFloors];
    }
}