## Lattice paths

If we take each intersection as a node and each direction as an edge, then we can see that this is just a DAG. 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 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.

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