#!/usr/bin/env python
# coding: utf-8

# This problem is very similar to [Problem 15](https://xojoc.pw/challenges/euler/15). We build a DAG and then find the longest path taking in consideration the weight of each node.
# This algorithm solves [Problem 67](https://xojoc.pw/challenges/euler/67) too.

# In[5]:


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))


# In[ ]: