Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Third 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 function works by looking 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.
Starting at bottom left row of pyramid 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, compare adjacent elements and
repeat as above. The pyramid is mutated as we progress.
Output: The maximum possible sum as an integer.
"""
copy_pyramid = list(list(row) for row in pyramid)
for row in range(len(copy_pyramid) - 1, 0, -1):
for col in range(0, row):
copy_pyramid[row - 1][col] += max(copy_pyramid[row][col],
copy_pyramid[row][col + 1])
return copy_pyramid[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"
Feb. 19, 2019
Comments: