Created
May 27, 2020 14:37
-
-
Save tonythomas01/1f66607960e5fe6e2cd4c7370ca0ab7a to your computer and use it in GitHub Desktop.
Two eggs problem, find the total tries to get to how many drops needs to be executed.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
Some solution to the 2 eggs problem. Given N floors, you find the first | |
floor and find how many steps you have to go up. | |
""" | |
import math | |
def find_roots_of_quadratic_equation(a, b, c): | |
""" | |
(-b +_ sqrt(b2 - 4ac))/2a | |
:param a: | |
:param b: | |
:param c: | |
:return: | |
""" | |
sqrt_b_square_minus_four_ac = math.sqrt(math.pow(b, 2) - 4 * (a * c)) | |
denominator = 2 * a | |
minus_b = (-1 * b) | |
return (minus_b + sqrt_b_square_minus_four_ac) / denominator, \ | |
(minus_b - sqrt_b_square_minus_four_ac) / denominator | |
def solve_two_eggs_quad_first_floor_equation(total_floors: int): | |
# x2 + x >= 2n | |
c = -2 * total_floors | |
root_a, root_b = find_roots_of_quadratic_equation(a=1, b=1, c=c) | |
if (math.pow(root_a, 2) + root_a) >= 2*total_floors: | |
return root_a | |
else: | |
return root_b | |
if __name__ == "__main__": | |
for n in [1, 2, 10, 23, 100]: | |
start_floor = round(solve_two_eggs_quad_first_floor_equation( | |
total_floors=n | |
)) | |
tries_for_this_n = 0 | |
floors_scanned = 0 | |
if n == 1: | |
# We dont really have to drop things here. | |
print( | |
f"n={n}, answer:{start_floor}, tries_for_this_n: {tries_for_this_n}") | |
continue | |
while floors_scanned < n: | |
additional_steps = (start_floor-tries_for_this_n) | |
if additional_steps < 0: | |
break | |
floors_scanned = floors_scanned + additional_steps | |
if floors_scanned > n: | |
floors_scanned = n | |
tries_for_this_n += 1 | |
print(f"n={n}, tries_for_this_n: {tries_for_this_n}, floors scanned:" | |
f" {floors_scanned}") | |
print(f"n={n}, answer:{start_floor}, tries_for_this_n: " | |
f"{tries_for_this_n} \n") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment