Solve Egg Dropping Puzzle problem in Python
So, guys today we will see How to solve the Egg Dropping Puzzle problem in Python. This is one of the best examples of the Dynamic Programming approach which helps us to get the optimum solution.
Let’s dive deep into the problem and move ahead and come up with a solution.
Solve Egg Dropping Puzzle problem in Python
Many of You might be knowing what the question is and what is being asked Right? But there may be some of them who might not know, So for them, I would like to elaborate on the problem
Given:
- Number of Floors
- Numbers of Eggs
An approach towards the Problem:
- Eggs that don’t break on falling can be used again.
- Egg once broke cannot be used again.
- Falling criteria are the same for all eggs.
- If an egg breaks on a certain floor then it’s understood that it will break if thrown from any higher floor.
- If an egg does not break after falling from a certain floor then it’s understood that it won’t break from any shorter floor.
Points to remember-
–> 1 Egg, N Floors = N Trials
–> N Eggs, 0 Floors = 0 Trials
–> N Eggs, 1 Floor = 1 Trials
Time Complexity: nk2
Code:
MAX_VALUE = 300 def eDrop(e, f): EF = [[0 for x in range(f+1)] for x in range(e+1)] for i in range(1, e+1): EF[i][1] = 1 EF[i][0] = 0 for j in range(1, f+1): EF[1][j] = j for i in range(2, e+1): for j in range(2, f+1): EF[i][j] = MAX_VALUE for k in range(1, j+1): ans = 1 + max(EF[i-1][k-1],EF[i][j-k]) if ans < EF[i][j]: EF[i][j] = ans return EF[e][f] e = 4 f = 16 print("Minimum number of trials in worst case with" + str(e) + "eggs and " + str(f) + " floors is " + str(eDrop(e, f)))
Output:
Minimum number of trials in worst case with 4 eggs and 16 floors is 5
Would you like to explore some more beautiful lines of codes? Here they are..Have a Look..!
Leave a Reply