Solve Egg Dropping Puzzle problem in Python

By Ronak Jethava

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:

1. Number of Floors
2. 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: nk²

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