Three egg proble​m

Mark_65387 0
Viewed 13624

I was just reading The Two Egg Problem:

The Two Egg Problem

You are given two eggs, and access to a 100-storey building. Both eggs are identical. The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.

If an egg breaks when dropped from floor n, then it would also have broken from any floor above that. If an egg survives a fall, then it will survive any fall shorter than that.

The question is: What strategy should you adopt to minimize the number egg drops it takes to find the solution?. (And what is the worst case for the number of drops it will take?)

I was following along until the "Look see I can do three" section. The author states that after the first egg breaks it degrades into the 2-egg problem and can be solved recursively.

That's great, but wouldn't we want to choose larger step-sizes when using 3 eggs instead of 2 (for the first egg)? From which floor do we throw the first egg?

With 1 egg, we have to start at floor 1.
With 2 eggs, we solve for n(n+1)/2=k and round up, where n is the starting floor, and k is the number of floors.
With 3... I'm having trouble coming up with a formula.

Thinking about this a bit more, with 2 eggs, the maximum number of drops is equal to the floor number that we drop our first egg from. For example, with 2 eggs and 100 floors, the solution is 14, which means we drop the first egg from floor 14, and if it breaks, we have to drop up to 13 more times, for floors 1-13.

With 3 eggs, the solution is 9 (as shown in the chart). But we wouldn't want to throw the first egg at floor 9, we can throw it higher, because we don't have to iterate by 1s in-between.

If we throw from floor 14 again, and it breaks, then we recurse. n(n+1)/2=k where k is now 13... but that gives us 4.815, if we ceil and that and add our previous drop we get 6, which is lower than the actual solution, so something here is wrong...

math algorithm
5 Answers

This is the same answer that I provided at Egg Drop Printing Solutions. I am providing it here for anyone who wants to see the whole decision tree and reasoning laid out.

# This uses dynamic programming to find the basic information.
def optimal_solution(floors, eggs):
    # dp[drops][eggs] = max_floors
    dp = []

    # With no drops, we can do no floors
    dp.append([0 for x in range(eggs+1)])

    # With one drop and any eggs, we can do 1 floor
    one_drop = [1 for _ in range(eggs+1)]
    one_drop[0] = 0 # Except no eggs is still no floors
    dp.append(one_drop)

    # Keep adding drops until we have our answer
    # Note, in python array element -1 is shorthand for the end of the array.
    while dp[-1][eggs] < floors:
        # 0 floors for 0 eggs.  1 more for one egg
        next_drop = [0, dp[-1][1] + 1]
        for i in range(2, eggs+1): # Python for 2..eggs
            # The best we can do is drop at floor dp[-1][i-1].
            # If the egg breaks, we can find the answer using that solution.
            # If the egg holds, we can find another dp[-1][i] floors.
            next_drop.append(dp[-1][i] + dp[-1][i-1])
        dp.append(next_drop)

    return dp

# This turns that optimal solution into a decision tree.    
def dp_to_decision_tree(dp, floors, start_floor=None, eggs=None, drops=None):
    # Figure out defaults if needed.
    if start_floor is None:
        start_floor = 0
    if drops is None:
        drops = len(dp) - 1
    if eggs is None:
        eggs = len(dp[0]) - 1

    # Are we done?
    if floors == start_floor:
        return start_floor
    elif dp[drops][eggs] < floors - start_floor:
        return None

    # Do we need all of our drops?
    while floors - start_floor < dp[drops-1][eggs]:
        drops -= 1

    drop_at = start_floor + dp[drops-1][eggs-1]
    if eggs == 1:
        drop_at = start_floor + 1
    if floors < drop_at:
        drop_at = floors
    return [
        drop_at,
        dp_to_decision_tree(dp,  floors,     drop_at,   eggs, drops-1),
        dp_to_decision_tree(dp, drop_at-1, start_floor, eggs-1, drops-1),
        {'eggs': eggs, 'floor_range': (start_floor, floors)}
        ]

# This prints the decision tree in a human readable format.
def print_decision_tree(tree, indent="", label="start"):
    if tree is None:
        print(f"{indent}{label}: ?")
    elif isinstance(tree, int):
        print(f"{indent}{label}: {tree} found")
    else:
        print(f"{indent}{label}: {tree[0]} {tree[3]}")
        print_decision_tree(tree[1], indent + "    ", label="held")
        print_decision_tree(tree[2], indent + "    ", label="broke")

# And this calls the previous functions.
def print_optimal_decisions(floors, eggs):
    print_decision_tree(
        dp_to_decision_tree(
            optimal_solution(floors, eggs), floors))

# And now we can try it.
print_optimal_decisions(36, 3)
user_5854110
user_72930570
Related