Do the math, O(1) speedy solution for Feed Pigeons by nickie - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

Do the math, O(1) solution in Speedy category for Feed Pigeons by nickie

def checkio(n):                               # explanation follows...
    p = lambda t: t * (t+1) // 2
    q = lambda t: (t*t*t + 3*t*t + 2*t) // 6
    h = 9*n*n - 1/27
    R = 3*n + h**(1/2)
    T = 3*n - h**(1/2)
    X1 = R**(1/3) + T**(1/3) - 1
    w = int(X1)
    return p(w) + max(0, n-q(w)-p(w))

"""
   p(t): number of of pigeons at round t
   p(1) = 1
   p(n) = p(n-1) + n

   p(n) = 1 + 2 + 3 + ... + n = n*(n+1)/2

   q(t): number of portions to feed all pigeons in the first t rounds
   
   q(t)
 = \sum_{i=1}^{n} p(i)
 = 1/2 * \sum_{i=1}^{n} n^2 + 1/2 * \sum_{i=1}^{n} n
 = 1/2 * n * (n+1) * (2*n+1) / 6 + 1/2 * n * (n+1) / 2
 = 1/12 * (2*n^3 + 3*n^2 + n) + 1/4 * (n^2 + n)
 = 1/12 * (2*n^3 + 3*n^2 + n + 3*n^2 + 3*n)
 = 1/12 * (2*n^3 + 6*n^2 + 4*n)
 = 1/6 * (n^3 + 3*n^2 + 2*n)

Suppose we start with N portions and w full rounds of pidgeons are fed:

    q(w) <= N
<=> w^3 + 3*w^2 + 2*w - 6*N <= 0

Single real root is calculated by:

    a = 1, b = 3, c = 2, d = -6*N

    f = (3*c/a - b*b/a/a)/3
    g = (2*b*b*b/a/a/a - 9*b*c/a/a + 27*d/a)/27
    h = g*g/4 + f*f*f/27
    R = -(g/2) + h**(1/2)
    S = R**(1/3)
    T = -(g/2) - h**(1/2)
    U = T**(1/3)
    X1 = S + U - b/3/a

theferore:  w = int(X1)

We can feed p(w) pidgeons and we are left with N - q(w) portions for round w+1.
But the first p(w) pidgeons in round w+1 have already been fed.
So, if N - q(w) > p(w), we can feed N - q(w) - p(w) more pidgeons.
"""

#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
    assert checkio(1) == 1, "1st example"
    assert checkio(2) == 1, "2nd example"
    assert checkio(5) == 3, "3rd example"
    assert checkio(10) == 6, "4th example"

Dec. 31, 2013

Comments:

bunnychai on Dec. 31, 2013, 2:15 p.m.
~cool~

A_bak_cfff596eda7840afb01132b2 on Jan. 8, 2014, 9:02 p.m.
A properly documented solution!

veky on Feb. 6, 2014, 11:22 a.m.
You could have: <ul> <li>used p in defining q, that way it would be much more clear those are binomial coefs</li> <li>extracted square root of h in place, instead of twice later</li> <li>written the return value as max(p(w), n - q(w))</li> </ul> Otherwise, nice solution. And yes, I appreciate documentation, so I can point people to it when they ask me what I meant. :-))

tommycarstensen on April 24, 2015, 2:19 p.m.
O(1) :) You are the king of checkio!

Adamzma on Dec. 31, 2015, 2:35 p.m.
nice one

BK024 on Jan. 23, 2016, 5:02 p.m.
You say "speedy" but it is one of the slowest solutions according to my timeit test. The test I have done: <pre class='brush: python'>def checkio(n): p = lambda t: t * (t+1) // 2 q = lambda t: (t*t*t + 3*t*t + 2*t) // 6 h = 9*n*n - 1/27 R = 3*n + h**(1/2) T = 3*n - h**(1/2) X1 = R**(1/3) + T**(1/3) - 1 w = int(X1) return p(w) + max(0, n-q(w)-p(w)) if __name__ == '__main__': import timeit T = [] T.append(timeit.timeit("checkio(1)", setup="from __main__ import checkio")) print(T[-1]) T.append(timeit.timeit("checkio(2)", setup="from __main__ import checkio")) print(T[-1]) T.append(timeit.timeit("checkio(3)", setup="from __main__ import checkio")) print(T[-1]) T.append(timeit.timeit("checkio(4)", setup="from __main__ import checkio")) print(T[-1]) T.append(timeit.timeit("checkio(5)", setup="from __main__ import checkio")) print(T[-1]) T.append(timeit.timeit("checkio(6)", setup="from __main__ import checkio")) print(T[-1]) T.append(timeit.timeit("checkio(7)", setup="from __main__ import checkio")) print(T[-1]) T.append(timeit.timeit("checkio(8)", setup="from __main__ import checkio")) print(T[-1]) T.append(timeit.timeit("checkio(9)", setup="from __main__ import checkio")) print(T[-1]) T.append(timeit.timeit("checkio(10)", setup="from __main__ import checkio")) print(T[-1]) print("average: {}".format(sum(T) / 10)) </pre> The output: 1.3883340559987118 1.4452293939993979 1.46020696999949 1.4994767119987955 1.4468806470013078 1.466870480999205 1.4384062770004675 1.4530673539993586 1.459077490000709 1.4514266120004322 average: 1.4508975992997875 Compared to for instance: <pre class='brush: python'>def checkio(number): minutes = 0 pigeons = 0 portions = 0 while True: minutes += 1 pigeons += minutes portions += pigeons if portions > number: pigeons -= minutes new_pigeons_left = portions - number if new_pigeons_left in range(1, minutes+1): pigeons += (minutes - new_pigeons_left) break return pigeons if __name__ == '__main__': import timeit T = [] T.append(timeit.timeit("checkio(1)", setup="from __main__ import checkio")) print(T[-1]) T.append(timeit.timeit("checkio(2)", setup="from __main__ import checkio")) print(T[-1]) T.append(timeit.timeit("checkio(3)", setup="from __main__ import checkio")) print(T[-1]) T.append(timeit.timeit("checkio(4)", setup="from __main__ import checkio")) print(T[-1]) T.append(timeit.timeit("checkio(5)", setup="from __main__ import checkio")) print(T[-1]) T.append(timeit.timeit("checkio(6)", setup="from __main__ import checkio")) print(T[-1]) T.append(timeit.timeit("checkio(7)", setup="from __main__ import checkio")) print(T[-1]) T.append(timeit.timeit("checkio(8)", setup="from __main__ import checkio")) print(T[-1]) T.append(timeit.timeit("checkio(9)", setup="from __main__ import checkio")) print(T[-1]) T.append(timeit.timeit("checkio(10)", setup="from __main__ import checkio")) print(T[-1]) print("average: {}".format(sum(T) / 10)) </pre> The output: 0.5126792259998183 0.5175171369992313 0.49145561200020893 0.5071757650002837 0.5116248350004753 0.5080509600011283 0.5755265309999231 0.5735033269993437 0.5504023440007586 0.5646204279983067 average: 0.5312556164999478 My environment: <blockquote> Python 3.4.3+ (default, Oct 14 2015, 16:03:50) [GCC 5.2.1 20151010] on linux </blockquote> So maybe not so speedy?

nickie on Jan. 25, 2016, 6:43 p.m.
Are you kidding? Try `checkio(1000000000)` (one billion) and let's talk then. (I know the task description says N<10**5 but please entertain me.) If you want to play with such small numbers, I guess the "speediest" solution is something like: <pre class='brush: python'>def checkio(N): return [0, 1, 1, 2, 3, 3, 3, 3, 4, 5, 6, 6, 6, 6, 6, 6, 6][N] </pre> that is, having the results precomputed. If you don't understand how algorithmic complexity works and what's the fuss about my O(1) vs. your O(N), I suggest an <a href="http://discrete.gr/complexity/">introductory article</a> written by my good old student dionyziz.

veky on Jan. 25, 2016, 7:47 p.m.
While you're completely correct in your reply to BK024, in the interest of completeness, try `checkio(9**999)`. :-P And before you say it's not fair, take a look at <a href="http://www.checkio.org/mission/feed-pigeons/publications/veky/python-3/optimal/?ordering=most_voted">this</a>. ;-) Of course, two of us have already had this discussion. But I think it might be useful to reiterate some points of it, for new listeners. :-)

nickie on Jan. 31, 2016, 7:19 p.m.
OK, point taken. Explanation follows, obviously not for veky but for future readers. My `checkio(9**999)` gives: `OverflowError: int too large to convert to float`. This is reasonable because, even though integer numbers in Python can get arbitrarily large, my program converts these large integers to floating point numbers for subsequent calculations. This is allowed up to some maximum value, which is exceeded in this case. Regardless of this, I would bet that the result of my `checkio` is wrong for large enough values, because this conversion to floating point numbers inevitably looses accuracy. On the other hand, you can have solutions such as <a href="http://www.checkio.org/mission/feed-pigeons/publications/veky/python-3/optimal/">the one brilliantly coded</a> by veky (which I had probably missed at that time). It's possible to do pretty much the same calculations without involving floating point numbers at all. Veky finds the root of the equation that gives the solution to this problem in logarithmic time, using a variation of binary search. Logarithmic time would be required anyway for manipulating large integer numbers, so this solution is indeed optimal.

veky on Jan. 31, 2016, 8:18 p.m.
Just a nitpick: when discussing complexity, it is usually done as the function mapping size of input to size of computation. Size of computation is naturally number of steps (while the notion of a "step" is not really well defined in higer programming languages, but that's beside the point), but size of input is often misunderstood when the input is a number. If input were a string consisting of ASCII letters, it is obvious that its length would be the criteria, not a value of a number it represents. We should probably stick to the same convention when discussing numeric algorithms. After all, naive factoring is hard not because it's linear, but because it's exponential. And Euclid's algorithm is fast because it's linear, logarithmic would probably be too much to ask. :-) So, pbs is linear. But it is really fast - you need linear time just to read all of the input, after all. :-)

ljy95135 on May 9, 2016, 5:50 a.m.
Awesome! It's the solution I want to find!

Ice Base

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.