Calculate the lattice paths in an n*n lattice (Project Euler #15)

Question

Project Euler #15 is to find out all the distinct possible ways there are to move from the first point (1,1) to point (n,n) in an n*n lattice.

def lattice_paths_of_n(n):
 list2 = []
 my_list = []
 for i in range(1, n+2):
 list2.append(i)
 for i in range(1, n+2):
 my_list.append(list2)
 for i in range(0,n+1):
 for f in range(0,n+1):
 if f == 0 or i == 0:
 my_list[i][f] = 1
 else:
 my_list[i][f] = my_list[i-1][f]+my_list[i][f-1]
 return my_list[n][n]
print(lattice_paths_of_n(20))

However, this function is extremely inefficient and I would appreciate it if you could give me suggestions to optimize the same. I tried to find a more efficient solution to this problem on this site, but couldn't find one in Python 3.

• Insane: What leads you to believe it's extremely inefficient? (I'm not arguing it isn't, just asking)
• Aradhye Agarwal: Well, I basically used brute force; whereas I can use a more efficient intelligent way to calculate the answer.
• Jaime: Won't spoil the fun for you, but there is a closed form solution that involves permutations: you just need to compute a couple of factorials to get to the answer.
• Insane: @Jaime Well this is what Code Review is! Feel free to write it up as an answer with an explanation :)
• Aradhye Agarwal: @Jaime if you do answer, I would appreciate it if you also provided a logical explanation behind your formula and it's derivation.

Answer 1

To move from the top left corner of an \$n\times n\$ grid to the opposite one you have to move \$n\$ times to the right and \$n\$ times down. So in total you will do \2ドルn\$ moves. If you could make those in any order there would be \$(2 n)!\$ ways of doing them. But you don't have that freedom, because the order within the movements to the right and within the movements down is fixed, e.g. you have to move from row 4 to row 5 before you can move from row 5 to row 6. So of the \$n!\$ ways the movements to the right can be ordered, only one is valid, and similarly with the movements down.

Summing it all up, the closed form answer to that problem is:

$$ \frac{(2n)!}{n!n!} $$

Unsurprisingly this is the same as \$C_{2n, n}\,ドル the combinations of \2ドルn\$ items taken \$n\$ at a time. You could think of the same problem as having \2ドルn\$ movements and having to choose \$n\$ of those to make e.g. the movements down, leaving the others for the movements right.

With Python's arbitrary size integers you could simply calculate that as:

import math
def pe15(n):
 n_fact = math.factorial(n)
 return math.factorial(2 * n) / n_fact / n_fact

To give this answer a little more meat, in most other languages you don't have the luxury of not having to worry about integer overflows. Even in Python it may be a good idea if you want to keep your computations fast for very large numbers. So you would typically do the same computation as:

def pe15_bis(n):
 ret = 1
 for j in range(1, n+1):
 ret *= n + j
 ret //= j
 return ret

In Python that doesn't seem to pay off (performance wise) until n is in the many hundreds, but I find lovely that, the way that code goes, ret is always exactly divisible by j. Figuring out why is left as an exercise for the reader...