"""
Problem 67: https://projecteuler.net/problem=67

By starting at the top of the triangle below and moving to adjacent numbers on
the row below, the maximum total from top to bottom is 23.
3
7 4
2 4 6
8 5 9 3
That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom in triangle.txt (right click and
'Save Link/Target As...'), a 15K text file containing a triangle with
one-hundred rows.
"""


# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/22
'''


def inputTriangle(filename: str = 'p067_triangle.txt') -> list:
    import re

    triangle = []
    with open(filename, 'r') as tf:
        for line in tf:
            row = line.strip().lstrip('0')
            if not row:  # blank line
                continue
            row = re.compile(r'\s+[0]*').sub(',', row)  # replace '___000'
            row = eval('[' + row + ']')
            if triangle and len(row) - len(triangle[-1]) != 1:
                raise ValueError(
                    f'{line} must one more data than the last row.')
            else:
                triangle.append(row)

    return triangle


def maxTotal(triangle: list = inputTriangle()) -> int:
    '''
    >>> print(maxTotal([[3],[7,4],[2,4,6],[8,5,9,3]]))
    23
    '''
    high = len(triangle)
    if high == 0:
        raise ValueError('triangle is empty.')
    for i in range(0, high):
        if len(triangle[i]) != i+1:
            raise ValueError('triangle is illegal.')

    if high == 1:
        return triangle[0][0]

    import copy
    res = copy.deepcopy(triangle)

    for row in range(high-2, -1, -1):
        for col in range(len(res[row])):
            res[row][col] += max(res[row+1][col], res[row+1][col+1])

    return res[0][0]


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print(maxTotal())

    # 7273