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

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 of the triangle below:

               75
              95 64
             17 47 82
            18 35 87 10
           20 04 82 47 65
          19 01 23 75 03 34
         88 02 77 73 07 63 67
        99 65 04 28 06 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 04 68 89 53 67 30 73 16 69 87 40 31
 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
"""

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

TRIANGLE = eval('''
[[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]]
''')



def solution(Triangle: list = TRIANGLE) -> tuple:
    '''
    >>> print(solution([[3],[7,4],[2,4,6],[8,5,9,3]]))
    (23, [3, 7, 4, 9])
    '''

    import copy
    triangle = copy.deepcopy(Triangle)
    
    high = len(triangle)  # top = 0, button = high - 1
    
    for layer in range(high-2, -1, -1):
        for i in range(len(triangle[layer])):
            triangle[layer][i] += max(triangle[layer+1][i], triangle[layer+1][i+1])
    
    zList = [list(zip(*x)) for x in list(zip(Triangle,triangle))]
    '''
    [[(75, 1074)],
     [(95, 995), (64, 999)],
     [(17, 818), (47, 900), (82, 935)],
     [(18, 704), (35, 801), (87, 853), (10, 792)],
     [(20, 686), (4, 640), (82, 766), (47, 731), (65, 782)],
     [(19, 666), (1, 614), (23, 636), (75, 684), (3, 660), (34, 717)],
     ...
     [(4, 4), (62, 62), (98, 98), (27, 27), (23, 23), (9, 9), (70, 70), (98, 98),
              (73, 73), (93, 93), (38, 38), (53, 53), (60, 60), (4, 4), (23, 23)]]
    '''
    
    for layer in range(1, high):
        zList[layer] = [x for x in zList[layer]
                        if x[1] == zList[layer-1][0][1] - zList[layer-1][0][0]]
    
    '''
    print(zList)
    
    [[(75, 1074)], [(64, 999)], [(82, 935)], [(87, 853)], [(82, 766)], [(75, 684)],
     [(73, 609)], [(28, 536)], [(83, 508)], [(32, 425)], [(91, 393)], [(78, 302)],
     [(58, 224)], [(73, 166)], [(93, 93)]]
    '''
    
    return triangle[0][0], [node[0] for layer in zList for node in layer]


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose = False)
    
    print(solution())
    # (1074, [75, 64, 82, 87, 82, 75, 73, 28, 83, 32, 91, 78, 58, 73, 93])