CheckIO - Home Challenge 10 : Golden Pyramid (algorithm B)

checkio.1.10b.goldenPyramid.py

# CheckIO - Home Challenge 10 : Golden Pyramid (algorithm B)
# http://checkio.org

# Consider a tuple of tuples in which the first tuple has one integer 
# and each consecutive tuple has one more integer then the last. 
# Such a tuple of tuples would look like a triangle. 
# You should write a program that will help Stephan find the highest possible sum 
# on the most profitable route down the pyramid. 
# All routes down the pyramid involve stepping down and to the left or down and to the right.
# Input: A pyramid as a tuple of tuples. Each tuple contains integers.
# Output: The maximum possible sum as an integer.
# Precondition:
#     0 < len(pyramid) ≤ 20
#     all(all(0 < x < 10 for x in row) for row in pyramid)
            

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

if __name__ == '__main__':
    assert count_gold((
        (1,),
        (2, 3),
        (3, 3, 1),
        (3, 1, 5, 4),
        (3, 1, 3, 1, 3),
        (2, 2, 2, 2, 2, 2),
        (5, 6, 4, 5, 6, 4, 3)
    )) == 23, "First example"