Optimizing the Egg Drop Problem implemented with Python

Question

I've implemented the Egg Drop Problem using Python. As described in the code, I'm trying to find the highest floor of a 102-story building from which I could drop an egg without it breaking.

The approach I took here is by using a binary search method, where I initialize the upper bound as the building height, the lower bound as 0, and the middle floor as half the building height. Depending on whether the egg breaks or not, I adjust the upper or lower bounds, and calculate a new middle floor for the next iteration, i.e., O(log(N)).

I know there are dynamic programming techniques to optimize this further which (a) reduce the number of eggs used or (b) minimize the number of drops. Can someone provide insights, resources or suggestions?

# The Empire State Building is 102 stories high. A man wanted to know the highest floor from
# which he could drop an egg without the egg breaking. He proposed to drop an egg from the
# top floor. If it broke, he would go down a floor, and try it again. He would do this until
# the egg did not break. At worst, this method requires 102 eggs. Implement a method that at
# worst uses seven eggs.

height = 102  

def EggDrop(floor):
  eggs = 7 
  upper, middle, lower = height, height // 2, 0 
  while eggs > 0:
    if middle > floor:
      upper = middle - 1
      eggs = eggs - 1
    elif middle < floor:
      lower = middle + 1
    else:
      if middle + 1 > floor:
        print(f"The highest floor we can drop an egg from is {middle}, with {eggs} eggs left over.")
        break
    middle = (upper + lower) // 2

for i in range(height + 1):
  EggDrop(i)

Answer 1

conventional spelling

def EggDrop(floor):

When writing an English sentence,
yore bedder aff riting korrekt ledders
than surprising the reader with non-standard spellings. Will the reader understand the meaning? Yes. But you could do a better job of conveying what you want understood.

Here, you and pep-8 are telling me that this is SomeClass, which is a bit jarring coming on the heels of def which introduces some_function. Worse, down below the EggDrop(i) call appears to be invoking a class constructor and discarding the resulting class instance. In a small program the Gentle Reader will remember these odd aspects and eventually realize it's a function call. But in a program with many classes and functions written by diverse authors, things can quickly grow unmanageable. Please write python code the way the rest of the python community does when you wish to collaborate with others.

---

return values

The biggest critique of this code is we evaluate a complex loop for side effects (for printing a result) rather than returning a result. This makes it harder to read, since it's only way down in the middle + 1 > floor clause that we get to the punch line which reveals the function's purpose.

Consider adopting any one of these signatures:

def egg_drop(target_floor: int) -> int:

def egg_drop(target_floor: int) -> tuple[int, int]:

def egg_drop(target_floor: int) -> str:

The middle one would return (middle, eggs), while the last would return the same formatted string you're printing now.

All of them would be unit testable, with the first two being especially convenient to test. (Yes, the OP code could be tested by redirecting sys.stdout to a buffer, but there's no need to design a Public API that is gratuitously hard to test. In general, side effects complicate things and make testing harder.)

---

The "problem setup" comments at top of source file were very nice and I thank you for them.

write """docstrings"""

I suggested renaming your formal parameter to something like target_floor, the floor number we binary search for, because I found the current signature initially misleading. I thought I understood your meaning, of "floor we took the elevator to and performed a drop experiment from", and soon found that interpretation was dead wrong.

Putting a """docstring""" below the signature gives you an opportunity to describe the meaning of outputs and inputs, even if you retain the floor name. Always take the opportunity to write at least one sentence, since the signature usually won't spell out everything of interest. Optionally go on with more description if you feel there's more to say.

---

invariants

There are some important relationships among your loop variables. Write them down in # comments.

Clearly each time we enter the while, middle will be in the range lower .. upper. You could have made that more clear by using a single assignment after the while, rather than a pair of assignments.

The intent is that upper > lower, which is a little tricky to prove.

It is OK to have middle == lower, and it wouldn't hurt to mention that in a comment.

We intend that target_floor shall be in the range lower .. upper, but we neglected to check that upon function entry. European floors would be numbered 0 .. 101, while American floor numbers range from 1 .. 102. Computer scientists like zero-origin, even if they don't live in Europe. It would be helpful to spell out what floor numbers mean in this context, to avoid an OBOB. Then write the occasional unit test to verify.

Answer 2

The implication of the problem statement is that there's an interactive experiment being conducted, but that doesn't seem to be what you've implemented.

To gain user interaction and also use the built-in bisect method rather than rolling your own, you could do something like:

from bisect import bisect


class Experiment:
    def __init__(self, floors: int, eggs: int) -> None:
        self.floors = floors
        self.eggs = eggs

    def __getitem__(self, floor: int) -> bool:
        if self.eggs > 0:
            self.eggs -= 1
        else:
            raise ValueError('We have run out of eggs.')

        answer = input(f'An egg is dropped from floor {floor}. Did it break (y/n)? ')
        return answer.lower() == 'y'

    def __len__(self) -> int:
        return self.floors

    def run(self) -> int:
        return bisect(a=self, x=False) - 1


def main() -> None:
    experiment = Experiment(floors=102, eggs=7)
    print(
        f'The highest floor we can drop an egg from is {experiment.run()}, '
        f'with {experiment.eggs} eggs left over.'
    )


if __name__ == '__main__':
    main()

An egg is dropped from floor 51. Did it break (y/n)? y
An egg is dropped from floor 25. Did it break (y/n)? y
An egg is dropped from floor 12. Did it break (y/n)? y
An egg is dropped from floor 6. Did it break (y/n)? y
An egg is dropped from floor 3. Did it break (y/n)? n
An egg is dropped from floor 5. Did it break (y/n)? y
An egg is dropped from floor 4. Did it break (y/n)? y
The highest floor we can drop an egg from is 3, with 0 eggs left over.

Answer 3

I won't duplicate the remarks made by J_H and instead offer one of my own:

What I find a bit strange is that your function EggDrop is being passed what ultimately turns out to be the correct answer. I would instead expect that in a more realistic posing of the problem you are passed a list floors of Boolean values. For indices 0 to some value N the values are True signifying that you can drop an egg safely from any of these floors (1 through N+1) and the remaining values are False. This list could be not just length 102 but rather any length > 0. What you are then looking for is the value N, i.e. the maximum value of n such that floors[n] is True. The edge cases are where all elements of floors are False (the egg cannot be dropped safely from any floor) or True (the egg can be safely dropped from all floors and therefore the answer is the top floor). The maximum number of searches should be ceil(log2(height) where height is the number of elements in floors.

We can then test our function using a height of 102 a total of 103 times for every possible case. I agree with J_H that you probably want to have your function return the correct answer even though I have not done that here rather than print it. But I also wanted to print the total number of searches done and I would then have to return back to the caller two values if I wanted to eliminate all printing from this function and I did not want to confuse the issue.

from typing import List
from math import ceil, log2

def egg_drop(floors: List[bool]) -> None:
    """floors is a list of boolean values, one for each floor.
    They are all True for index values 0 to n representing
    that an egg can be safely dropped from floors 1 through n+1.
    All the other values are False. We are to find the maximum value
    of n for which floors[n] is True (if any) and then print n+1.
    """

    height = len(floors)
    searches_performed = 0

    # Index range to be searched:
    lower, upper = 0, height - 1
    while True:
        searches_performed += 1
        # Check floor n:
        n = (lower + upper) // 2

        if n < 0:
            # We have looked at every floor to no avail:
            print('The egg cannot be safely dropped from any floor', end=' ')
            break

        # If we cannot drop an egg from this floor,
        # modify the upper bound:
        if not floors[n]:
            upper = n - 1
            continue

        # The egg can be dropped from this floor, but what about from the
        # floor above?
        floor_above = n + 1
        if floor_above == height or not floors[floor_above]:
            # We can go no higher and safely drop an egg:
            print(f'The highest floor we can drop an egg from is {n + 1}', end=' ')
            break
        else:
            lower = n + 1

    print(f'(the number of searches was {searches_performed}).')
    assert searches_performed <= ceil(log2(height))

def tester() -> None:
    HEIGHT = 102

    for n in range(0, HEIGHT+1):
        floors = [False] * HEIGHT
        # All floors from 0 to n-1 will be True
        for i in range(0, n):
            floors[i] = True
        egg_drop(floors)

if __name__ == '__main__':
    tester()

Prints:

The egg cannot be safely dropped from any floor (the number of searches was 7).
The highest floor we can drop an egg from is 1 (the number of searches was 6).
The highest floor we can drop an egg from is 2 (the number of searches was 7).
The highest floor we can drop an egg from is 3 (the number of searches was 5).
The highest floor we can drop an egg from is 4 (the number of searches was 6).
The highest floor we can drop an egg from is 5 (the number of searches was 7).
The highest floor we can drop an egg from is 6 (the number of searches was 4).
The highest floor we can drop an egg from is 7 (the number of searches was 6).
The highest floor we can drop an egg from is 8 (the number of searches was 7).
The highest floor we can drop an egg from is 9 (the number of searches was 5).
The highest floor we can drop an egg from is 10 (the number of searches was 6).
The highest floor we can drop an egg from is 11 (the number of searches was 7).
The highest floor we can drop an egg from is 12 (the number of searches was 3).
The highest floor we can drop an egg from is 13 (the number of searches was 6).
The highest floor we can drop an egg from is 14 (the number of searches was 7).
...
The highest floor we can drop an egg from is 94 (the number of searches was 6).
The highest floor we can drop an egg from is 95 (the number of searches was 7).
The highest floor we can drop an egg from is 96 (the number of searches was 4).
The highest floor we can drop an egg from is 97 (the number of searches was 6).
The highest floor we can drop an egg from is 98 (the number of searches was 7).
The highest floor we can drop an egg from is 99 (the number of searches was 5).
The highest floor we can drop an egg from is 100 (the number of searches was 7).
The highest floor we can drop an egg from is 101 (the number of searches was 6).
The highest floor we can drop an egg from is 102 (the number of searches was 7).