py_0018_maximum_path_sum_i.py

# Solution of;
# Project Euler Problem 18: Maximum path sum I
# 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
# 
# NOTE: As there are only 16384 routes, it is possible to solve this problem
# by trying every route. However, Problem 67, is the same challenge with 
# a triangle containing one-hundred rows; it cannot be solved by brute force,
# and requires a clever method! ;o)
# 
# by lcsm29 http://github.com/lcsm29/project-euler
import timed


def fn_maxsum_from_bottom(n):
    def g(num):
        return int(0.5 * num * (num + 1))

    flat = [int(s) for s in s_triangle.split()]
    n_rows = next((i for i in range(int(1e100)) if g(i) >= len(flat)), None)
    t = [flat[g(i):g(i + 1)] for i in range(n_rows)]
    for i in range(n_rows - 2, -1, -1):
        for j in range(len(t[i])):
            t[i][j] += max(t[i + 1][j], t[i + 1][j + 1])
    return t[0][0]


s_triangle = '''
                            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
'''

if __name__ == '__main__':
    n = None
    i = 23_000
    prob_id = 18
    timed.caller(fn_maxsum_from_bottom, n, i, prob_id)