Python Challenge - Egg Dropper

This community-built FAQ covers the “Egg Dropper” code challenge in Python. You can find that challenge here, or pick any challenge you like from our list.

Top Discussions on the Python challenge Egg Dropper

There are currently no frequently asked questions or top answers associated with this challenge – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this challenge. Ask a question or post a solution by clicking reply (reply) below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this challenge, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!
You can also find further discussion and get answers to your questions over in Language Help.

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head to Language Help and Tips and Resources. If you are wanting feedback or inspiration for a project, check out Projects.

Looking for motivation to keep learning? Join our wider discussions in Community

Learn more about how to use this guide.

Found a bug? Report it online, or post in Bug Reporting

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

def egg_drop(n): i = 1 total = 0 while True: total += i if total >= n: break else: i += 1 return i print(egg_drop(100))
def egg_drop(n): y = 0 for x in range(n+1): if y < n: y+=x index = x return index print(egg_drop(400))

It’s a triangular series (but that’s math, not compsci i guess)

#Linear time!! import math def egg_drop(n): return math.ceil(math.sqrt(2*n+1) - 1)
import math def egg_drop(n): return math.ceil(math.sqrt(2*n + 1/4) - 1/2) print(egg_drop(100))

Trying to break down my thinking about this one by giving a smaller example: The ideal strategy for this problem can be characterized by the first pick to drop an egg from.

Suppose you have n = 15 floors. To minimize the amounts of tries, first drop one egg from floor 5.

  1. If it breaks, drop the second egg from floor 1, then 2, 3, and 4 to find floor f. At worst you need 5 egg drops this way.
  2. If the egg dropped from floor 5 doesn’t break, drop it from floor 9 (5+4) next. If it breaks, drop the second egg from floors 6, 7, 8 (again needing 5 egg drops at worst). If not, drop the first egg from floor 12 (5+4+3) next, floor 14 (5+4+3+2) next, floor 15 at last (5+4+3+2+1).

So you need a minimum of 5 egg drops for n = 15. For floor numbers up to n = 21 you need 6 egg drops etc. x egg drops are needed for a number of floors up to n = x(x+1)/2 because this gives you the sum of all natural numbers from 1 to x . We’re after x so we can rearrange this equation to x = sqrt(2n + 1/4) - 1/2 and round this up.

2 Likes
import numpy as np
def egg_drop(n):
  # number of attempts t
  # find sum of integers from 1 to t
  # sum is given by sum = t/2 * (t + 1)   
  t = (-1 + ((1 + 4*2*n)**.5))/2
  return int(np.ceil(t))



print(egg_drop(100))

def egg_drop(n):

Write your function here

#explanation
# Recursion would mean that I call this function
# Inside of this function, so
# We could use the tip for 2 story building situation
# >For example egg_drop(2) should return 2
# and using it to solve more complex situations

# as soon as your first egg breaks
# you have to go bottom to top with your last egg

# if we have 1 egg and k candidates for f
# we solve it reliably in k drops

# egg_drop(5)

# if we drop it on the 3rd floor and it does not break
#   we solve it with 2 drops on 4 and 5
# if we drop it on the 3rd floor and it does break
#   we solve it with 2 drops on 1 and 2
# this looks like a binary search pattern, but it 
# does not hold:

#egg_drop(11)

# if we follor binary search logic and drop an egg
# on 6th floor and it breaks
# we have to go from 1 to 5, resulting in 6 drops
# !not binary tree recursion!

# example above made me think
# if egg_drop(100)=14, then it means, that
# if
  #we divide floors in equal clusters and 
  # drop eggs from the top of the clusters
  # starting from a bottom cluster going up
  # as soon as one cluster gives a broken egg
  # we go and check the cluster from bottom to top
# then the worst case of checking means that 
# we got to the top cluster and we have to go all
# the way through the cluster and 
# total amount of clusters + amount of floors in
# one cluster = 14 + 1 = 15
# no sum of 2 multiplicators of 100 gives 15

#OH

# WE DON'T NEED TO DIVIDE THE FLOORS IN EQUAL CLUSTERS
# THE FIRST CLUSTER IS 14 FLOORS LONG
# SECOND IS 13 (27 total)
# third is 12 (39 total)
# fourth is 11 (50 total)
# fifth is 10 (60 total)
# sixth is 9 (69 total)
# seventh is 8 (78 total)
# eight is 7 (85 total)
# ninth is 6 (91 total)
# tenth is 5 (95 total)
# eleventh is 4 (99 total)
# twelth_better is 3 (102 total)
# thirteenth_better is 2 (104 total)
# fourteenth_better is 1 (105 total)

# how do we calculate this cluster thing?

# this is a sum of integers from 1 to eggdrop(n) 
# we can set up a while loop to check if the
# sum is bigger than the n
# and the counter would be the answer

S=0
i=0
while S<n:
i+=1
S+=i
return i

print(egg_drop(100))

If you were climbing the tower you would want to start from the highest floor you could drop the egg from (14) and then be able to drop the other egg from the first floor up. If it didn’t break on floor 14 you could drop the next egg from floor 27 or 13 floors above 14 as this would still leave you enough moves to check all the floors between 14 and 27. This same pattern would continue to the top.

Luckily though, this is just a theoretical problem so we can start at the top taking 1 extra floor away each time and count how many times we took away floors. In this way we get the same solution.

def egg_drop(n):
  attempts = 0
  while n > 0:
    attempts += 1
    n -= attempts
  return attempts

print(egg_drop(100))

My solution. Can I explain how it works logically? Absolutely not. Does it work? Yes. Also, ignore the lack of indentation, it was present in my original code of course, but I can’t figure out quite how to get it to work on this forum.

def egg_drop(n):
x = 0
y = 1
minNum = 0
while x < n:
x += y
y += 1
minNum += 1
return minNum

print(egg_drop(100))

1 Like

I wanted to post a solution that might help people walk themselves through the logic behind the egg drop problem.
While there does exist both a maths solution and an optimization by assuming num_eggs == 2.

The nature of the general problem is really quite fascinating. So I hope my solution can help someone else get there as well.

import sys
NUM_EGGS = 2

class EggDropHelper():
    """
    Class to help solve the Egg Drop problem for any number of eggs/floors.
    Construct the class with specified number of eggs and levels,
    then compute solution with EggDropHelper.compute()
    """

    def __init__(self, num_eggs, num_floors):

        self._num_eggs = num_eggs
        self._num_floors = num_floors

        #      1e 2e 3e 4e
        # 1f [[ ][ ][ ][ ]]
        # 2f [[ ][ ][ ][ ]]
        # 3f [[ ][ ][ ][ ]]
        self._soln_table = [[-1 for _ in range(num_eggs)] for _ in range(num_floors)]

    def egg_drop(self, num_eggs, num_floors):
        """
        Compute the minimum number of drops for a 
        given number of eggs and floors.

        This is done recursively, by:
        - Looking at the current problem state.
        - Scaning through each possible floor we could drop an egg from.
        - For each floor, we consider 2 scenarios:
            1) The egg breaks
                 We now have 1 less egg, and the floor is below us.
                 Recurse to the sub-problem where we have 1 less egg,
                 for all the floors below us.
            2) The egg DOES NOT break
                 We still have all our eggs, and the floor is above us.
                 Recurse to the sub-problem where we have the same amout of eggs,
                 for all the floors above us.
        - Take the maximum value of the 2 possible branches.
          (This value is the maximum number of tests possible if we drop from this floor,
           considering both the simulations where the egg broke here or it didn't)
        - Compare this upper bound on testing cost, to the floor with the current minimum cost.
        - If it is lower, then we have found a cheaper path in our simulations.
          Update the current minimum cost.

        Since this computation is recursive, we must consider the base cases:

        Base Case #1 -- 1 Egg
           We must scan through all floors from the bottom up, to avoid losing our only egg.
           Minimum <= num_floors
           
        Base Case #2 -- 0/1 Floors
           Trivial scenario, no tests necessary.
           Minimum <= num_floors

        Caches solutions in lookup table _soln_table
        This caching is NOT OPTIONAL for this class of algorithm.
        Without some sort of lookup table for existing solutions,
        you won't make it much further than 2 eggs ~25 levels
        """
                
        # Base cases
        if num_eggs == 1 or num_floors <= 1:
            return num_floors

        # Grab potentially pre-computed solns
        soln = self._soln_table[num_floors-1][num_eggs-1]
        if soln != -1:
            return soln

        # Find the minimum of the worst simulated scenarios
        soln = sys.maxsize
        for i in range(1, num_floors+1):
            
            # Egg NO break, 
            # Recurse to find the cheapest scenario where we have 
            # the same number of eggs and just the floors above us
            case_no_crack = self.egg_drop(num_eggs, num_floors-i)

            # Egg breaks,
            # Recurse to find the cheapest scenario where we have 
            # ONE FEWER egg and just the floors below us
            case_crack = self.egg_drop(num_eggs - 1, i-1)
            
            # Determine the more costly simulation
            soln = min(soln, max(case_crack,  case_no_crack))

        # Need to add 1 to account for the drop at this level of the recursion
        # We computed, above, the number of further drops necessary, 
        # IF WE DROPPED on a particular floor
        # So we need to account for us actually having dropped the egg, when we return to the caller
        soln+=1

        # Cache solution
        self._soln_table[num_floors-1][num_eggs-1] = soln

        return soln

    def compute(self):
        """
        Compute the minimum number of drops needed to determine 
        the egg dropping threshold.
        """
        return self.egg_drop(self._num_eggs, self._num_floors)

def egg_drop(n):
  return EggDropHelper(NUM_EGGS, n).compute()

1 Like
def egg_drop(n): # Write your function here f = 1 num = 1 while num < n: f += 1 num = num + f return f print(egg_drop(100))

lol no recursion

def egg_drop(n): drops = 0; floors = 0; while floors < n: drops += 1 floors += drops return drops print(egg_drop(100))

Now with recursion

def egg_drop(n): def eggs(drops, floors, n2): if floors >= n2: return drops - 1 return eggs(drops + 1, floors + drops, n2) return eggs(0, 0, n) for i in range(100): print(i, end = "") print(" ", end = "") print(egg_drop(i))

Maybe it’s a bug, I don’t know. This is probably another case of “code works - no idea why”.
The main idea was to split the floors into even clusters to narrow down the cluster where “f” is located and return the number of iterations needed to break down the total number of floors. I am skeptical whether this should work this way. Maybe the tests in the challenge should be reviewed, code below:

def egg_drop(n):

Write your function here

tries = 0
floors = n
while floors >= 1:
floors = floors//2
tries = tries+1
if n > 10:
return tries*2
else:
return tries

print(egg_drop(12))
print(egg_drop(100))

def egg_drop(n): eggs = 0 while n > 0: eggs += 1 n -= eggs return eggs print(egg_drop(100))
1 Like
If I drop an egg and it breaks, I'm forced to test floors below
one by one. So I want a starting floor of which when worst case
the egg breaks, the resulting total drops is my minimum.

I know it is the minimum once I can increment up from that
starting floor using the same logic, just 1 less in total added
floors each time to account for the previous drops, and reach
the max floor. This way I know I'll be able to test all floors.

Once I find a starting floor where I can increment this way,
the answer is the starting floor, since that is how many drops
would be required to know for certain from that floor, and it
is the worst case scenario for that setup.
def egg_drop(n): """ Ex. n = 5 | 1 , 6 | 6 > 5, I can test all floors | 1 , 3 | 2 , 5 | 0 | 1 , 1 | 2 , 2 | 3 , 3 | So 3 is the minimum drops needed """ # Testing starting floors starting from 0 for i in range(n+1): # Keep a running count with initial value of starting floor count = i # Decrement from starting floor to 1 for j in reversed(range(1,i+1)): # Add one less to decrement value to running count count += j - 1 # Answer is found when running count exceeds the top floor if count >= n: return i print(egg_drop(100))

def egg_drop(n):

Write your function here

if n==1:
return 1
list_num = [1]
for i in range(1,n):
if list_num[-1] == len(list_num):
list_num.append(1)
else:
list_num[-1] +=1
len_l = len(list_num)

return len_l

print(egg_drop(3))