Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Second solution in Clear category for Golden Pyramid by colinmcnicholl
def count_gold(pyramid):
"""Input: A pyramid as a tuple of tuples. Each tuple contains integers.
The function finds the highest possible sum from all possible routes
down the pyramid.
The method is to look at the pyramid from the bottom to the top,
adding "maximums" along the way. This will bubble the maximum total to
the top of the pyramid.
Output: The maximum possible sum as an integer.
"""
# First create a work copy list as a mutable data type is needed.
work = list(list(row) for row in pyramid)
# Now iterate over all the rows going from the bottom to the top
for row in range(len(work) - 1, 0, -1):
# Compare adjacent elements in current row, pick the "maximum", say x,
# and replace the element for the current column in the row above,
# say y, with the sum x + y. Move to next column in the current row,
# and repeat. The pyramid is mutated as we progress.
for col in range(0, row):
work[row - 1][col] += max(work[row][col], work[row][col + 1])
return work[0][0]
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
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"
assert count_gold((
(1,),
(2, 1),
(1, 2, 1),
(1, 2, 1, 1),
(1, 2, 1, 1, 1),
(1, 2, 1, 1, 1, 1),
(1, 2, 1, 1, 1, 1, 9)
)) == 15, "Second example"
assert count_gold((
(9,),
(2, 2),
(3, 3, 3),
(4, 4, 4, 4)
)) == 18, "Third example"
Jan. 23, 2019
