Simple DP clear solution for Golden Pyramid by nickie - python coding challenges

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

Simple DP solution in Clear category for Golden Pyramid by nickie

def count_gold(pyramid):
    """
    A simple dynamic programming approach, O(n^2) time, O(n) space.
    """
    for i, row in enumerate(pyramid):
        if i == 0:
            curr = [row[0]]
        else:
            prev = curr
            def sofar(j, x):
                if j == 0:
                    return prev[j]
                elif j == i:
                    return prev[i-1]
                else:
                    return max(prev[j-1], prev[j])
            curr = [x + sofar(j, x) for j, x in enumerate(row)]
    return max(curr)

April 30, 2014

Comments:

timur.hamzin on June 30, 2014, 1 p.m.
Smart, didn't think of it! Compared every possible "trajectory" from the top down instead.

tassio on July 12, 2014, 12:11 p.m.
If you consider that the size of the problem is the amount k of numbers in the pyramid, then the algorithm takes O(k) time and O(sqrt(k)) space, no?

nickie on July 13, 2014, 8:14 p.m.
Yes. I implicitly took the size 'n' to be the length of the pyramid's base (or height). If your size is 'k', the number of elements in the pyramid, then k = O(n^2) and you're absolutely right.

StackOfPancakes on July 25, 2014, 7:07 a.m.
I wish an uncommented solution that consists of a huge amount of single letter variables and nested function definitions wasn't upvoted. This isn't clear or educational.

nickie on Feb. 6, 2015, 10:36 p.m.
If you want comments, I'll refer you to the solution published by <a href="http://www.checkio.org/mission/golden-pyramid/publications/zero_loss/python-3/first/?ordering=most_voted">zero_loss</a>. The idea is identical, the code only differs.

sumeet.lintel on Dec. 17, 2014, 2:28 p.m.
It is Simple. But recursive way would have reduced time to n!

nickie on Feb. 6, 2015, 10:33 p.m.
Sorry, I don't understand this. What recursive way are you suggesting? <a href="http://www.checkio.org/mission/golden-pyramid/publications/sumeet.lintel/python-27/recursive-approach/">Your recursive solution</a> takes exponential time, not linear. Think about it: each recursive call generates two recursive calls. (Moreover, it takes a lot of space too, as line 8 in each recursive call makes a copy of the pyramid, but this is not the main issue here.) That's what <a href="http://en.wikipedia.org/wiki/Dynamic_programming">dynamic programming</a> is for: to avoid re-computing the same things again and again when you have overlapping subproblems.

TheBmo on Feb. 6, 2015, 6:23 p.m.
This isn't clear at all. Isn't that function being declared in memory every iteration also? I don't get why you would do that.

nickie on Feb. 6, 2015, 10:24 p.m.
Are we talking about clarity or about something else? I claim that my solution is clear, on the assumption that the reader knows what dynamic programming is. Whether the function is "declared in memory" (whatever that means) in every iteration, this is something implementation specific and has nothing to do with clarity. I would hate to believe that a Python implementation would declare this in every iteration; `sofar` is just a function closure, capturing the value of `i`. I am doing it this way (i.e., I am defining a function closure) because it helps clarity. In every new line (`curr`), the value of each element is the value of the corresponding element in the pyramid (`x`) plus the best possible way to get there, which is given by function `sofar`. Now that I look at this again, `sofar` does not use parameter `x`, it must have remained from an older version of my program. If this is what confused you, I apologise. Here's a better version of lines 10-17: <pre class='brush: python'> def sofar(j): if j == 0: return prev[j] elif j == i: return prev[i-1] else: return max(prev[j-1], prev[j]) curr = [x + sofar(j) for j, x in enumerate(row)] </pre>

Look up in the Dict()

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.