Egg dropping in worst case

Question

I have been trying to write an algorithm to compute the maximum number or trials required in worst case, in the egg dropping problem. Here is my python code

def eggDrop(n,k):
   eggFloor=[ [0 for i in range(k+1) ] ]* (n+1)
 for i in range(1, n+1):  
    eggFloor[i][1] = 1
    eggFloor[i][0] = 0
 for j in range(1, k+1):
    eggFloor[1][j] = j
 for i in range (2, n+1):
    for j in range (2, k+1):
        eggFloor[i][j] = 'infinity'
        for x in range (1, j + 1):
            res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x])
            if res < eggFloor[i][j]:
                eggFloor[i][j] = res

 return eggFloor[n][k]print eggDrop(2, 100)

```

The code is outputting a value of 7 for 2eggs and 100floors, but the answer should be 14, i don't know what mistake i have made in the code. What is the problem?

possible duplicate of [Generalised Two-Egg Puzzle](http://stackoverflow.com/questions/10177389/generalised-two-egg-puzzle) — Ken White, Feb 25 '15 at 18:00
See https://stackoverflow.com/questions/3974077 for a better exposition — Colonel Panic, Feb 25 '15 at 18:09

score 1 · Accepted Answer · answered Feb 25 '15 at 18:06

The problem is in this line:

eggFloor=[ [0 for i in range(k+1) ] ]* (n+1)

You want this to create a list containing (n+1) lists of (k+1) zeroes. What the * (n+1) does is slightly different - it creates a list containing (n+1) copies of the same list.

This is an important distinction - because when you start modifying entries in the list - say,

    eggFloor[i][1] = 1

this actually changes element [1] of all of the lists, not just the ith one.

To instead create separate lists that can be modified independently, you want something like:

eggFloor=[ [0 for i in range(k+1) ] for j in range(n+1) ]

With this modification, the program returns 14 as expected.

(To debug this, it might have been a good idea to write out a function to pring out the eggFloor array, and display it at various points in your program, so you can compare it with what you were expecting. It would soon become pretty clear what was going on!)

@overflow: Thanks! If you found it helpful, you may like to consider upvoting and/or accepting the answer :) — psmears, Feb 26 '15 at 08:55

Egg dropping in worst case

1 Answers1