Understanding Egg Drop Algorithm for more than two eggs.

Question

http://datagenetics.com/blog/july22012/index.html

I am using the mentioned link to understand the eggdrop problem. I have also looked at code online which I understand to decent extent (the recursion is a bit confusing) but I can't seem to understand a few main things about this egg drop problem.

Suppose we have 100 floors

• For 2 eggs we say we start at 14 and then go to 14 + (14-1). I understand why we do this to keep the worse case time uniform and all. However, where will we start for three eggs? The formula shows that 3 eggs will have a max of 9 tries in the worst case. Obviously we don't start from 9 because going 9 + ( 9 - 1 ) doesn't give us a consisten 9 trials across 100 so where do we start for 3? Not only that but how do we figure this out?

• It seems like for 3 eggs, we run a few trials until the problem degenerates into 2 eggs and x amount of floors. Conceptually this makes sense but I don't understand how to visualize or implement this

• I have to find the sequence of tries in a worst case scenario and implement it which is why I want to visualize the tries.

I hope this is clear. It is the first bullet of mine that is my main issue. Please let me know if I'm missing out any info and I'll edit it.

Answer 1

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 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