The graph in my input (and I assume everyone else's too) is DAG so one can use transfer matrices for the first part (after severing connections going out of "out") and the second one topological sorting and just count paths between each node separately and multiply them. First part could be done much easily using the machinery of part2 but I wanted to use my favourite object transfer matrices for the solution. Second part runs in about 0.09 seconds.
from pathlib import Path
import networkx as nx
import numpy as np
cwd = Path(__file__).parent.resolve()
def parse_input(file_path):
with file_path.open("r") as fp:
data = list(map(str.strip, fp.readlines()))
nodes = [y for line in data for y in line.replace(':','').split(' ')]
M = np.zeros((len(nodes), len(nodes)))
for line in data:
from_node = line.split(':')[0]
to_nodes = line.split(': ')[-1].split(' ')
I0 = nodes.index(from_node)
I1 = [nodes.index(n) for n in to_nodes]
M[I0, I1] = 1
return M, nodes
def count_paths_between(ind0, ind1, M):
'''
counts paths by severing any outgoing connection from node ind1
and using transfer matrices. Stopping condition is having the
same positive number of paths for 10 cycles.
'''
vec = np.zeros((M.shape[0]))
vec[ind0] = 1
nhistory = []
A = M.T.copy()
A[:, ind1] = 0
A[ind1, ind1] = 1
counter = 0
while True:
vec = A@vec
nhistory.append(vec[ind1])
counter +=1
if len(nhistory)>10 and (len(set(nhistory[-10:]))==1 and nhistory[-1]!=0):
return nhistory[-1]
def count_paths_dag(G, source, target):
npaths = {node: 0 for node in G.nodes()}
npaths[source] = 1
for node in nx.topological_sort(G):
for nbr in G.successors(node):
npaths[nbr] += npaths[node]
return npaths[target]
def solve_problem1(file_name, path_nodes=None):
M, nodes = parse_input(Path(cwd, file_name))
if path_nodes is None:
npaths = count_paths_between(nodes.index("you"), nodes.index("out"), M)
else:
G = nx.from_numpy_array(M, create_using=nx.DiGraph(),
nodelist=nodes)
# assumed G is a DAG, below will raise error if not
sorted_nodes = list(nx.topological_sort(G))
sorted_path_nodes = sorted(path_nodes, key=sorted_nodes.index)
#make sure path nodes are not topoligically equivalent
for node1, node2 in zip(sorted_path_nodes[:-1], sorted_path_nodes[1:]):
assert nx.has_path(G, node1, node2)
npaths = np.prod([count_paths_dag(G, node1, node2) for node1, node2 in
zip(sorted_path_nodes[:-1], sorted_path_nodes[1:])])
return npaths
if __name__ == "__main__":
assert solve_problem1("test_input1") == 5
assert solve_problem1("input") == 431
assert solve_problem1("test_input2", ["svr","dac","fft","out"]) == 2
assert solve_problem1("input", ["svr","dac","fft","out"]) == 358458157650450