p018.py

################################################################################
#                            P18: Maximum path sum I                           #
################################################################################
#                                                                              #
#       Find the maximum total from top to bottom of the triangle below.       #
#                                                                              #
################################################################################
#                       Problem found at projecteuler.net                      #
#                                Author: ncfgrill                              #
################################################################################

from copy import deepcopy

tri = [[75],
       [95,64],
       [17,47,82],
       [18,35,87,10],
       [20,4,82,47,65],
       [19,1,23,75,3,34],
       [88,2,77,73,7,63,67],
       [99,65,4,28,6,16,70,92],
       [41,41,26,56,83,40,80,70,33],
       [41,48,72,33,47,32,37,16,94,29],
       [53,71,44,65,25,43,91,52,97,51,14],
       [70,11,33,28,77,73,17,78,39,68,17,57],
       [91,71,52,38,17,14,91,43,58,50,27,29,48],
       [63,66,4,68,89,53,67,30,73,16,69,87,40,31],
       [4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]]

sum_tri = deepcopy(tri)

for l in range(len(sum_tri) - 1):
    for r in range(len(sum_tri[l])): sum_tri[l][r] = 0

l = len(sum_tri) - 1
while l > 0:
    for r in range(len(sum_tri[l])):
        if r < len(sum_tri[l]) - 1:
            s = sum_tri[l][r] + tri[l-1][r]
            if s > sum_tri[l-1][r]: sum_tri[l-1][r] = s
        if r > 0:
            s = sum_tri[l][r] + tri[l-1][r-1]
            if s > sum_tri[l-1][r-1]: sum_tri[l-1][r-1] = s

    l -= 1

print('Maximum total:', sum_tri[0][0])