# Maximum path sum I

This problem is very similar to Problem 15. We build a DAG and then find the longest path taking in consideration the weight of each node. This algorithm solves Problem 67 too.

import networkx as nx
from urllib.request import urlopen

triangle_data = ""
try:
with open(file) as f:
except FileNotFoundError:
with urlopen("https://xojoc.pw/project-euler/" + file) as response:

return [[int(n) for n in line.split(' ')] for line in triangle_data[:-1].split('\n')]

def build_graph(triangle):
g = nx.DiGraph()

def T(n):
return n * (n + 1) // 2

def i(row, col):
return 1 + T(row) + col

for r in range(len(triangle)):
for c in range(r + 1):

for r in range(len(triangle)-1):
for c in range(r+1):
g.add_edge(i(r, c), i(r + 1, c))
g.add_edge(i(r, c), i(r + 1, c + 1))

return g

def longest_path(g):
sorted_nodes = list(nx.topological_sort(g))
first_node = sorted_nodes
node_weights = nx.get_node_attributes(g, 'weight')
cache = {}
for n in reversed(sorted_nodes):
max_weight = 0
for s in g.successors(n):
max_weight = max(cache[s], max_weight)
cache[n] = node_weights[n] + max_weight
return cache[first_node]

for f in ["18.txt", "67.txt"]:
print(longest_path(g))
1074
7273