Dynamic speedy solution for Golden Pyramid by veky - python coding challenges

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

Dynamic solution in Speedy category for Golden Pyramid by veky

def count_gold(pyramid):
    p = tuple(map(list, pyramid))
    for i in reversed(range(len(p))):
        for j in range(i): p[i-1][j] += max(p[i][j:j+2])
    return p[0][0]

May 8, 2014

Comments:

SandeepManilal on May 18, 2014, 10:05 a.m.
Great solution!

veky on May 18, 2014, 12:16 p.m.
Thanks. Be sure to check out other solutions I made. ;-)

SandeepManilal on May 20, 2014, 3:52 p.m.
Hey, I think the in-line reply to comments via email doesn't work, I sent you a test reply today and dont think you got it. but Heres my response to this comment on May 18 Sandeep Manilal <a href="mailto:saapman@gmail.com">saapman@gmail.com</a> May 18 (2 days ago) to please-reply+7. Yes I have already. You are very active on the site. And a very skilled programmer IMHO. Great work man!

veky on May 20, 2014, 5:26 p.m.
Thanks. Unfortunately, following me will not do much good by itself, since I already solved most of the tasks. But look at the history. :-)

mandalorx on Feb. 23, 2015, 5:20 p.m.
There is no lambda, WHO ARE YOU AND WHAT HAVE YOU DONE WITH VEKY!!!!! :P

veky on Feb. 24, 2015, 2:27 a.m.
Of course there is no lambda. Where would you put it in this solution? As I said many times: contrary to popular myths, I'm not trying to solve every task here with a lambda. I'm just trying to solve every problem that can be best solved with a lambda, with a lambda. :-P This is just not one of them. (Of course, this is just my opinion - if you have a nice lambda solution, I'm eager to look at it.) lambda is just a tool, like any other. You should pick the right tool for the job. The fact that there are a lot of tasks here where the function sought can be best expressed as a lambda, doesn't mean that I'm some kind of lambda fanatic. I am a fanatic adherent of the principle that specific constructs are more valuable than general ones, when explaining algorithms. Every lambda "is" a def, but not every def "is" a lambda ("is" here meaning, "can be implemented as, without many contortions"). The fact that we have both means we should carefully pick which one expresses our intent most cleanly. Analogous example: for loop is more specific than while loop. Every for "is" a while, but not every while "is" a for. Does that mean we should write every loop with while? NO, for Python's sake. The very fact that for is more specific is incredibly valuable when reading code, when you see "ah, here it iterates through seq" rather than "here it repeats some stuff as long as i is less than length of seq". And more relevant to this discussion, some kind of "for fanatic" that would try to contort every loop to be a for loop, would be completely missing the point of having two looping constructs in Python. The fact of using for every time directly annihilates its usefulness as an indicator of "oh yes, this is one of those ordinary iterations". I hope that cleared it up. :-)

StefanPochmann on April 15, 2015, 1:04 a.m.
<blockquote> if you have a nice lambda solution, I’m eager to look at it </blockquote> How about <a href="http://www.checkio.org/mission/golden-pyramid/publications/StefanPochmann/python-3/shortest/">this short one</a> or <a href="http://www.checkio.org/mission/golden-pyramid/publications/StefanPochmann/python-3/short-fast-recursive/">this decently fast one</a>?

veky on April 15, 2015, 7:37 a.m.
Hmm, interesting - but recursive. Python is not particularly recursive-friendly language, for many reasons. I get that this is hard to write a nonrecursive looping expression solution here, but that's exactly why I said the above.

StefanPochmann on April 15, 2015, 11:20 a.m.
Do you know a good article about the recursion problems or can you name some? I like recursion and don't see a problem with it (except for very deep recursion, which we don't have here). And it's not hard to do this without recursion, how do you like <a href="http://www.checkio.org/mission/golden-pyramid/publications/StefanPochmann/python-27/short-fast-non-recursive-lambda/">this new one</a>? I think that's about as straight-forward as it gets, actually. Thanks for the extra motivation :)

veky on April 15, 2015, 2:30 p.m.
Yup, that's a nice one. Of course, the loop is then handled with reduce which Guido also doesn't like, but we can ignore him. :-] (Since I think this is just a readability / personal preference, not a hard design issue like recursion.) For a "good article", I think I can refer you to <a href="http://neopythonic.blogspot.com/2009/04/final-words-on-tail-calls.html,">http://neopythonic.blogspot.com/2009/04/final-words-on-tail-calls.html,</a> where Guido tries to explain a related thing, why Python won't ever have tail call optimization. Especially the comments are worth reading, like <a href="http://neopythonic.blogspot.com/2009/04/final-words-on-tail-calls.html?showComment=1240930560000#c4044704463007880383">this one</a>. :-) In short: Python call is not a goto. It always constructs a stack frame, which can be inspected and even changed (a bit) from the inside. When f calls g, the call of g doesn't "live at the same depth" as the call of f. Of course you might say that this only matters if the recursion depth is big enough, but I don't think so. Recursion (what the above linked comment called "Programmers who program like computer scientists") really steers you toward a different kind of solution. Very often, when you forbid yourself to use recursion, you get a nicer solution. One example is just what you wrote above. The other you can see in a great article by Ned: <a href="http://nedbatchelder.com/blog/201205/recursive_dogma.html">http://nedbatchelder.com/blog/201205/recursive_dogma.html</a> - note that he is against the simplistic "recursion bad" approach, but still his function became a lot nicer when he eliminated the recursion. I'd say it's not a coincidence, and if you read his post a bit between the lines, you'll see he has a similar opinion. As a commenter on his post writes: <blockquote> It is also a sad fact that far too often people try to solve simplistic problems using recursive techniques (usually badly expressed) when they are unnecessary and wasteful, as you have also shown.I don't have anything against recursion, but it pains me to see it used when people think it makes their code more 'elegant' or 'simpler'. It may make it a few lines shorter, its just sad that it is also going to eat all your memory and utilize 100 times as much cpu as it needs to unless you write it properly. So Python being 'bad' at implementing flabby, wasteful code is a bonus in my book. </blockquote> There are certain complicated truths, and there are useful simplifications we tell newbies. I'd say that if you have only one recursive call per call (as you do in the "decently fast" solution), a good rule of the thumb says recursion is never a good idea. It will benefit you to write a nonrecursive solution, even if the recursion is not very deep.

dunpealer on Sept. 6, 2015, 4:56 p.m.
As always with veky, good solution. Minor space optimization: we don't really need to copy the entire pyramid. For the dynamic programming, all we need is the last row, i.e. a list of length equal to the bottom row of the pyramid. See <a href="http://www.checkio.org/mission/golden-pyramid/publications/dunpealer/python-3/simple-minimal-elegant-solution/">example solution</a>.

veky on Sept. 6, 2015, 5:53 p.m.
Yes. The story is this: a long time ago, when dinosaurs have roamed the Earth, and lists have roamed the CiO :-DD, this task was specified as a function receiving list of lists. And in that distant world, the solution was obvious. Later, when someone changed the task so input was tuple of tuples, I just added the line 2 to my solution. :-)

andriiabaimov on Jan. 4, 2016, 10:11 a.m.
max(p[i][j:j+2]) trick was new for me, thanks!

veky on Jan. 4, 2016, 7:37 p.m.
<pre class='brush: python'>max(p[i][j:][:2]) </pre> is also possible, unrepeating the `j` at the expense of double slicing. :-)

Look up in the Dict()

0 %

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