# Different path for grid move (part 3)

This is a continued discussion from (Different path for grid move (part 2)) to optimize for space complexity (using only cur list, other than a cur and another pre lists), and since it is new code and I make a new post.

Given a m * n grids, and one is allowed to move up or right, find the different number of paths between two grid points.

My major idea is, if move r steps right, u steps up, we can find (1) solutions for r-1 steps right and u steps up, then combine with one final right step (2) solutions for r steps right and u-1 steps up, then combine with one final up step.

Source code in Python 2.7,

def grid_move_v2(rights, ups):
cur = [1] * (ups + 1)
for r in range(1, rights+1):
for u in range(1, ups+1):
cur[u] = cur[u] + cur[u-1]
return cur[-1]

if __name__ == "__main__":
print grid_move_v2(2,3)
print grid_move_v2(4,2)

• That is correct. I am not very familiar with Python style rules, so perhaps someone else can help you with that. – Raziman T V Jan 20 '17 at 6:11

You should just use coderodde's formula:

$$\frac{(a + b)!}{a!b!}$$

Assuming $a \le b$, you can reduce the amount of numbers you need to multiply by. Using:

$$\frac{\Pi_{i = 1 + b}^{i \le a + b}i}{a!}$$

And so you can get $O(a)$, rather than $O(a + b)$ or $O(ab)$ code:

from functools import reduce, partial
from operator import mul

product = partial(reduce, mul)

def grid_move(a, b):
a, b = sorted([a, b])
return product(range(1 + b, a + b + 1)) / product(range(2, a + 1), 1)

• finally! I ruined half of my working day today just because I was trying to get this formula to answer, I was 100% sure that there is a pure math way to calculate this. – Alex Jan 20 '17 at 13:25
• Nice idea Peilonrayz, mark your reply as answer to benefit other people who has similar issues in the future. – Lin Ma Jan 22 '17 at 22:15

Since you never use r you can shift it down by one and call it _ (the customary unused variable in Python).

def grid_move_v2(rights, ups):
cur = [1] * (ups + 1)
for _ in range(rights):
for u in range(1, ups+1):
cur[u] = cur[u] + cur[u-1]
return cur[-1]

• Looks nice! It is more elegant. – Lin Ma Jan 20 '17 at 22:32

This

    for u in range(1, ups+1):
cur[u] = cur[u] + cur[u-1]


is just an accumulation loop. Python 3 has the itertools.accumulate function to perform it efficiently, but you can borrow the code from there if you want to stay with Python 2: it will name things and make the code more readable:

def accumulate(iterable):
"""Return running totals"""
it = iter(iterable)
total = next(it)
yield total
for element in it:
total = total + element
yield total

def grid_move_v2(rights, ups):
cur = [1] * (ups + 1)
for _ in range(rights):
cur = accumulate(cur)
return list(cur)[-1]

if __name__ == "__main__":
print grid_move_v2(2,3)
print grid_move_v2(4,2)


(I also used the improvement proposed by @Graipher)

• Nice answer, and vote up! – Lin Ma Jan 22 '17 at 22:15