Project Euler

Problem

This problem comes from Project Euler 15

Problem

Starting in the top left corner of a 2 × 2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20 × 20 grid?

Solution 1: Combinatorics

We can use combinatorics to solve this question! If we look at the grid, we always make a total of four moves in some combination of moving right and moving down. Of the four possible moves, we should choose two of them to be in a particular direction, say, towards the right. With that, we get “4 choose 2.”

This means that there are six possible combinations of moving rightward from the four moves we have. That is, RRxx, RxRx, RxxR, xRxR, xRRx, and xxRR. I used ‘x’ to help emphasize the rightward movements, but we know that ‘x’, by default here, means downwards.

For a 20 × 20 grid, we have forty moves, so we should choose 20 of them to be in a particular direction.

Solution 2: Dynamic Programming

Seeing that Project Euler produces programming challenges, I figured that this is likely the intended solution compared to the combinatorics one.

Below is the minimum amount of code required (for my solution) to solve the problem. It runs slowly, but we’ll optimize it later.

# Project Euler: Problem 15
# Lattice paths

def paths(m, n, ran=False):

    # Edge cases
    if m == 0 and n > 0:
        return n
    
    if m > 0 and n == 0:
        return m
    
    if m <= 0 or n <= 0:
        return 0
        
    # Normal operation
    if not ran:
        m += 1
        n += 1

    if m == 1 or n == 1:
        return 1

    return paths(m-1, n, True) + paths(m, n-1, True)

print(paths(20, 20))

Movements

In the problem, we don’t move in the squares but along the edges.

In the 2 × 2 grid example given, we can make six moves. What about other grids? Such as a

• 1 × 1 grid? We can make two moves: DR, RD.
• 0 × 1 “grid”? Actually, this is just a single line, but we can make one move.
• 0 × 2 “grid”? Similar to the 0 × 1 “grid,” but we can move twice in one direction.
• 0 × 0 “grid”? This is just a point, so there are no moves.

This shows that for $m \times n$ grid, we have $m$ moves in one direction and $n$ moves in another direction.

Recursion

This program uses recursion to solve the problem. Let’s see how.

Let’s look at the example 2 × 2 grid and pick a direction to move, say the right. By doing so, we are actually trying to solve a 2 × 1 grid! Now, if we were to move down, we would be trying to solve a 1 × 1 grid. We can see that each move tries to solve a smaller grid, or “subproblem.” The act of solving subproblems using the same process is called dynamic programming.

The following snippet performs dynamic programming by moving in a direction, either down (m-1) or to the right (n-1), recursively using the function.

return paths(m-1, n) + paths(m, n-1)

Fixes

Missing Solution

The example 2 × 2 grid should return six possible paths, but the code below isn’t sufficient to do so.

if m == 1 or n == 1:
    return 1

return paths(m-1, n, True) + paths(m, n-1, True)

When paths(2,2) is called, the function calls (with numbers substituted in)

return paths(1, 2, True) + return paths(2, 1, True)

Due to m == 1 or n == 1, both functions return 1, leading to the incorrect output of 2.

The reason for this is that we have only calculated the answer for $m-1$ and $n-1$ but not $m$ and $n$ ! So, we correct this by adding one to $m$ and $n$ , but only for the first time pass() is called.

if not ran:
    m += 1
    n += 1

The boolean flag ran is False in the first call but is passed as True in all other subsequent calls.

Zero Bugs 🐛

# Edge cases
if m == 0 and n > 0:
    return n

if m > 0 and n == 0:
    return m

if m <= 0 or n <= 0:
    return 0

Since we add one to $m$ and $n$ and check for m == 1 or n == 1, any grid size involving zero will automatically return 1, which is incorrect. This code fixes that. That’s right, this is a fix for a fix 😵. And yes, the title is a play on words.

Optimization

Finally, we add code to optimize the solution, in this case, memoization. The program saves the solutions to the various grids it solves. On further function calls, it checks to see if it has already seen a grid subproblem, and if so, immediately returns the answer.

For example, with a 3 × 3 grid, it’ll solve the subproblem of a 2 × 2 grid. We already know that there are six possible paths for a 2 × 2 grid, so instead of solving that grid again, it just immediately returns the answer of six.

Code

# Project Euler: Problem 15
# Lattice paths

def paths(m, n, memo={}, ran=False):

    key = str(m) + ',' + str(n)
    if (key in memo):
        return memo[key]

    # Edge cases
    if m == 0 and n > 0:
        return n
    
    if m > 0 and n == 0:
        return m
    
    if m <= 0 or n <= 0:
        return 0
        
    # Normal operation
    if not ran:
        m += 1
        n += 1

    if m == 1 or n == 1:
        return 1

    memo[key] = paths(m-1, n, memo, True) + paths(m, n-1, memo, True)
    return memo[key]

print(paths(20, 20))