#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/challenges/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[0]
    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):