Created
June 1, 2014 19:42
-
-
Save GuillermoPena/ecf6605e0dc263e0d84b to your computer and use it in GitHub Desktop.
CheckIO - Home Challenge 10 : Golden Pyramid (algorithm B)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment