You have three eggs that are "unbreakable." You believe this claim to be nonsense and would like to test it. You want to see how high the egg's shells can withstand. Because this is in the distant future, you live in a building 1,000,000 stories tall. Because you're not made of time, you'd like to do this as quickly as possible.
What's the best strategy for determining exactly how high you can drop an egg from?
Hint (Highlight to read):
Binary search has a worst case of nearly 250,000, you can do much better than that. You know you're on the right track when your worst case is around 300, you'll know you have it when you're even less than that.
The optimal strategy is not the one that follows. But it is LIKE the one that follows so you should read it over first and understand it.
First: Go to floor 10,000, test, if it breaks the move to the second stage of the strategy, if it doesn't, move up to floor 20,000, repeat.
Second: When you have one broken egg, move down 9,900 floors (to floor X0,100) and tests floors in multiples of 100 until the egg breaks.
Third: When the second egg breaks, move down 99 floors, and test the floors one at a time going up until the egg breaks.
But as it turns out, there is an even more optimal strategy than that. So what can we do to make the worst case better? Well right now there's a worst case penalty imposed whenever you go up floors. You're doing more testing without making the search space smaller.
It relies on triangle and tetrahedral numbers. Triangle numbers are like factorals for addition. 1, 1+2, 1+2+3, etc. They start out as 1, 3, 6, 10, 15, 21. Tetrahedral numbers is what you get when you add up the triangle numbers in the manner. 1, 1+3, 1+3+6... They start out as 1, 4, 10, 20, 35, 56...
To solve this let's consider 100 floors with two eggs. Our solution before would have us start at the 10th floor, then go up another 10 every time until the first egg broke. Worst case would be 19 attempts.
Using the formula 1/2(n)(n+1) for triangle numbers. The first triangle number larger than 100 is 14th (105). So we test the 14th floor. If it breaks then we go up 13 floors, then 12. So our worst case scenario is 14 tests. Rather than 19. I'll state that as a fact. The reason why should be obvious to the most casual observer.
So if we know that triangle numbers are the most efficient way to run the second stage in our three egg run, then we know that the first stage should be something similar. So we turn to tetrahedral numbers. Our plan is tetrahedral numbers -> triangle numbers -> natural numbers.
So finally, the solution is:
Phase 1: Using the formula 1/6(n)(n+1)(n+2) for tetrahedral numbers. The first tetrahedral number larger than 1,000,000 is the 181st (1,004,731). So we find the 181st triangle number, which is 16,471, and go to that floor. Test the egg. If it breaks move to phase 2. If it doesn't break, we move up 16,290 floors (this is the 180th triangle number) to floor 32,761. Test the egg. Etc.
Phase 2: Go back down to the last floor successfully tested. Using the formula 1/2(n)(n+1) for triangle numbers, we need to figure out the applicable number of floors to go up based on our search space. The good thing is this time the number will always come out round because of our floor choices in phase one. In fact, if you went up by the nth triangle number the last time, you should go up n floors. So let's say your egg broke on floor 32,761. You go back down to floor 16,471 then up 180 floors, then 179, etc. When your second egg breaks move to phase 3.
Phase 3: Go back down to the last floor successfully tested. Using the formula n for natural numbers (haha), we go up one floor at a time until the egg breaks.
Worst case for this method is 181 drops. Which is much better than the 298 drops for the other method, and way, way better than the 250,001 drops for the binary search.