0
\$\begingroup\$

I was trying to solve this problem called lattice path from Project Euler:

Count the number of unique paths to travel from the top left to the bottom right of a lattice of squares.

How many such routes are there through a 20×20 grid? It takes me forever to get an answer...

https://projecteuler.net/project/images/p015.gif
(source: projecteuler.net)

    #  Input:     An interger N (which is the size of the lattice)
    #  Output:    An interger (which represents the number of unique paths)
    #
    #  Example:   input: 2
    #
    #             (2 x 2 lattice of squares)
    #              __ __
    #             |__|__|
    #             |__|__|
    #

When moving through the lattice, you can only move either down or to the right.

I currently have 1 solution, and I am not sure how much better if we memoize it. But I wanted to ask for code review for my solution below:

def lattice_paths(m, n):
    if m == 0 and n == 0:
        return 1
    if m < 0 or n < 0:
        return 0
    return lattice_paths(m - 1, n) + lattice_paths(m, n - 1)

Here is the time complexity and space complexity of my first solution.
# Time Complexity: O(2^(M+N))
# Auxiliary Space Complexity: O(M+N)

Dynamic approach with the memorized solution:

def lattice_paths(m, n): # m rows and n columns


    def helper(x, y):

      if x > helper.m or y > helper.n:
        return 0
      if helper.cache.get((x, y)) is not None: 
        return helper.cache[(x, y)]

      helper.cache[(x, y)] = helper(x + 1, y) + helper(x, y + 1)
      return helper.cache[(x, y)]  
    helper.cache = {}

    helper.m = m
    helper.n = n
    helper(0,0)

    if m  ==  0 and n == 0:
      return 1
    elif m < 0 or n < 0:
      return 0
    else:
      return helper.cache[(0, 0)]
\$\endgroup\$
1
  • 1
    \$\begingroup\$ That's more of a mathematics and algorithm problem than a coding one. Check out this excellent blog post \$\endgroup\$ Aug 2, 2018 at 21:44

2 Answers 2

2
\$\begingroup\$

All of your approaches are very brute force. The answer can be computed with a bit of mathematical reasoning. For an m × n lattice, all paths will have m + n segments, of which m segments will go down and n segments will go right. So, out of m + n slots, count the ways to pick m downward moves; the rest of them will be rightward moves. The number of paths is:

$${m + n \choose m} = {m + n \choose n} = \frac{(m+n)!}{m! \, n!}$$

So, the Python solution is simply:

from math import factorial

def lattice_paths(m, n):
    return factorial(m + n) // factorial(m) // factorial(n)

Even though the calculation involves large factorials, Python supports big integers seamlessly, and arrives at the answer nearly instantaneously.

\$\endgroup\$
-1
\$\begingroup\$

here's a solution that uses cache to memoize the solution

def lattice_paths(m, n):
    cache = [1]
    larger = max(m, n)
    smaller = min(m, n)
    while(len(cache) < larger + 1):
        for i in range(1, len(cache)):
            cache[i] += cache[i - 1]
        cache.append(2 * cache[len(cache) - 1])
    return cache[smaller]

# Time Complexity: O(N)
# Auxiliary Space Complexity: O(N)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.