Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Golden Pyramid by yama_k_1101
import itertools
def count_gold(pyramid):
total_score = [[0] * (i+1) for i in range(len(pyramid))]
total_score[0][0] = pyramid[0][0]
for i,j in [sorted(c, reverse=True) for c
in itertools.combinations_with_replacement(range(len(pyramid)), 2) if c[0] != 0 or c[1] != 0]:
"""
Use the below code if you need maximum-value-path.
prev_idx, prev_score = max(
(j-1, total_score[i-1][j-1] if j > 0 else -1),
(j, total_score[i-1][j] if j < len(total_score[i-1]) else -1),
key=lambda v: v[1])
"""
prev_score = max(total_score[i-1][j-1] if j > 0 else -1,
total_score[i-1][j] if j < len(total_score[i-1]) else -1)
total_score[i][j] = prev_score + pyramid[i][j]
return max(total_score[-1])
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. 7, 2015
