Project Euler Problem 15 - Lattice Paths

Problem: Starting in the top-left corner of a 20×20 grid, and only being able to move right and down, how many routes are there to the bottom-right corner?

At first glance, this seems like a classic dynamic programming or pathfinding problem.

But I took a different approach - let the computer explore small cases, then use pattern recognition to crack the larger problem.

from itertools import permutations
import math
from math import factorial

dictionary_x = {}
list_x = [0, 1]
set_y = set()
for perm in permutations(list_x):
    if perm not in set_y:
        set_y.add(perm)
dictionary_x[1] = len(set_y)
set_y.clear()
list_x = [0, 1, 0, 1]
for perm in permutations(list_x):
    if perm not in set_y:
        set_y.add(perm)
dictionary_x[2] = len(set_y)
set_y.clear()
list_x = [0, 1, 0, 1, 0, 1]
for perm in permutations(list_x):
    if perm not in set_y:
        set_y.add(perm)
dictionary_x[3] = len(set_y)
set_y.clear()
list_x = [0, 1, 0, 1, 0, 1, 0, 1]
for perm in permutations(list_x):
    if perm not in set_y:
        set_y.add(perm)
dictionary_x[4] = len(set_y)
set_y.clear()
list_x = [0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
for perm in permutations(list_x):
    if perm not in set_y:
        set_y.add(perm)
dictionary_x[5] = len(set_y)

print(dictionary_x)

print((factorial(2 * 20))/pow((factorial(20)),2))

The Key Insight:

The code generated this sequence: {1: 2, 2: 6, 3: 20, 4: 70, 5: 252}

Good mathematicians will immediately recognise this as the central binomial coefficients sequence.

Me, not being a classically trained mathematician arrived at this solution via utilising the Online Encyclopedia of Integer Sequences.

Why does this work?

Each path through an n×n grid requires exactly:

• n moves right (represented as 1)

• n moves down (represented as 0)

The question becomes: "In how many unique ways can we arrange n ones and n zeros?"

This is a classic combinatorics problem: C(2n, n) = (2n)! / (n!)²

For the 20×20 grid: (40)! / (20!)² = 137,846,528,820 paths

Why I love this approach:

✅ Computational exploration builds intuition - By manually computing small cases, I could see the pattern emerge

✅ OEIS as a mathematical search engine - The ability to identify sequences from their first few terms is incredibly powerful

✅ Recognizing computational limits - The brute force permutation approach works for n≤5 but becomes infeasible quickly (40! permutations would take longer than the age of the universe!)

✅ Mathematical elegance - A complex pathfinding problem reduces to a simple closed-form solution

The Broader Lesson:

In data engineering, we often face similar choices: when to brute force, when to optimize, and when to step back and find a fundamentally better approach. Sometimes the best solution isn't a faster algorithm - it's recognizing the underlying mathematical structure.

#ProjectEuler #Mathematics #Python #ProblemSolving #OEIS #DataEngineering #Combinatorics #AlgorithmDesign