Project Euler # 15 Lattice paths in Python

Question

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?

from time import time
from functools import lru_cache


def make_grid(grid_size):
    """Return a list of lists containing grid."""
    grid = tuple((0,) * (grid_size + 1) for _ in range(grid_size + 1))
    return grid


@lru_cache(None)
def count_lattice_paths(matrix, row, column):
    """Return number of all possible paths from top left to bottom right of n * n grid."""
    if row == 0 or column == 0:
        return 1
    return count_lattice_paths(matrix, row - 1, column) + count_lattice_paths(matrix, row, column - 1)


if __name__ == '__main__':
    start_time = time()
    g = make_grid(20)
    length = len(g) - 1
    print(count_lattice_paths(g, length, length))
    print(f'Time: {time() - start_time} seconds.')

Answer 1

Performance Counter

When you use time.time(), you are getting the number of seconds since January 1, 1970, 00:00:00 UTC. This value is (as I'm writing this) around 1565401846.889736 ... so has about microsecond resolution.

When you use time.perf_counter(), you are getting "a clock with the highest available resolution to measure a short duration". As I was writing this, I retrieved the value 53.149949335 ... so it has approximately nanosecond resolution.

For profiling code, you want the highest resolution timer at your disposal ... so eschew time.time() in favour of time.perf_counter().

Timed Decorator

Since you are doing a lot of performance measurements in your exploration of Project Euler, you should package up the performance measurement code in a neat little package that can be easily reused. You were given a decorator for this in an answer to your "Time & Space of Python Containers" question. But here it is again, slightly modified for just doing timing:

from time import perf_counter
from functools import wraps

def timed(func):
    @wraps(func)
    def wrapper(*args, **kwargs):
        start = perf_counter()
        result = func(*args, **kwargs)
        end = perf_counter()
        print(f"{func.__name__}: {end-start:.6f} seconds")
        return result
    return wrapper

You can decorate a function with @timed, and it will report how long that function takes. You can even decorate multiple functions!

And it moves the timing code out of your if __name__ == '__main__': block.

Use Test Cases

Project Euler 15 gives you the answer to a 2x2 lattice grid. You should run that test case in your code, to give yourself confidence you are getting the correct answer. Eg)

@timed
def count_lattice_paths(rows, cols):
    # ...

def pe15(rows, cols):
    paths = count_lattice_paths(rows, cols)
    print(f"{rows} x {cols} = {paths} paths")

if __name__ == '__main__':
    pe15(2, 2)
    pe15(20, 20)

A few import points.

1. The if __name__ == '__main__': block clearly runs two cases
   • a 2x2 lattice, and
   • a 20x20 lattice.
2. The pe15(rows, cols) calls count_lattice_paths(rows, cols) to get the result, and then prints out the result with a description of the case.
3. The count_lattice_paths(rows, cols) is the @timed function, so the time spent printing the result report in not counted in the timing.
4. The count_lattice_paths() method can be generalized to work with an NxM lattice; it doesn't need to be square, even though the problem asked for the result for a square lattice and gives a square lattice test case.

Count Lattice Paths (without a cache)

As you noticed, a 2x2 lattice is better represented by a 3x3 grid of nodes.

• It should be obvious there is only 1 way to reach every node along the top edge.
• It should be obvious there is only 1 way to reach every node along the left edge.

So, our initial array of counts would look like:

1 1 1
1 . .
1 . .

At each node (other than the top edge and left edge), the number of paths is equal to the sum of the paths to the node above it and the paths to the node to the left of it. So, there are 1+1 = 2 paths to the node at 1,1:

1 1 1
1 2 .
1 . .

Since the value at each point is defined entirely by the values above and left of it, we can directly loop over each node, and compute the required values, and finally return the value at the lower right corner of the grid. We don't even need to store the entire grid; we can compute the next row from the current row.

@timed
def count_lattice_paths(rows, cols):
    steps = [1] * (cols + 1)
    for _ in range(rows):
        for i in range(cols):
            steps[i+1] += steps[i]
    return steps[-1]

Answer 2

I like this code.

I like the use of the @lru_cache decorator. I appreciate seeing the elegance of the recursive solution, while knowing it has the performance of a dynamic programming one.

I like the naming, including the fact that name complexity scales with scope. I like the clarity, including the clear handling of the recursion base case. I like the formulation of the recursion that allows you to define (0,0) to be the base case rather than anything with a 20 in it.

I do notice that you don't actually use the matrix parameter to that function, except to pass to itself in a recursive call. I can only suspect that you had originally intended to use it to implement the dynamic programming explicitly, and didn't clean up completely when you changed plan. By the same token, make_grid can be completely removed and so can g. That incomplete cleanup is really the only criticism I would have of this code.

---

I will also mention, as with many of the project Euler problems, a more mathematical lens can be employed to avoid any exhaustive searching at all. For example, to reach the corner you need some order of twenty R and twenty D. Quantifying how many of those there are is a simple instance of the Multiset Permutation calculation.

However, it's probably faster to write this code and execute it than do that calculation, so the apparent inefficiency of running code that doesn't need to be run is probably justified.

Answer 3

Other answers have given you feedback on the code itself. I thought I'd tackle the performance tag. Josiah has a great remark regarding the mathematical approach to Project Euler problems. While it might be permissible to solve this challenge non-optimally, I guarantee that you will run into harder problems, where an inefficient method will be unusable.

My advice is to start as early as possible with finding the optimal approach, even if that takes more time to implement, and involves extra reading. The end result is worth it. Regarding the multiset permutation, I remembered from previous experience that this problem is related to Pascal's triangle. I checked the Wikipedia page, and found the formula for a specific element.

Then I double checked against your solution to find if the answers were correct. If I didn't have your solution, I'd check against a few smaller cases, and verify manually.

The maths basially boils down to "we want to take 40 steps, 20 of them should be to the right and 20 of them should be down". In how many ways can this be done?That number is exactly given by the expression \$40 \choose 20\$, where the formula \${n \choose k} = \frac{n!}{k!(n-k)!}\$. It should be noted that this expression is symmetric, so it doesn't matter whether you choose how to distribute your right-steps or your down-steps. And since there are as many right-steps as there are down-steps, the formula can be simplified to \${2k \choose k} = \frac{(2k)!}{k!^2}\$.

With this in mind, the code itself is almost trivial:

def fac(n):
    if n == 0:
        return 1
    return n * fac(n-1)

def count_lattice_paths_fast(n):
    n_fac = fac(n)
    return fac(n*2)//n_fac**2

For the original problem, this solution is about 80 times faster than your original solution. However, that factor grows as the input grows. For input 100, it is almost 10000 times faster. And that speedup will be crucial in later problems, because it will be the difference between waiting for hours or seconds.