#!/usr/bin/env python
# coding: utf-8
# If we take each intersection as a node and each direction as an edge, then we can see that this is just a [DAG](https://en.wikipedia.org/wiki/Directed_acyclic_graph).
# To count the possible paths from start to end we can observe than the number of paths of a node is the sum of the number of paths of its children. We do a [topological sort](https://en.wikipedia.org/wiki/Topological_sorting) of the graph and starting from the bottom right corner we go back calculating the number of paths. Since for each $v$ the paths of its children have already been calculated, we need to just sum them.
# In[3]:
import networkx as nx
def build_graph(n):
g = nx.DiGraph()
def i(col, row):
return n * (row - 1) + col
for c in range(1, n + 1):
for r in range(1, n + 1):
if c != n:
g.add_edge(i(c, r), i(c + 1, r))
if r != n:
g.add_edge(i(c, r), i(c, r + 1))
return g
# Kahn's algorithm
def topological_sort(g):
g = g.copy()
sorted_nodes = []
without_incoming_edges = [1]
while without_incoming_edges:
n = without_incoming_edges.pop()
sorted_nodes.append(n)
edges_to_remove = []
for s in g.successors(n):
edges_to_remove.append((n, s))
if g.in_degree(s) == 1: # the edge n -> s will be removed, so we check for 1 instead of 0
without_incoming_edges.append(s)
for (n, s) in edges_to_remove:
g.remove_edge(n, s)
return sorted_nodes
def count_paths(g, f, t):
sorted_nodes = topological_sort(g)
cache = {t: 1}
for n in reversed(sorted_nodes[:-1]):
count = 0
for s in g.successors(n):
count += cache[s]
cache[n] = count
return cache[f]
nodes = 20 + 1
g = build_graph(nodes)
count_paths(g, 1, nodes * nodes)