The Falling Eggs Puzzle: Part 1

Introducing advanced dynamic programming techniques

You are getting ridiculously bored. You’re favourite publication has not posted any long articles for a while, and your brain, hungry for more problem-solving, decides to entertain itself by cooking up a new problem. Literally- it starts from you cooking an egg omelette.

As you break the eggs to cook it, you remember your cousin, who has a chicken farm. His chickens lay genetically modified eggs that are super-resistant to damage. In order to test the strength of each egg, he needs to collect some number, K, of eggs in a box. He then finds a building with N floors. All the K eggs are identical, and he tests their strength by taking an egg and going up to some floor in the building. He then drops the egg and checks if it breaks. If it breaks, he takes another egg from the box, otherwise he re-uses the unbroken egg. The process is repeated until he finds the highest floor from which he can drop an egg without it breaking.

As you remember your cousin, coincidentally, he sends you a text requesting you to solve his problem.

Given the number of eggs, K, and the number of floors to test, N, what is the minimum number of drops I need so that I am guaranteed to solve my problem before running out of eggs? Write some code to solve it please

Time to put on your thinking cap and get to work!

Dear readers,

The long awaited big post is finally here! So big, in fact, that it must be split into 2 parts. Thank you all for your patience and support. These 2 big posts will each have a free section, and a paid section. In order to experience the full thing, and also support my contribution to building up your problem-solving skills, consider becoming a paid subscriber. To those who do so by 24 September, there is 10% discount per month available to be redeemed here

To those who aren’t already subscribed, consider joining the family for new brain-boosting content every week!

Sit back, relax, and happy reading!

Is there always a solution?

Before finding a solution, it’s probably best to confirm that there is, in fact, a solution to this problem every single time. To do so, let’s investigate problem states. This is a concept you’re probably familiar with from dynamic programming, but if not, a quick recap- problem states are a piece of information telling us how close we are to solving a problem.

To begin, what information do we need to know whether we have solved the problem? The proof is simple and can be derived from a step-by-step logical process.

1. If I have at least 1 egg, there is a solution that can obtained by dropping that egg from the lowest floor, then the one above it, and so on until it breaks. Once the egg breaks, I have a solution. This is, of course, the slowest possible solution- testing every floor one-at-a-time.

2. Therefore, if I have more than 1 egg, a solution must exist. It is expected, however, that since I have more eggs, the solution will be faster. Our job is to find this faster strategy

3. If I have 0 eggs, I must have found the solution (otherwise there’s nothing I can do anyways since I have no eggs to drop).

So the information needed to solve this problem is

• Number of eggs left

• Number of levels not tested yet

Every egg drop brings us from one state to another.

• If I had k eggs and the one I drop breaks, I now have k-1

• There are fewer levels that I have left to test, since dropping the egg revealed new information

Initially, the state is one where I have K eggs and N levels to test. Once the problem is solved, the state becomes one where I have 0 levels to test, and the number of eggs I have is (logically) not a negative number (otherwise I have used more eggs that I have).

Starting simple

Let f be some function that gives us the solution we’re looking for. It’s useful to describe the recurrence in words first. Again, logic is our best friend here.

• Imagine I have to test levels numbered from a to b. For example, at first, I have to test levels from 1 to N. Also imagine that I have k eggs for this particular task.

• I get to choose any level, l, from which to drop the egg. I will choose the value of l that gives the shortest path to the solution even in the worst case.

  • If the egg breaks, I know that the egg must logically also break from levels l+1 to b. Therefore, I then need to test levels a to l-1 with k-1 eggs.

  • If the egg does not break, I know that the egg must logically also not break from levels a to l-1. Therefore, I then need to test levels l+1 to b with k eggs.

• Notice that the values of a and b do not matter, since they are completely generalised. Therefore, instead of using a and b, we can say that there are n floors I am yet to test, arbitrarily labelled from 1 to n.

  • Then the case where the egg breaks simplifies to one that leaves me with n-l levels to check with k-1 eggs

  • Similarly, the case where the egg does not break simplifies to one that leaves me with l-1 levels to check with k eggs.

• I choose the value of l that gives the lowest drops even in the worst case

• Therefore, let f(n,k) be the solution for n levels and k eggs.

Let’s break down the equation we just derived

Once that’s done, our answer is just f(N, K).

Since all we need to solve this problem are 2 numbers, n and k, our state can be simplified to a pair of numbers written in the form (n,k).

• There are N*K possible states

• From the function f, it takes O(n) time to move from one state to another, because that’s the time it takes to test every value of l and find which one is the best

• Overall, therefore, the time complexity of this solution is O(KN^2)

Not bad for a first try, but we can get better indeed. Much better. To discover the more efficient solution, we need to exploit monotonicity.

Monotonicity

Whenever we have a function, there’s a chance that the function is always increasing or always decreasing.

Definition

A monotonic function always preserves or reverses the given order of input. This means that as the input to the function increases, the value of the function either always increases or always decreases. There are no turning points, or other deviations from this pattern. It can (but doesn’t need to be) a straight line.

A monotonically increasing function is always increasing as the input increases. A monotonically decreasing function is always decreasing as the input increases.

Within the function f(n,k), we’re particularly interested in this bit.

It should makes sense that 2 things happen as l increases from 1 to n.

1. l-1 also increases as l increases

2. n-l decreases as l increases

Now consider what implications this has. Consider 2 functions that have the same k value. Let’s call these f(n1, k) and f(n2, k). Suppose that n2 > n1. This means that with the same number of eggs, I need to test a larger number of levels. So the number of drops I will need is guaranteed to be more. This should make sense- the more levels I need to test, the more drops I will need to get a guaranteed answer. So if n2 > n1, then f(n2, k) > f(n1, k). This means that as n increases in the function f(n, k), then f also increases. We conclude that f is monotonically increasing with respect to n.

The use of monotonicity unlocks a new method to solve this problem. Now that we know how f works, let’s graph f against l and see what happens. Remember that as l increases, l-1 increases while n-l decreases?

Exploiting monotonic graphs

The property of monotonicity is important in reducing the time complexity of our solution dramatically, let’s investigate how.