Mdthbs

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.')

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.

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]