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)

CodePudding user response：

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).

CodePudding user response：

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.