In [ ]:

    

import numpy as np
import math
import itertools
from memoized import memoized # pip3 install hg+https://bitbucket.org/gsakkis/memoized


    

In [ ]:

    

def parseTriStr(triStr, n):
    mat = np.empty((n, n))
    i = 0
    for line in triStr.strip().split("\n"):
        #print(np.asarray(list(map(int, line.split()))))
        row = np.asarray(list(map(int, line.split())))
        row.resize(n)
        row[i+1:] = -1e2
        mat[i,:] = row
        i += 1
    return mat

@memoized
def maxPathSum(x, y):
    if x > y:
        raise ValueError("x > y")
    if y == 0:
        return mat[y, x]
    elif x == 0: # Leftmost row, Can only move up
        return mat[y, x] + maxPathSum(x, y - 1)
    elif x == y: # Rightmost row, can only move up+left
        return mat[y, x] + maxPathSum(x - 1, y - 1)
    else:
        return max(mat[y, x] + maxPathSum(x, y - 1),
                   mat[y, x] + maxPathSum(x - 1, y - 1))

def totalMaxPathSum():
    assert mat.shape[0] == mat.shape[1]
    return max(maxPathSum(i, mat.shape[0] - 1) for i in range(mat.shape[0]))


    

In [ ]:

    

triStr = """
3
7 4
2 4 6
8 5 9 3
"""
mat = parseTriStr(triStr, 4)
totalMaxPathSum()


    

In [ ]:

    

triStr = """
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
"""
mat = parseTriStr(triStr, 15)
totalMaxPathSum()


    

In [ ]:

    

# Problem 67
import requests
mat = parseTriStr(requests.get("https://projecteuler.net/project/resources/p067_triangle.txt").text, 100)


    

In [ ]:

    

# Problem 67 solution
totalMaxPathSum()