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 () 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 () below!
You can also find further discussion and get answers to your questions over in #get-help.
Agree with a comment or answer? Like () to up-vote the contribution!
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.
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.
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.
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))
#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
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
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()
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
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))
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)
) below.
) to up-vote the contribution!