Three egg proble​m

Question

I was just reading The Two Egg Problem:

The Two Egg Problem

You are given two eggs, and access to a 100-storey building. Both eggs are identical. The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.

If an egg breaks when dropped from floor n, then it would also have broken from any floor above that. If an egg survives a fall, then it will survive any fall shorter than that.

The question is: What strategy should you adopt to minimize the number egg drops it takes to find the solution?. (And what is the worst case for the number of drops it will take?)

I was following along until the "Look see I can do three" section. The author states that after the first egg breaks it degrades into the 2-egg problem and can be solved recursively.

That's great, but wouldn't we want to choose larger step-sizes when using 3 eggs instead of 2 (for the first egg)? From which floor do we throw the first egg?

With 1 egg, we have to start at floor 1.
With 2 eggs, we solve for n(n+1)/2=k and round up, where n is the starting floor, and k is the number of floors.
With 3... I'm having trouble coming up with a formula.

---

Thinking about this a bit more, with 2 eggs, the maximum number of drops is equal to the floor number that we drop our first egg from. For example, with 2 eggs and 100 floors, the solution is 14, which means we drop the first egg from floor 14, and if it breaks, we have to drop up to 13 more times, for floors 1-13.

With 3 eggs, the solution is 9 (as shown in the chart). But we wouldn't want to throw the first egg at floor 9, we can throw it higher, because we don't have to iterate by 1s in-between.

If we throw from floor 14 again, and it breaks, then we recurse. n(n+1)/2=k where k is now 13... but that gives us 4.815, if we ceil and that and add our previous drop we get 6, which is lower than the actual solution, so something here is wrong...

---

Solution 1

If we throw from floor 14 again, and it breaks, then we recurse. n(n+1)/2=k where k is now 13... but that gives us 4.815, if we ceil and that and add our previous drop we get 6, which is lower than the actual solution, so something here is wrong...

What if it doesn't break? Then you have a three-egg problem with 86 floors, which takes maybe one drop less to solve than the 100-floor problem.

Say you drop the first egg from the 50^th floor. If it breaks, you have a two-egg problem with 49 floors, which takes up to 10 additional drops. So that would give you a worst-case of 11 drops (since if it doesn't break, the 50-floor three-egg problem takes at most 7 additional drops).

If you choose the 37^th floor for the first drop, if it breaks, you have a 36-floor two-egg problem, needing up to 8 additional drops. If it doesn't break, you have a 63-floor three-egg problem left. You want to solve that problem with at most 8 drops, so if the next drop breaks the egg, the remaining two-egg problem should be solvable in at most 7 drops, thus the highest floor you can choose for the second drop is 37 + 28 + 1 = 66, since 28 floors is the highest you can solve with at most 7 drops and two eggs. If the egg doesn't break, you have a 34-floor three-egg problem with 7 drops left. The highest you can certainly solve with the remaining 6 drops if the egg breaks is 21 (6*7/2), so you can choose floor 66 + 21 + 1 = 88. If the egg doesn't break, you have 12 floors left with 6 drops, which is already doable with only two eggs.

Systematically, the highest number of floors you can certainly solve with d drops and e eggs is

          / 1, if d == 1
F(e,d) = |  d, if e == 1
          \ F(e-1,d-1) + 1 + F(e,d-1), if e > 1 and d > 1

If you have only one drop, you have no choice but to choose the lowest floor of which you do not yet know that the egg doesn't break. If that breaks it, and you tried a higher floor, you don't know the first floor to break the egg.

If you have only one egg, you have to check every floor in order until the egg breaks or you run out of drops.

Otherwise, if the first drop is from a floor higher than F(e-1,d-1) + 1, you possibly can't find the first breaking floor if the egg breaks. If the first drop is from a lower floor, you can't reach as high with d-1 drops if the egg doesn't break, so the first drop should be from floor F(e-1,d-1) + 1. If it breaks, you can solve with the remaining e-1 eggs and d-1 drops by assumption. If not, you can solve for the next F(e,d-1) floors with the remaining drops and eggs.

Conversely, to find how many drops you may need for f floors with e eggs, you have to find

D(e,f) = min { d | F(e,d) >= f }

You can find that by calculating the F(e,d) matrix, or you can use dynamic programming:

If you choose floor s for the first drop, if the egg breaks, you need up to D(e-1,s-1) drops to determine the floor. If the egg doesn't break, you need up to D(e,f-s) drops to determine the floor. So the worst case for choosing floor s for the first drop is

WC(s,e,f) = 1 + max { D(e-1,s-1), D(e,f-s) }

and the best of the worst case is

D(e,f) = minimum { WC(s,e,f) | 1 <= s <= f }

(where of course D(e,0) = 0).

Solution 2

This problem can be solved with following 3 approaches (that I 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 as follows:

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 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 (i.e. number of vertical columns in 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

Solution 3

This is the same answer that I provided at Egg Drop Printing Solutions. I am providing it here for anyone who wants to see the whole decision tree and reasoning laid out.

# This uses dynamic programming to find the basic information.
def optimal_solution(floors, eggs):
    # dp[drops][eggs] = max_floors
    dp = []

    # With no drops, we can do no floors
    dp.append([0 for x in range(eggs+1)])

    # With one drop and any eggs, we can do 1 floor
    one_drop = [1 for _ in range(eggs+1)]
    one_drop[0] = 0 # Except no eggs is still no floors
    dp.append(one_drop)

    # Keep adding drops until we have our answer
    # Note, in python array element -1 is shorthand for the end of the array.
    while dp[-1][eggs] < floors:
        # 0 floors for 0 eggs.  1 more for one egg
        next_drop = [0, dp[-1][1] + 1]
        for i in range(2, eggs+1): # Python for 2..eggs
            # The best we can do is drop at floor dp[-1][i-1].
            # If the egg breaks, we can find the answer using that solution.
            # If the egg holds, we can find another dp[-1][i] floors.
            next_drop.append(dp[-1][i] + dp[-1][i-1])
        dp.append(next_drop)

    return dp

# This turns that optimal solution into a decision tree.    
def dp_to_decision_tree(dp, floors, start_floor=None, eggs=None, drops=None):
    # Figure out defaults if needed.
    if start_floor is None:
        start_floor = 0
    if drops is None:
        drops = len(dp) - 1
    if eggs is None:
        eggs = len(dp[0]) - 1

    # Are we done?
    if floors == start_floor:
        return start_floor
    elif dp[drops][eggs] < floors - start_floor:
        return None

    # Do we need all of our drops?
    while floors - start_floor < dp[drops-1][eggs]:
        drops -= 1

    drop_at = start_floor + dp[drops-1][eggs-1]
    if eggs == 1:
        drop_at = start_floor + 1
    if floors < drop_at:
        drop_at = floors
    return [
        drop_at,
        dp_to_decision_tree(dp,  floors,     drop_at,   eggs, drops-1),
        dp_to_decision_tree(dp, drop_at-1, start_floor, eggs-1, drops-1),
        {'eggs': eggs, 'floor_range': (start_floor, floors)}
        ]

# This prints the decision tree in a human readable format.
def print_decision_tree(tree, indent="", label="start"):
    if tree is None:
        print(f"{indent}{label}: ?")
    elif isinstance(tree, int):
        print(f"{indent}{label}: {tree} found")
    else:
        print(f"{indent}{label}: {tree[0]} {tree[3]}")
        print_decision_tree(tree[1], indent + "    ", label="held")
        print_decision_tree(tree[2], indent + "    ", label="broke")

# And this calls the previous functions.
def print_optimal_decisions(floors, eggs):
    print_decision_tree(
        dp_to_decision_tree(
            optimal_solution(floors, eggs), floors))

# And now we can try it.
print_optimal_decisions(36, 3)

Solution 4

You can use simple dynamic programming solution. n - number of floors. k - number of eggs. D[n,k] = you answer (The number of minimum throws). D[j,1] = n-1 for each 1 <= j <= n.

The main idea for calculate D[n,k] for k>1:

D[n,k] = maximum 1 <= j <= n-1 { maximum{ D[j,k-1]+1, D[n-j,k]+1 }.

View more solutions

Comments

[Richard Sitze]

see stackoverflow.com/questions/4699067/…

[mpen]

@RolazaroAzeveires The description is at the bottom of my question, no?

[Ogen]

Is there a way to find out which floors in particular to drop from? Given that I have all the information, including the number of eggs, the number of drops, and the number of floors.

[Rushikesh]

It is a mathematical challenge to come up with formula for Fmax(e, n).

[Rushikesh]

where both e and n are variables.

[Jim]

@DanielFischer: if it doesn't break, the 50-floor three-egg problem takes at most 7 additional drops I think it takes at most 5. 1st drop from the 50th floor, 2nd drop from the 96th floor and if it does not break in the 2nd drop we have 4 floors left with 3 eggs that can be solved within at most 3 drops for a total of 5

[Daniel Fischer]

@Jim I don't remember whether the 7 was sharp or not, but the only thing that matters at that point of the argument is that the number is not larger than the worst-case for the two-egg problem you get when the first egg dropped breaks. As for your strategy, it's fine when the second egg doesn't break, but what if it breaks? Then you have a two-egg problem with 45 floors.

[Jim]

@DanielFischer: I mentioned that mainly to make sure I understood fully your excellent answer. By calculating the F(e,d) matrix, or you can use dynamic programming. Why do you make a distinction between the matrix and DP? Isn't the DP exactly building that F(e,d) matrix?

[Jim]

@DanielFischer: Is your last formula using WC(s,e,f) meant for the recursive algorithm implementation?

[Daniel Fischer]

@Jim I'm not sure whether computing the matrix counts as DP. I think it doesn't really match the description, but it's open to interpretation. Anyhow, the part after the "or you can use DP:" is a description of my suggested DP algorithm. Yes, the stuff with WC is for the recursive algorithm. Of course you don't need to compute WC(s,e,f) for all 1 <= s <= f (that would be inefficient), the minimum occurs where D(e-1,s-1) - D(e, f-s) changes sign (since D(e-1,s-1) grows with s, and D(e,f-s) decreases for growing s, ...

[Daniel Fischer]

... you know that the optimal s cannot be larger when D(e-1,s-1) >= D(e,f-s), and it cannot be smaller when D(e-1,s-1) <= D(e,f-s)). You can find the optimal s (for given e and f) quickly by binary search (but a skewed search is a little faster; how much to skew depends on e, the more eggs you have, the smaller the skew should be).

[Jim]

@DanielFischer: I tried to create the code based on your answer here: pastebin.com/zpV30JVa The number of drops is correct but the first breaking floor is wrong. Unless I misunderstood your algorithm, the answer should not be the minimum { WC(s,e,f) | 1 <= s <= f } because we are trying to find a floor that distributes the breaks evenly right? So the worse case is the same across all cases which this does not be achieved this way. Could you please check the code in the pastebin? I wasn't sure how to initialize the cache so I used a large number (200).

[Jim]

@DanielFischer: Also I am not sure at which part to apply the binary search and the range

[Daniel Fischer]

@Jim The F array and the WC are parts of different algorithms. Also, we cannot determine the floor at which the egg breaks, so getFirstBreakingFloor is at least misleadingly named (might it be getFirstDroppingFloor, to find the floor from which we first drop an egg?). And I don't understand how getMinimumEggDrops is meant to work. I would implement that as for(int i = 1; i <= floors; ++i) { if (getNumberFloors(eggs, i) >= floors) return i; } throw new WTFException(); (omitting sanity checks for the arguments and early returns e.g. for floors <= 0).

[Daniel Fischer]

Now to the algorithm with WC. That too is intended to find the number of drops we might need to find the first breaking floor (if any), but it can also be used to find out from which floor to drop the first egg (there can be more than one option), which your getFirstBreakingFloor would do (it would return the lowest starting floor leading to the smallest overall number of drops) if getMinimumEggDrops worked correctly. Let's first suppose you want to determine the floor from which to drop the first egg (assuming you have more than one egg) and you have a correct getMinimumEggDrops

[Daniel Fischer]

(which I'll call drops for shortness). First set lo = 1; hi = f;, and s_min = s = (lo + hi)/2. Then let b = drops(e-1,s-1); nb = drops(e,f-s); wc = 1 + max(b,nb);. If b == nb you have found an optimal starting floor. If b > nb, no higher starting floor can do better, so set hi = s-1;, and if b < nb no lower starting floor can be better, so set lo = s+1. Then s = (lo + hi)/2; b = drops(e-1,s-1); nb = drops(e,f-s); wc1 = 1 + max(b,nb);, if wc1 < wc, then set wc = wc1; s_min = s. repeat until b == nb or lo == hi (either means you have found an optimal starting floor).

[Daniel Fischer]

That's the binary search. Of course, as always, be careful with edge conditions. To use the WC to implement drops, make a cache for the case of more than one egg and more than one floor, and have the trivial returns of 0 for zero floors, 1 for one floor, floors for one egg (and throw for no egg). Then do the binary WC-search (within drops) to find an optimal starting point, but instead of returning s_min as above, store wc in the cache (for the given eggs and floors) and return wc. That gets a recursive memoised drops.

[Jim]

@DanielFischer: Yes the name for the getFirstBreakingFloor is wrong. This is meant to be the implementation of F(e,d) that you have defined. The getMinimuEggDrops initially tries to create the F(e,d) array (loop to 200) and then tries to find the drops based on the floors i.e. it was an attempt at D(e,f) = min { d | F(e,d) >= f } which apparently I messed up. Here are the changes after your review: pastebin.com/QA4wgGfs I still get the wrong result though so I am still messing up somewhere.

[Jim]

@DanielFischer: I didn't understand your last comment To use the WC to implement drops. Why would that be required? Isn't the function returning the min drops as is now? I am confused a bit on if WC is an alternative approach or not. Also what does b and nb as names stand for?

[Jim]

@DanielFischer: I also moved the if statement here in the binary search (check for b == nb and break) pastebin.com/U6B71YPQ

[Jim]

@DanielFischer: I expected System.out.println(getFirstDroppingFloor(2, 36)); to print 8 as is the only floor that has guaranteed worse case so should be the solution to the problem or 14 due to the reasoning in datagenetics.com/blog/july22012/index.html which is the original article the original post was referring. I am not sure why 9 is reported unless I have a bug there

[Jim]

@DanielFischer: I guess I am confused. The best worse case should be the one that has the better distribution?

[Bubesh p]

@Ogen, did you find the answer for your question? Is there a way to find out which floors in particular to drop from? Given that I have all the information, including the number of eggs, the number of drops, and the number of floors.

[Ogen]

@Bubeshp No sorry I didn't