**The Egg Problem**

### An Interview Question Examined.

We have a building defined in terms of height in floors, or ‘H’. This building has a special floor ‘N’ where 0 <= N <= H. We also have two eggs. These eggs have a special property, where if they are dropped out the window of any floor, they will break if the floor is is greater than or equal to N. Once an egg is broken, they can no longer be used for this dropping experiment. How do we find N in the least amount of drops?

### Relevance

I read this question somewhere online maybe 4 months ago. I casually thought about it, came up with a vague idea of a solution and moved on. However, recently I stumbled upon this article which presents a slightly different version of the same problem. This article claimed this was one of the top questions interviewers at Apple gave to engineering interviewees. Well this piqued my interest. Since then, like all good puzzles, has been stuck in my head. I was thinking about it in the shower, before I fell asleep, and while driving. So let’s see if we can’t make some progress on finding this answer.

### General Solution

All the solutions I could come up with all fell into the same general pattern:

- Drop an egg from a test point at some floor ‘X’.
- If the drop at X did not cause a break, we have eliminated floors 0 – X. Drop another Egg any floor from X to H. This is our new X.
- If the drop at X caused a break, move to next step.
- Start dropping eggs floor by floor starting at ‘Y’, where Y is either 0, or the last X that did not cause an egg break.
- The next broken egg will occur at floor N.

### Choosing Our Drop Point

Since the height of our building is variable, it makes sense to define our X in terms of H. Let X = H / F, where F is an arbitrary integer Consider a building where H=100 and our F is 10. X = 10, or 100/10. Consider a building where H=1000 and our F=5. X = 200, or 1000/5. Note that we are only considering integer division so that we don’t end up with an answer that is not a valid floor. In my code below I refer to this as ‘factor’.

This is where things get tricky. Our number of drops is a function of N and F. Consider a building where H=100, and F=20. If our N=1, our algorithm finds the floor in 3 drops. A drop at floor 5 where the first egg breaks, a drop at floor 0 where the egg doesn’t break, and another at floor 1, where our egg breaks and we are confident that N=1. Keep in mind, I’m thinking in terms of indexing, where the first floor in our building is 0, and the highest floor is (H-1).

Consider the same building where N = 99. We have to drop our egg 20 times before the first break. and another 5 times before our egg breaks again for floors 95 – 99. This demonstrates how our algorithm performs very efficiently for certain values of N, and not as efficiently for others.

This also points out a deficiency in our algorithm. If the egg breaks on the first drop, we have to check floor 0. If the egg breaks at another value, we don’t have the check the last floor where we last performed a drop with no break. Let’s make note of this for our implementation.to

In any case, if we’re going to judge the efficiency of this algorithm for different values of F, it is logical to assume that we have to test it for *all* values of N. That way, we can objectively say that if we don’t know the value of N, a certain value of F is the best for the task.

Implementation

The only elements of our building concept that we are concerned with are H or height, and N for our special floor. This lends itself to a very simple minimal class:

1 2 3 4 |
class Building(): def __init__(self, h, n): self.H = h self.N = n |

### My Python Algorithm for Finding N

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 |
def findN(self, factor, bld): final_count = 0 # Eliminates need for multiple returns drop_count = 0 # Stores drops as we go x = 0 # Increases by factor, marks our test drops y = 0 # Equals 0 or last unbroken egg drop at x for i in range(bld.H): x += factor if x > bld.H: # Just in case we overshot H x = bld.H drop_count += 1 if x >= bld.N: # Our first egg broke. (y <= N <= x) while y < bld.N: if y == 0 and bld.N == 0: # Handles N=0 Case final_count = 2 y += 1 drop_count += 1 if y >= bld.N or (y+1) == x: # Egg is broken. We found N. # y+1 = x code implies that N=x final_count = drop_count else: # Our egg is intact. Set y to x and test again y = x return final_count |

Next we need a system for testing our algorithms. I created a separate class to handle this:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Dropper: def __init__(self): self.FACTORS = range(5,75)[::5] #Edit to test different ranges. self.RESULTS = [0]*len(self.FACTORS) self.TEST_HEIGHT = 100 # Edit to test different buildings # ... see definition of findN() above ... def run(self): # 'i' equals floor number for i in range(self.TEST_HEIGHT): bld = Building(self.TEST_HEIGHT, i) # 'j' represents every different factor in our list for j in range(len(self.FACTORS)): # the '//' operator preserves integer division. drops = self.findN((self.TEST_HEIGHT // self.FACTORS[j]), bld) self.RESULTS[j] += drops self.average_results() self.present_results() |

Now all we need to do is call the
run() method on a `Dropper`

object.

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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
Results Results of building H = 50: Factor 5: Drop Average 8 Factor 10: Drop Average 8 Factor 15: Drop Average 10 Factor 20: Drop Average 13 Factor 25: Drop Average 13 Factor 30: Drop Average 25 Factor 35: Drop Average 25 Factor 40: Drop Average 25 Factor 45: Drop Average 25 Factor 50: Drop Average 25 Results of building H = 100: Factor 5: Drop Average 13 Factor 10: Drop Average 10 Factor 15: Drop Average 11 Factor 20: Drop Average 13 Factor 25: Drop Average 14 Factor 30: Drop Average 18 Factor 35: Drop Average 26 Factor 40: Drop Average 26 Factor 45: Drop Average 26 Factor 50: Drop Average 26 Factor 55: Drop Average 50 Factor 60: Drop Average 50 Factor 65: Drop Average 50 Factor 70: Drop Average 50 Results of building H = 500: Factor 5: Drop Average 53 Factor 10: Drop Average 30 Factor 15: Drop Average 24 Factor 20: Drop Average 23 Factor 25: Drop Average 23 Factor 30: Drop Average 24 Factor 35: Drop Average 25 Factor 40: Drop Average 27 Factor 45: Drop Average 29 Factor 50: Drop Average 30 Factor 55: Drop Average 33 Factor 60: Drop Average 35 Factor 65: Drop Average 39 Factor 70: Drop Average 39 Results of building H = 1000: Factor 5: Drop Average 103 Factor 10: Drop Average 55 Factor 15: Drop Average 41 Factor 20: Drop Average 35 Factor 25: Drop Average 33 Factor 30: Drop Average 32 Factor 35: Drop Average 32 Factor 40: Drop Average 33 Factor 45: Drop Average 34 Factor 50: Drop Average 35 Factor 55: Drop Average 37 Factor 60: Drop Average 40 Factor 65: Drop Average 41 Factor 70: Drop Average 43 |

### Deficiencies in Our Model

The first drawback to our model is our test values for F. I chose these somewhat haphazardly. There is probably a more mathematical way to selecting these, but for the moment, we’ll stick with these.

The next deficiency is the fact that we’re only testing values of F in a linear way. Consider a building of H=100 and our F=10. Say for example we decide to determine F as a fraction of either the distance from the last unbroken egg drop or zero to H. In this scenario our first drop still occurs at floor 10. The next drop would occur at floor 19. This occurs because H – 10 = 90. 90 / F = 9. 9 + 10 = 19. It is also very possible that having a varying value of F as the algorithm unfolds would be very helpful. Again, there is probably a very mathematical way of determining the best possible method for varying F as we go, but that is beyond my skill level…at the moment anyway.

Conclusions and Next Steps

The results vary greatly as H changes. This makes sense because as our H increases, the small differences between our values of F become more significant due to rounding. It would be a fun experiment to create a system for evaluating this data again and produce visualizations for the data where we can see the value of each factors change as H increases.

However, let’s assume H is 100 always. Then we can at least be pretty confident that our program can get us pretty close to the right answer. For fun, let’s try this again with values of F specifically chosen for the H=100 scenario and see what we get.

1 2 3 4 5 6 7 8 9 10 11 |
Results of building H = 100: Factor 2: Drop Average 26 Factor 4: Drop Average 15 Factor 6: Drop Average 11 Factor 8: Drop Average 10 Factor 10: Drop Average 10 Factor 12: Drop Average 10 Factor 14: Drop Average 11 Factor 16: Drop Average 11 Factor 18: Drop Average 13 Factor 20: Drop Average 13 |

As you can see, F = 8, 10, and 12 all give us the minimum drop average or 10. For the sake of completion, let’s test values in between to see if they vary at all.

1 2 3 4 5 6 |
Results of building H = 100: Factor 8: Drop Average 10 Factor 9: Drop Average 10 Factor 10: Drop Average 10 Factor 11: Drop Average 10 Factor 12: Drop Average 10 |

So at least in terms of our system of checking values, 10 is the fewest number of drops we can use to discover N. It’s good to know that if we had to test this in real life we’ll only have to buy a dozen eggs.

http://imgur.com/a/MbwAy

This is how it looks like on my chrome :<

Fixed. This post was copied from my old blog and I didn’t notice that some of the formatting HTML came with it. Thanks for pointing that out.

Can we just simply use Binary search for this problem?