Egg drop DP over moves in Python

Why this matters

Many real problems ask how to find a boundary with a limited number of tries. A tester wants to find the first version of a program that fails, using as few test runs as possible. Each test costs something, and a test can destroy the thing being tested. The question is how to plan the tests so the worst case stays as small as possible.

The egg drop puzzle is the classic form of this question. It is a good example of dynamic programming over moves, not over positions in a list. The table does not store a count of routes or a sum. It stores the best result you can guarantee after a given number of moves, where a move is one drop of an egg.

The probability lesson earlier in this module also uses a table, but that table counts outcomes. This one counts how far the search can reach.

The puzzle is set in a building with n floors, numbered 1 to n. Somewhere in the building there is a critical floor. An egg dropped from that floor or above breaks. An egg dropped from below it survives and can be used again. You do not know the critical floor, and you have k eggs. A broken egg is gone for good. Your job is to find the critical floor, which may be floor 1. The number you want is the fewest drops that guarantee an answer in the worst case.

Every program in this lesson is a complete Python file that uses only the standard library. Save it as a file, for example main.py, and run it with python3 main.py. The outputs below were produced by Python 3.14.

Step 1: One egg

Start with the simplest case. You have one egg and ten floors. If you drop it from floor 5 and it survives, the critical floor is above 5. But you have only one egg, so if it breaks you cannot test any other floor. You have to test floor 1, then floor 2, then floor 3, and so on, until the egg breaks. In the worst case the critical floor is the top floor, so you need 10 drops.

With one egg, the answer is always the number of floors. No strategy beats that, because any floor you skip could be the critical one.

Step 2: Two eggs and a table of worst cases

Two eggs allow a smarter plan. Drop the first egg from floor 4. There are two outcomes.

The egg breaks. The critical floor is one of floors 1, 2 or 3. You now have one egg, so you need 3 more drops in the worst case.
The egg survives. The critical floor is one of floors 5 to 10. You still have two eggs and 6 floors to check.

The worst of these two outcomes decides how good the choice of floor 4 is. The cost of the drop is 1, plus the worse of the two outcomes:

1 + the larger of (drops needed for the floors below) and (drops needed for the floors above)

Try every floor x from 1 to the number of floors, and keep the smallest cost. That idea becomes a table worst[e][f], the fewest drops that always work with e eggs and f floors. Two base cases start the table. With one egg, worst[1][f] is f. With zero floors, nothing needs to be dropped, which is the default 0 that the list starts with. Each other entry comes from this rule:

worst[e][f] = 1 + the smallest value, over every floor x from 1 to f, of the larger of worst[e-1][x-1] and worst[e][f-x]

Here is the program. The first function is the table. The later functions are the faster approaches, which come after this step. A table in Python is a list of lists: worst[e] is one row, and worst[e][f] is one entry in that row.

Python · editable

from bisect import bisect_left
from math import comb

def worst_case_table(eggs, floors):
    """worst[e][f] = fewest drops that always work with e eggs and f floors."""
    worst = [[0] * (floors + 1) for _ in range(eggs + 1)]
    for f in range(1, floors + 1):
        worst[1][f] = f
    for e in range(2, eggs + 1):
        for f in range(1, floors + 1):
            worst[e][f] = min(
                1 + max(worst[e - 1][x - 1], worst[e][f - x])
                for x in range(1, f + 1)
            )
    return worst

def fewest_drops_by_moves_table(eggs, floors):
    reach = [0] * (eggs + 1)
    moves = 0
    while reach[eggs] < floors:
        moves += 1
        next_reach = [0] * (eggs + 1)
        for e in range(1, eggs + 1):
            next_reach[e] = reach[e - 1] + reach[e] + 1
        reach = next_reach
    return moves

def can_check(moves, eggs, floors):
    total = 0
    for i in range(1, min(eggs, moves) + 1):
        total += comb(moves, i)
        if total >= floors:
            return True
    return total >= floors

def fewest_drops_binary_search(eggs, floors):
    low = 1
    high = floors
    while low < high:
        mid = (low + high) // 2
        if can_check(mid, eggs, floors):
            high = mid
        else:
            low = mid + 1
    return low

def fewest_drops_bisect(eggs, floors):
    index = bisect_left(range(1, floors + 1), True, key=lambda m: can_check(m, eggs, floors))
    return index + 1

def main():
    table = worst_case_table(3, 10)
    print("Worst-case drops, floors 1 to 10:")
    for e in range(1, 4):
        cells = "".join(f"{table[e][f]:3d}" for f in range(1, 11))
        print(f"  eggs={e}:{cells}")

print("Eggs and floors, then answers from each method:")
    pairs = [(1, 10), (2, 10), (2, 100), (3, 14), (3, 100), (4, 1000)]
    for k, n in pairs:
        table_answer = worst_case_table(k, n)[k][n]
        print(
            f"  eggs={k} floors={n}  table={table_answer}"
            f"  moves={fewest_drops_by_moves_table(k, n)}"
            f"  search={fewest_drops_binary_search(k, n)}"
            f"  bisect={fewest_drops_bisect(k, n)}"
        )

mismatches = 0
    checked = 0
    for k in range(1, 7):
        t = worst_case_table(k, 80)
        for n in range(1, 81):
            checked += 1
            if (t[k][n] != fewest_drops_by_moves_table(k, n)
                    or t[k][n] != fewest_drops_binary_search(k, n)
                    or t[k][n] != fewest_drops_bisect(k, n)):
                mismatches += 1
    print(f"Cases checked: {checked}, mismatches: {mismatches}")

print("Floors reachable with 2 eggs after each drop:")
    reach = [0, 0, 0]
    for m in range(1, 5):
        next_reach = [0, 0, 0]
        for e in range(1, 3):
            next_reach[e] = reach[e - 1] + reach[e] + 1
        reach = next_reach
        print(f"  drops={m}  one egg={reach[1]}  two eggs={reach[2]}")

print(f"4 drops with 3 eggs cover 14 floors: {can_check(4, 3, 14)}, 15 floors: {can_check(4, 3, 15)}")
    print(f"Fewest drops, 100 eggs and 1000000000 floors: {fewest_drops_binary_search(100, 1_000_000_000)}")

if __name__ == "__main__":
    main()

Run it and the output begins like this:

Worst-case drops, floors 1 to 10:
  eggs=1:  1  2  3  4  5  6  7  8  9 10
  eggs=2:  1  2  2  3  3  3  4  4  4  4
  eggs=3:  1  2  2  3  3  3  3  4  4  4
Eggs and floors, then answers from each method:
  eggs=1 floors=10  table=10  moves=10  search=10  bisect=10
  eggs=2 floors=10  table=4  moves=4  search=4  bisect=4
  eggs=2 floors=100  table=14  moves=14  search=14  bisect=14
  eggs=3 floors=14  table=4  moves=4  search=4  bisect=4
  eggs=3 floors=100  table=9  moves=9  search=9  bisect=9
  eggs=4 floors=1000  table=13  moves=13  search=13  bisect=13
Cases checked: 480, mismatches: 0
Floors reachable with 2 eggs after each drop:
  drops=1  one egg=1  two eggs=1
  drops=2  one egg=2  two eggs=3
  drops=3  one egg=3  two eggs=6
  drops=4  one egg=4  two eggs=10
4 drops with 3 eggs cover 14 floors: True, 15 floors: False
Fewest drops, 100 eggs and 1000000000 floors: 30

The row for two eggs reads 1 2 2 3 3 3 4 4 4 4. With two eggs and ten floors, the answer is 4. The best first drop is floor 4, the same floor used in the plan above, because both outcomes then need at most 3 more drops: 3 floors below with one egg, and 6 floors above with two eggs.

Filling the table takes time. For each cell, the loop tries every floor, so the work is about eggs times floors squared. For 10 floors that is tiny. For 1000 floors it is still usable. For a billion floors it is not, and the later steps address that.

Step 3: A table of moves

The table in Step 2 asks a different question from the one we need. It asks for the worst case with a given number of floors. A more useful table asks the reverse question. Given a number of drops, how many floors can you handle?

Call that table reach[m][e]. It is the largest number of floors you can always resolve with m drops and e eggs. Two base cases: with no drops left, you can resolve no floors, so reach[0][e] is 0. With no eggs left, you cannot test anything, so reach[m][0] is 0.

Now the rule. With m drops and e eggs, drop the first egg from floor reach[m-1][e-1] + 1.

If the egg breaks, the floors below it are reach[m-1][e-1] floors. You have m - 1 drops and e - 1 eggs, so you can handle them.
If the egg survives, the floors above it are reach[m-1][e] floors. You have m - 1 drops and still e eggs, so you can handle them.

Add the two groups and the one floor you just tested:

reach[m][e] = reach[m-1][e-1] + reach[m-1][e] + 1

Now the answer is easy to read off. The fewest drops for k eggs and n floors is the smallest m for which reach[m][k] is at least n. The function fewest_drops_by_moves_table in the program does exactly that: it adds one row of moves at a time until the entry for k eggs covers all the floors. It keeps only the current row, which is the list reach, and builds the next one as next_reach.

The numbers for two eggs, from the output above, grow like this:

After 1 drop: 1 floor. The formula gives reach[1][2] = reach[0][1] + reach[0][2] + 1 = 1.
After 2 drops: 3 floors. The formula gives reach[2][2] = reach[1][1] + reach[1][2] + 1 = 1 + 1 + 1 = 3.
After 3 drops: 6 floors.
After 4 drops: 10 floors.

So two eggs with 4 drops handle 10 floors, and the answer for 10 floors is 4.

The row for one egg is just m, because with one egg each drop covers one new floor. The table for one egg matches the answer from Step 1.

Step 4: A faster search with binomial sums

The moves table takes time proportional to the answer times the number of eggs. For 100 eggs and a billion floors, the answer is about 30 drops, which is small. But the table would grow one row per drop, and each row has an entry for each egg count. That is still manageable here, yet there is a faster method.

Look at the numbers again. For two eggs, the floors covered after m drops are 1, 3, 6, 10. For m drops and one egg the answer is m. Those numbers are the triangle numbers, which are sums of the counts of ways to choose one or two things from m. In formula form:

reach[m][k] = C(m,1) + C(m,2) + ... + C(m,k)

Here C(m,i) is the number of ways to choose i items out of m, written in the textbook as "m choose i". Python computes it with math.comb(m, i). Check the formula on a small case. With m = 4 and k = 2, the sum is C(4,1) + C(4,2) = 4 + 6 = 10. That matches the table. With m = 3 and k = 2, the sum is 3 + 3 = 6, which also matches.

The formula agrees with the table because of a rule about binomial coefficients, called Pascal's rule. It splits each C(m,i) into two smaller coefficients for m - 1. Applied to the whole sum, that split gives the same "one more floor" rule as the moves table. You do not need the algebra for this lesson. You need only the formula and the checks above.

Now the binary search. The number of floors covered grows as the number of drops grows, so there is a smallest number of drops that covers n floors. A binary search finds that smallest number in about log2 steps. Each step asks: can mid drops cover all the floors? The function can_check answers that by adding the first k binomial coefficients, one at a time, and stopping as soon as the total reaches the number of floors.

If you want to see the coefficients without math.comb, they come from a running product. Start at 1, which is C(m,0). Each step computes binom = binom * (m - i + 1) // i. The // keeps the result a whole number. For m = 4: starting from 1, the first step gives 1 * 4 // 1 = 4, the second gives 4 * 3 // 2 = 6, and the third gives 6 * 2 // 3 = 4. Those are C(4,1), C(4,2) and C(4,3). The Java version of this lesson needed that product to stay below a fixed limit so it would fit in a long. Python integers have no such limit, so the early stop only saves work.

The function fewest_drops_bisect does the same search with the standard bisect module. bisect_left with a key function, available from Python 3.10, finds the first position where can_check turns true. The result is one more than that position, because the list starts at 1. The output shows it agrees with the other methods.

The result is the same as the table for every case the program checks. It checked 480 pairs of eggs and floors, using all four methods, and found 0 mismatches.

Worked example: 2 eggs and 100 floors

This is the classic case. Use the sum formula by hand. With 13 drops and 2 eggs, the floors covered are C(13,1) + C(13,2) = 13 + 78 = 91. That is less than 100, so 13 drops are not enough. With 14 drops the sum is 14 + 91 = 105, which is at least 100. So the answer is 14.

The program prints 14 for this case with all four methods. The table, the moves table, the binary search and the bisect version agree.

Worked example: 3 eggs and 14 floors

Now there is one more egg. Four drops with three eggs cover C(4,1) + C(4,2) + C(4,3) = 4 + 6 + 4 = 14 floors. That is exactly 14, so 4 drops are enough. Five drops would cover more, but four is the fewest. The program checks this directly: can_check(4, 3, 14) is True and can_check(4, 3, 15) is False. So the answer for 14 floors is 4, and 15 floors need one more drop.

Worked example: 100 eggs and a billion floors

With many eggs, the answer is limited by drops, not eggs. If the number of eggs is at least the number of drops, the sum of all the binomial coefficients from 1 to m is 2 to the power m minus 1. For m = 30 that is 2 ** 30 - 1, which is 1073741823 and is at least one billion. For m = 29 it is 2 ** 29 - 1, which is 536870911 and is less than one billion. So the answer is 30.

The program confirms this with the binary search and prints 30. The search needs about 30 checks, and each check runs at most 100 steps of the inner loop. The time is small, even though the building has a billion floors. The table method would need about 30 rows of 101 entries, which is also small. What makes the search faster for large inputs is that it does not store a table at all.

Common mistakes

An off-by-one error in the loop condition gives an answer that is one too large. This is the most common mistake in the moves table. The table row for 2 eggs already reaches 10 floors after 4 drops, so the loop should stop there:

while reach[eggs] < floors:  # correct

If the condition is written with <=, the loop runs one more time:

while reach[eggs] <= floors:  # wrong: adds one extra drop

In a test program, the wrong version prints 5 for 2 eggs and 10 floors. The correct version prints 4. Test every version on a small case that you can check by hand, such as 2 eggs and 10 floors.

Asking for zero eggs crashes the table. A program that calls worst_case_table(0, 5) builds a table with one row, which is row 0, and the first base case then reads row 1. Python reports this as an index error:

def worst_case_table(eggs, floors):
    worst = [[0] * (floors + 1) for _ in range(eggs + 1)]
    for f in range(1, floors + 1):
        worst[1][f] = f
    return worst
 
 
try:
    worst_case_table(0, 5)
except IndexError as e:
    print("IndexError:", e)

The output is:

IndexError: list index out of range

The message names the problem only in general terms, so check the number of eggs is at least 1 before you call the function.

Building a two-dimensional table with * copies a row reference, not the row itself. This is a Python-specific trap. The rows of [[0] * 3] * 2 are the same list, so a change to one row shows up in the other. Use a list comprehension to make a separate row for each egg count:

bad = [[0] * 3] * 2
bad[0][1] = 5
print("shared rows:", bad)
 
good = [[0] * 3 for _ in range(2)]
good[0][1] = 5
print("separate rows:", good)

The output is:

shared rows: [[0, 5, 0], [0, 5, 0]]
separate rows: [[0, 5, 0], [0, 0, 0]]

The naive table is slow for large floor counts. Its inner loop tries every floor, so filling the table takes time that grows with eggs times floors squared. For 1000 floors, that is about half a million steps for each egg count, which is fine. For a billion floors it is not usable. Use the binary search for large inputs.

Mixing up drops and floors gives a wrong answer that looks plausible. The table and the search return a count of drops, not a floor number. Read the question carefully: the answer for 2 eggs and 10 floors is 4 drops, and printing the floor count or the egg count instead would not answer the question.

The binary search needs the right bounds. The answer is at least 1, because a building with at least one floor needs at least one drop. The answer is never more than floors, because one egg can always test the floors in order. The program uses low = 1 and high = floors for that reason.

Practice

Exercise 1. You have one egg and seven floors. What is the fewest drops that always works?

Show the answer

With one egg, each drop must test the next floor up from the last safe one, so the worst case is the top floor.

Exercise 2. You have two eggs and six floors. What is the fewest drops that always works?

Show the answer

The moves table gives reach[3][2] = 6, because reach[2][1] + reach[2][2] + 1 = 2 + 3 + 1 = 6. Three drops cover six floors, and two drops cover only three.

Exercise 3. With two eggs and 5 drops, how many floors can you always resolve?

Show the answer

The sum is C(5,1) + C(5,2) = 5 + 10 = 15. Six drops would cover 6 + 15 = 21 floors. Calling fewest_drops_binary_search(2, 15) and fewest_drops_binary_search(2, 16) gives 5 and 6.

Exercise 4. The loop while reach[eggs] <= floors gives 5 instead of 4 for 2 eggs and 10 floors. Explain why in one or two sentences.

Show the answer

After 4 drops, reach[4][2] is already 10, which equals the number of floors. The <= condition keeps the loop going, adds one more drop, and returns 5. The loop should stop as soon as the number of floors covered reaches the number of floors needed, which is what < does.

Exercise 5. A building has 14 floors and you have 3 eggs. Can 4 drops always find the critical floor? Can 3 drops?

Show the answer

Yes for 4 drops, because C(4,1) + C(4,2) + C(4,3) = 4 + 6 + 4 = 14 is at least 14. No for 3 drops, because C(3,1) + C(3,2) + C(3,3) = 3 + 3 + 1 = 7 is less than 14. The answer for 14 floors and 3 eggs is 4.

Summary

The worst-case table tries every first drop and keeps the best, which is fast for small buildings only.
The moves table counts how many floors can be handled with each number of drops, and the answer is the first drop count that covers all the floors.
The moves table grows by the rule reach[m][e] = reach[m-1][e-1] + reach[m-1][e] + 1.
The number of floors covered after m drops with k eggs is the sum of C(m,1) through C(m,k), which math.comb computes.
A binary search over the number of drops, with that sum as the check, runs in time that depends on the number of eggs and the logarithm of the floors.

Egg drop DP over moves in Python

Why this matters

Step 1: One egg

Step 2: Two eggs and a table of worst cases

Step 3: A table of moves

Step 4: A faster search with binomial sums

Worked example: 2 eggs and 100 floors

Worked example: 3 eggs and 14 floors

Worked example: 100 eggs and a billion floors

Common mistakes

Practice

Summary

Stuck? Ask the tutor