Project Euler # 15 Lattice paths in Python 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.')
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 &amp; 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.


The if __name__ == '__main__': block clearly runs two cases


a 2x2 lattice, and
a 20x20 lattice.

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.
The count_lattice_paths(rows, cols) is the @timed function, so the time spent printing the result report in not counted in the timing.
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]