Perfect Square uncategorized solution for Ghosts Age by goonbee - python coding challenges

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

Perfect Square solution in Uncategorized category for Ghosts Age by goonbee

from math import sqrt

def is_perfect_square(n):
    s = int(sqrt(n))
    return s*s == n

def is_fibonacci_number(n):
    return is_perfect_square(5*n*n + 4) or is_perfect_square(5*n*n - 4);
    
def checkio(opacity):
    opacity_counter = 10000
    for age in range(1, 5000):
        if opacity_counter == opacity:
            return age-1
        if is_fibonacci_number(age):
            opacity_counter -= age
        else:
            opacity_counter += 1

#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
    assert checkio(10000) == 0, "Newborn"
    assert checkio(9999) == 1, "1 year"
    assert checkio(9997) == 2, "2 years"
    assert checkio(9994) == 3, "3 years"
    assert checkio(9995) == 4, "4 years"
    assert checkio(9990) == 5, "5 years"

Aug. 23, 2015

Comments:

veky on Oct. 6, 2016, 8:13 a.m.
A very nice idea. :-) However, the implementation of isperfectsquare could be more robust by using round instead of int.

DahliaSR on Oct. 6, 2016, 6:58 p.m.
What's the reason isperfectsquare would be more robust when using round?

veky on Oct. 7, 2016, 6:56 a.m.
When the number to be checked is big, there is a chance for sqrt to not be exact. Since it returns a float (and works on the input as being a float), it's possible that it returns a slightly smaller value than the exact integer, and int would convert it to the one below. But round would probably still work in this case.

DahliaSR on Oct. 7, 2016, 5:10 p.m.
Makes sense. :P Thx

veky on Oct. 8, 2016, 5:49 a.m.
Of course, the true solution is <pre class='brush: python'>from checkio(mission=feed_pigeons, author=veky, name=optimal) import pbs def is_perfect_square(n): candidate = pbs(lambda x: x**2 <= n) return candidate**2 == n </pre> :-)

DahliaSR on Oct. 8, 2016, 5:34 p.m.
God Complex?

goonbee on Oct. 8, 2016, 8:10 p.m.
Burn!!!

veky on Oct. 9, 2016, 9:54 a.m.
Where? :-) You should be easier on your judgement, I think. :-)

veky on Oct. 9, 2016, 9:49 a.m.
Well... you know the say: complex is better than complicated. :-PPP <hr /> And now let's try to be serious. As you're surely aware, the big problem with almost all float-using algorithms is that they mysteriously break at some vague point when the numbers get too big. If there is a true solution, it uses integer arithmetic only. That being said, the obvious strategy is "find a candidate y, and then check whether y squared is equal to x". The only detail left is how do we find y. y should obviously have the property that if there's any number that when squared gives x, then the candidate does (Hilbert's epsilon-style). That combined with the requirement for y to be an integer gives a floored sqrt of x to be a natural candidate. That much was acknowledged by Martelli in his wonderful <a href="http://stackoverflow.com/questions/2489435/how-could-i-check-if-a-number-is-a-perfect-square">answer on SO</a>. The step he didn't take is to realize that the algorithm he used can be generalized to any nonconstant monotonically decreasing function from nat to bool. In this way, it becomes a pretty standard "binary search" algorithm, only in Platonic infinite realm (where instead of keeping values in some thisworldly array, you keep them in a mathematical mapping of ints). I did take that step, and if it makes me a god in your eyes, so be it. But regardless of my god status: pbs is a wonderfully useful function. There are already three or four missions on CiO that can be very naturally solved using it. Try it some time.

DahliaSR on Oct. 6, 2016, 6:59 p.m.
I like it, except for the for the fact that it takes too many iterations.

GitHub

0 %

PyCharm The Python IDE for Professional Developers. Enjoy productive Python, web and scientific development with PyCharm. Download it now!