Nine, One, MinusOne speedy solution for Numbers Factory by hrvoje - python coding challenges

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

Nine, One, MinusOne solution in Speedy category for Numbers Factory by hrvoje

def factorize(n, t=[]):
    for i in range(9,1,-1):
        if n % i == 0:
            n, t = n/i, t+[str(i)]
            return factorize(n, t)
    return (n, t)
            

def checkio(number):
    residue, factors = factorize(number, [])
    return int(''.join(sorted(factors))) if residue==1 else 0

July 9, 2015

Comments:

veky on July 19, 2015, 2:02 a.m.
Algorithm is cool. Python, not so much. <ol> <li>Flat is better than nested => loop is better than recursion. Seriously, that golfing has damaged your brain. ;-P</li> <li>List is not the only accumulator.</li> <li>by sorted you mean reversed. ;-)</li> <li>False == 0</li> </ol> Keeping all of it in mind, here is your algorithm in True Python: <pre class='brush: python'>def checkio(n, t=''): for i in range(9, 1, -1): while not n%i: n, t = n//i, str(i)+t return n==1 and int(t) </pre>

hrvoje on July 19, 2015, 10:11 a.m.
Damn, that's really much more elegant and simple. And half the size! :-P

veky on July 19, 2015, 12:12 p.m.
You see now why golfing is counterproductive, even if you're only trying to produce not too long code? It steers your mind towards recursion, which is not really a Pythonic way - and it makes you forget about the loops, which are often much more natural. Once someone asked me don't I hate Python's recursion limit, and how can I live with it. I said: there are two main types of recursive functions---those that call themselves only once per call, and those that call themselves two or more times per call. First ones (such as yours here) are not really recursive: those are simply loops written in a convoluted way. For them, recursion limit is good, since it forces you to write your code in a normal and Pythonic way once you start to hit bigger inputs. Python not having tail call optimization is for the same reason. Consenting (and stubborn) adults can always increase recursion limit at their own risk, or manage their frames by hand. Second ones are more common when bruteforcing some exponential algorithms, but there the recursion depth limit is irrelevant, since recursion width will crush you much sooner. 2**1000 is a horribly big number, much bigger than the number of particles that ever existed in the universe, and there is simply no way you could survive with a tree this deep, even if Python let you. [Of course, there is a third type, that rarely calls itself two times, and usually calls itself only one time. But if even 5% of calls make more than one recursive call, it's still hopelessly wide. For functions calling itself only once in 99% of cases, recursionlimit (and nonoptimization of tail calls) is a genuine problem. But I never encountered such a problem in practice, and if I did, I'd probably just make my own stack for it instead of using Python's.]

hrvoje on July 19, 2015, 9:22 p.m.
I was never a big fan of recursion, with golf or without it. However, I tend to experiment a little and solve things in a way I wouldn't usually go for if it was a real world assignment. It also taught me a lot about recursions, since I always avoided them. Would I ever consider writing a recursive function in real life? Highly doubt it, there would have to be a really good reason to do that. Learning includes moving away from the comfort zone sometimes. I'll get better with time (hopefully). I love the last line of your solution :))

veky on July 20, 2015, 3:56 a.m.
<blockquote> Learning includes moving away from the comfort zone sometimes. </blockquote> Of course. Then take LISP and go medieval on your dark functional desires. Don't violate the innocent language that's not made for such exhibitions. It's as if you said that writing <pre class='brush: python'>i = 0 p = 0 while 1: e = a[i] p = p + e i = i + 1 if i == len(a): break </pre> to sum elements of a is "moving away from the comfort zone". It really doesn't serve any purpose, except showing how you can write assembler code in Python (and even that's not completely faithful, since it lacks goto). <blockquote> I was never a big fan of recursion </blockquote> It's not surprising, if you didn't realize before the strong divide brtween two types of recursive functions I talked above (let's call them monocursion and polycursion:). Monocursion is in most cases just a simple loop in disguise. It might require a bit of reorganizing your code if it's not a tail call, but such reorganizing usually pays off since it makes your code easier to follow. My point is that monocursion shouldn't be written in Python (in the same sense that the above snippet for summing `a` shouldn't be written in Python - it shows the language in the wrong light, and it masks subtle bugs - see if you can find one;). On the other hand, polycursion is a perfectly natural way of solving problems, in Python or elsewhere (except FORTRAN IV:)). Many times I saw you struggling with a task that's almost trivially solvable polycursively, and it's obvious polycursion is out of your comfort zone. You should practice it, of course. But writing monocursive functions and thinking it somehow enhances your understanding is childish. <blockquote> Would I ever consider writing a recursive function in real life? </blockquote> I did write a polycursive function professionally. It is currently part of codebase for a banking software I write, and it's passed code review as really a natural way to solve the problem of reflecting class hierarchies in the database. Since you usually write an abstract class only if you have in mind at least 2 subclasses (having something in common), it's obvious that it's polycursive. It's also obvious that the depth is really small (at most 3 currently), and it could have been written by separating the levels, but it would just confuse the reader of the code. <pre class='brush: python'>Simple is better than complex. Complex is better than complicated. </pre> in this instance translates as <pre class='brush: python'>Loop is better than monocursion. Polycursion is better than repeating yourself. </pre> ;-) By all means, go and try solving some tasks with polycursion. But don't confuse it with monocursion (at least in Python - as I said, you can use a TCOd language that doesn't make such a distinction).

hrvoje on July 21, 2015, 1:08 p.m.
It's not easy to choose the correct algorithm, spouse, shoes or mattress. :-))) An example or two would be helpful in describing what you'd consider a valid case for using recursion. No need to give complete solutions, just a description of a problem or two for which recursion is the right choice would be helpful. As for the subtle bugs, maybe you're thinking of referencing a[i] without knowing if it's empty or not, which can break in certain conditions?

veky on July 21, 2015, 2:34 p.m.
I think you haven't understood, my criteria is very simple. From the start of executing function f till its return to the caller, how many times is f called? If it's only (zero or) once, that's monorecursive function, and it should be written as a loop. If it's (usually) twice or more times, that's polyrecursive function, and there the recursion might be justified. Example of a monorecursive function, you have above: every . For an example of polyrecursive function, see Unfair dice. :-) <blockquote> As for the subtle bugs, maybe you’re thinking of referencing a[i] without knowing if it’s empty or not, which can break in certain conditions? </blockquote> Yes. "certain conditions" being "`a` being empty". :-)

hrvoje on July 21, 2015, 2:49 p.m.
So, recursions should be branchy, not loopy? :))

veky on July 21, 2015, 9:25 p.m.
Yup. In other words, if depth is a problem to you, then you're doing it wrong. :-)

GitHub

0 %

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