"Golden Pyramid" Review

Let's look at a classical CS problem that was realised as the Checkio mission. I mean "Golden Pyramid" mission.

Consider a triangle of numbers. There is one number in the top of the triangle. On the next level - two numbers, then three and so on. You are start at the top and should down to the bottom of the triangle. For each step down you can move to on of two cell below current. And you "collect" (summarize) passed numbers. Your goal is find the maximum possible sum of numbers for all possible routes from top to bottom.

Recursive

The first obvious idea is to use recursion and calculate all paths from top to down. When we down to one level, then all below available cells are the new sub-triangle and we can start our function one more time for the new triangle. And so on until we reach the bottom. Simple and obviously.

def golden_pyramid(triangle, row=0, column=0, total=0):
    global count
    count += 1
    if row == len(triangle) - 1:
        return total + triangle[row][column]
    return max(golden_pyramid(triangle, row + 1, column, total + triangle[row][column]),
               golden_pyramid(triangle, row + 1, column + 1, total + triangle[row][column]))

But as we can see for the first level we run our function 2 times, then 4, 8, 16.... So as result we will get 2^N complexity and for the hundred-storied pyramid we need ≈ 10³⁰ function calls. Hm...

Dynamic Programming

But what if we will use dynamic programming method and break our problem to small pieces, which can be merged then. For simplicity look at the triangle upside down. Now look at the second (from new top) level. For each cell we can choose what is the best possible for this small three element triangle. Choose the best from the first level (early bottom), summarize with current cell value and write it. Now we have the new shorter triangle and can repeat this operation again and again. As result we have (N-1)+(N-2)+...2+1 operations and this is N² complexity.

def golden_pyramid_d(triangle):
    tr = [row[:] for row in triangle]  # copy
    for i in range(len(tr) - 2, -1, -1):
        for j in range(i + 1):
            tr[i][j] += max(tr[i + 1][j], tr[i + 1][j + 1])
    return tr[0][0]

Checkio Player Solutions

@gyahun_dash made the interesting realisation of dynamic programming method in "DP" solution. He used "reduce" to work at rows by pairs with accumulating and "map" to process each level.

from functools import reduce
​
def sum_triangle(top, left, right):
    return top + max(left, right)
​
def integrate(lowerline, upperline):
    return list(map(sum_triangle, upperline, lowerline, lowerline[1:]))
​
def count_gold(pyramid):
    return reduce(integrate, reversed(pyramid)).pop()

@evoynov used binary numbers to define all possible paths as combinations of 1 and 0 in "Binaries" solution. But this solution has the complexity as recursive method that was described early.

def count_gold(p):
    path = 1 << len(p)
    res = 0
    while bin(path).count("1") != len(p) + 1:
        s = ind = 0
        for row in range(len(p)):
            ind += 1 if row > 0 and bin(path)[3:][row] == "1" else 0
            s += p[row][ind]
        res = max(res, s)
        path += 1
    return res

And just for final little brain breaking puzzle (don't worry it's not too hard) with @nickie's in "Functional DP" one-liner which is only formally two-liners. Of course this is solution from "Creative" category and don't think that @nickie writes this for production. Just for fun.

count_gold=lambda p:__import__("functools").reduce(lambda D,r:[x+max(D[j],D[j+1])
for j,x in enumerate(r)],p[-2::-1],list(p[-1]))[0]

That's all folks. Propose your ideas for the next articles.

Valentin Bryukhanov aka Bryukh