#Skip to menu

## Maximum path sum I

First read the problem description.

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

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

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):
g.add_node(i(r, c), weight=triangle[r][c])

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"]:
triangle = read_triangle(f)
g = build_graph(triangle)
print(longest_path(g))
1074
7273

Source code of the solution(s):