#Skip to menu

Lattice paths

First read the problem description.

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

See what people say about this article.


Source code of the solution(s):