arithmetic uncategorized solution for Feed Pigeons by bunnychai - python coding challenges

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

arithmetic solution in Uncategorized category for Feed Pigeons by bunnychai

def checkio(number):
    k = int((6 * number) ** (1.0 / 3))
    if k * (k + 1) * (k + 2) > 6 * number:
        k -= 1
    t = k * (k + 1) / 2
    s = t * (k + 2) / 3
    return t + max(number - s - t, 0)

#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. 25, 2013

Comments:

Amachua on Dec. 25, 2013, 11:08 a.m.
Happy to see that a O(1) solution exists! :)

marshall.zheng on Dec. 25, 2013, 12:55 p.m.
it looks awesome but can you elaborate this solution?

bunnychai on Dec. 25, 2013, 2:42 p.m.
it finds the max k, such that in the k-th minute, all of the t pigeons could be fed with s portions (at least once). in the next minute, the remaining portions are fed to the same t pigeons first, then the final excess (if any) are for the new pigeons...

bryukh on Dec. 25, 2013, 11:01 p.m.
Mmm, the pure math. Super!

veky on Feb. 6, 2014, 11:17 a.m.
Not pure, this is using float arithmetic. Mine is pure. ;-)

RyanDagg on Dec. 29, 2013, 8 p.m.
Yay math.

nickie on Dec. 31, 2013, 2:01 p.m.
It seems that you had a clearer mind than me for simplifications... :-) Good job.

DiEvAl_0d0e0434e59e45f68684d0e on Dec. 31, 2013, 2:39 p.m.
<pre class='brush: python'>k = int((6 * number) ** (1.0 / 3)) if k * (k + 1) * (k + 2) > 6 * number: k -= 1 </pre> This was pretty smart. I didn't think of this, so I used wolfram alpha to find roots of the polynomial <pre class='brush: python'>P(x) = x*(x + 1)*(x + 2) - 6*n </pre> and then took an int() of the positive one. I didn't notice that <pre class='brush: python'>P((6*n) ** (1/3)) > 0 P((6*n) ** (1/3) - 1) < 0 </pre> so the root is between those 2 numbers, and the result is either <pre class='brush: python'>int((6*n) ** (1/3)) </pre> or <pre class='brush: python'>int((6*n) ** (1/3)) - 1 </pre>

CyroAvernus on Dec. 31, 2013, 6:35 p.m.
Can anyone explain please???

bunnychai on Jan. 1, 2014, 5:59 a.m.
see below or comments in DiEvAl's or nickie's code...

DiZ on Jan. 7, 2014, 12:11 a.m.
Nice solution (quite the same on my own, except I reasoned on k-1). Just a bit surprised by last line ; why not simply ;-) : <pre class='brush: python'>return max(t, number - s) </pre>

atrioom on Jan. 7, 2014, 2:45 p.m.
I'd never have come to this. Partly because I didn't know **, but mostly because it is beyond my intellectual grasp. Even reverse engineering it would take me probably hours. I should do it :P I have to say, my approach seems to be much much easier, and admittedly... uglier too.

pkstarstorm05 on Jan. 8, 2014, 7:57 p.m.
I right with you atrioom. I would have never come to this solution. I'm not a mathematician by training (I am a geneticist), so the reason I'm even bothering to post is because I'm interested to read what you guys think about more simple folk like myself even really needing to worry ourselves over not being able to arrive at this. My approach too is much longer, and much uglier (though I am proud of it!).

Dragonfly555 on Jan. 10, 2014, 2:57 p.m.
Didn't like the use of letters as variables. it's unreadable. a plus for you is that you didn't use a loop.

HighOrbit on Jan. 16, 2014, 8:33 p.m.
This is impressive. I can't read it at all though... Time to go learn me some maths...

seandor on Jan. 18, 2014, 3 a.m.
It seems very great:D

Uladzimir on Jan. 19, 2014, 5:46 p.m.
From one side it's cool, because your algorithm is O(1), but it's completely unreadable, so such solution only applicable for any "do and forget" tasks. :)

MasterSergius on Jan. 22, 2014, 11:17 a.m.
Fast solution, but it is opposite to Zen of Python. You have to comment at least, explain method and so on.

grutte_pier on Jan. 25, 2014, 2 p.m.
I don't agree at all with people saying the solution is not 'readable': learn your maths!

Alf_ on Jan. 30, 2014, 1:38 a.m.
what is k, s, t, 1, 2, 6 ?

bunnychai on Jan. 30, 2014, 7:51 a.m.
At k-th minute, t pigeons could be fed with s portions. 1, 2, 6 are just magic numbers derived from the arithmetic. should have more comments explaining stuff...

Alf_ on Jan. 30, 2014, 6:57 p.m.
for me is the most magic number here is 6 :)

Alf_ on Jan. 31, 2014, 2:43 a.m.
how did I manage to solve it without this number?

bunnychai on Jan. 31, 2014, 5:58 a.m.
6 is just a number coming from the sum of 1+2^2+3^2+...+n^2 in your code, the iteration is calculating this sum implicitly...

Alf_ on Feb. 1, 2014, 5:17 a.m.
Ok

UndeadMonkey on Jan. 30, 2014, 3:38 p.m.
Not very readable, but looks succinct. Perhaps better naming of the variables would have helped.

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.