CODEWITHSUNDEEP
pythonpython-3.xalgorithm
Ümit Kara
Ümit Kara

Reputation: 95

Egg dropping puzzle

I'm working on this kata on codewars, which is extended version of famous two egg poblem. Goal is to find the critical floor height with given count of eggs and tries, attempts.

I look it for a little bit an find out that critical floor height is equal to sum of binomial coefficients until the given egg and try count:

Sum of Combination (Tries/i) where i is in range between 1 to Eggs + 1.

I use the comb function from scipy.special with exact=True parameter.

For relatively small numbers, like 477 eggs and 500 tries or 477 eggs and 10000 tires, program calculates very fast, under 0.05 secs. But there are very large checks like 4477 eggs and 10000 tries, which takes about 15 secs.

Is my approach wrong or could i done this calculations without getting execution timeout on codewars with this way?

Here is my script:

import scipy.special

# n: Eggs m: Tries
def height(n,m):
    ret = sum(scipy.special.comb(m,i, exact=True) for i in range(1,n+1))
    return int(ret)

Upvotes: 0

Views: 243

Answers (3)

Ümit Kara
Ümit Kara

Reputation: 95

I found out instead of using scipy, using loop is more efficient. And implemented this:

# n: Eggs m: Tries
def height(n,m):
    if n == 0 or m == 0:
        return 0
    if n > m:
        n = m
    counter,current,total = 1,1,0
    while counter <= n:
        d = (m+1-counter) * current // counter
        total,current,counter = total+d,d,counter+1
    return total

It is very fast compared to my previous attempt. On 4477,10000 this takes 0.02 secs to complete, previous one toke 16.97 secs to complete.

Upvotes: 0

gimix
gimix

Reputation: 3833

Let's do it by hand on very small numbers, say 5 and 7. And let me consider also the case of 0 items out of 7, whose value is 1 (you can always subtract 1 from the following if you don't want to include it)

  • The number of combinations for 0 items out of 7 is 7! / (0! (7-0)!) => 1
  • The number of combinations for 1 item is 7! / (1! (7-1)!) => 7
  • 2 items => 7! / (2! (7-2)!) => 21. Note we have a new factor 6, since (7-2)! * 6 == (7-1)!, and a new divisor 2 since 1! * 2 == 2!. At the previous iteration we had a factor 7 and a divisor 1 of course
  • 3 items => 35. New factor 5, new divisor 3
  • 4 items => 35 again. New factor and new divisor are both 4
  • 5 items => 21 again. Now new factor and new divisor are inverted (3 and 5)

Should we continue we would get

  • 6 items => 7
  • 7 items => 1.

So the total number of combinations up to 5 items out of 7 is 1 + 7 + 21 + 35 + 35 + 21 => 120. Note that if we count up to 7 we get 128, i.e. 2**7 - 1

So the simplest code can be:

def sum_of_combos(n,k):
    mult = k
    total = 1
    currval = 1
    for i in range(1,n+1):
        currval = (currval * mult) // i
        total += currval
        mult -= 1
    return total

>>> timeit("sum_of_combos(4477,10000)", globals=globals(), number=1000)
17.124391099999997

>>> timeit("sum_of_combos(8477,10000)", globals=globals(), number=1000)     
36.44438840000001

Is there room for optimizations? Yes, there is. For instance in the second example above instead of iterating 8477 times we could calculate 2**10000 and then subtract from that the first (10000 - 8477) values.

Upvotes: 1

Matt Timmermans
Matt Timmermans

Reputation: 59184

Since C(N,k) = N! / (k!(N-k)!),

We have C(N,1) = N

And for larger k: C(N,k) = C(N,k-1) * (N-k+1) / k

Calculating C(N,k) is much faster and easier if you start with C(N,k-1).

Upvotes: 2

Related Questions