# https://projecteuler.net/problem=81
from projecteuler.FileReader import file_to_2D_array_of_ints
# this problem uses a similar solution to problem 18, "Maximum Path Sum 1."
# this problem uses a diamond instead of a pyramid

matrix = file_to_2D_array_of_ints("p081.txt", ",")

y_max = len(matrix) - 1
x_max = len(matrix[0]) - 1

for y in range(y_max, -1, -1):
    for x in range(x_max, -1, -1):
        if y == y_max and x == x_max:
            continue
        elif y == y_max:
            matrix[y][x] += matrix[y][x + 1]
        elif x == x_max:
            matrix[y][x] += matrix[y + 1][x]
        else:
            matrix[y][x] += min(matrix[y][x + 1], matrix[y + 1][x])

print(matrix[0][0])