Generalized puzzle with two eggs

Question

Here is a description of the problem:

Suppose we want to know which stories in an N-story building are safe to throw eggs, and because of which the eggs will break when planted. We make several assumptions: An egg that survives after a fall can be reused.

• A broken egg must be discarded.
• The drop effect is the same for all eggs.
• If an egg breaks when removed, it will break if it falls out of a higher window.
• If the egg survives in the fall, it will withstand a shorter fall.
• It is possible that the windows of the first floor break eggs and do not exclude that the windows of the Nth floor do not cause the eggs to burst.

Given the creation of the N-floor and the supply of eggs d, find a strategy that minimizes (in the worst case) the number of experimental drops needed to determine the fault.

---

I saw and solved this problem for 2 eggs, where the answer is 14 for N = 100. I tried to understand the generalized solution from the wiki using DP, but I could not understand what they were trying to do. Tell us how they arrived at DP and how it works.

EDIT:

The repetition given in this article for the highest level 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 repetition is excellent, but I can’t understand how it turns out?

I don’t understand the explanation .... I just want someone to explain this repetition to me in clearer words.

Answer 1

(1) Consider the case when the first drop breaks an egg. Then you can define a partition if and only if it is not greater than f [d-1, e-1]. Therefore, you cannot start more than f [d-1, e-1] + 1 (and should not start below, of course).

(2) If your first drop does not destroy the egg,, you are in the case f [d-1, e], only starting from the floor of your first drop + 1, instead of floor 1.

So, the best thing you can do is to start dropping eggs on the floor f [d-1, e-1] + 1 (due to (1)), and you can get up f [d-1, e] floors higher than that (due to (2)). it

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

Answer 2

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

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 available test eggs

k = number of (consecutive) floors to be tested

Below is my understanding.

We have k floors, n eggs, suppose we use an egg for testing in the x floor. There are only two possible outcomes:

• it breaks, so the problem recursively comes to: x-1 floors, n-1 eggs, which are reflected on W(n-1,x-1)
• it will not break, therefore the problem recursively comes to: kx floors, n eggs that are reflected on W(n,kx)

Since the problem requires the worst case, we need to choose a larger one to provide the worst case, so we add a maximum between W(n-1,x-1) and W(n,kx) .

In addition, since we only assumed that testing is on the x floor, x can be from 1 to k , in this situation we definitely need to choose the minimum to guarantee the minimum experimental drops to find out n , so we add the min between {max(W(n − 1, x − 1), W(n,k − x)): x = 1, 2, ..., k}

Finally, since we used 1 drop in x floor, so the equation should add 1 , which reflects the first part of the equation.

Hope that solves your puzzle :-)

Answer 3

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

I think this is self-evident. Please feel free to ask if any part is clear. We will be happy to explain

Answer 4

This problem can be solved by the following three approaches (what I know):

• Dynamic programming
• Binary Search Tree Solution
• The solution is by obtaining a direct mathematical formula for the maximum number of floors that can be checked or covered with a given number of eggs and a given number of drops

Let me first identify some of the characters that are used in the following analysis:

 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 principle of dynamic programming lies in the following recursive formula for Fmax:

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

And the essence for obtaining a direct mathematical formula for Fmax is the following recursive formula for Fmax:

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

An alternative solution using a binary search tree (BST) is also possible for this problem. To facilitate our analysis, we will make a BST with minor changes 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 a BST with this view, then the width of the BST represents the number of eggs.

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

Therefore, obtaining the optimal solution is equivalent to obtaining the location of nodes in the BST with a minimum height that falls under the restriction: the width of BST <= e

For more information on all of the above three approaches, check out my blog at: 3 Approaches to Solving the Generalized Ovipositor Problem

Answer 5

This problem is not higher, from which eggs should be thrown to the floor in order to minimize the number of drops.

• Suppose we have n eggs and k floors,
• Basic example:
  • When the word is 1, then MinNoOfDrops (n, 1) = 1
  • And when the egg is 1, MinNoOfDrops (1, k) = k
• Common decision:
• MinNoOfDrops (n, k) = 1 + min {max (MinNoOfDrops (n - 1, x - 1),
  MinNoOfDrops (n, k - x))}, x = 1, 2, ..., k

---

Dynamic Programming Algorithm:

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

• Basic case: when an egg is zero or one, set for floor i, table [0] [i] = 0; and table [1] [i] = i

• Base case: the floor is zero or one, then set the egg j, table [j] [0] = 0 and table [j] [1] = 1

• Iterate egg i from 2 to total_eggs

  • Mash gender j from 2 to total_floors
    • Set table [i] [j] = INFINITY
    • Iterate gender k from 1 to j
    • Set maxDrop = 1 + max (table [i-1] [k-1], table [i] [jk])
    • If the 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]; } }