Different path for grid move (part 3)

Question

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)

• Raziman T V: That is correct. I am not very familiar with Python style rules, so perhaps someone else can help you with that.

Answer 1

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)

• Alex: 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.
• Lin Ma: Nice idea Peilonrayz, mark your reply as answer to benefit other people who has similar issues in the future.

Answer 2

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]

• Lin Ma: Looks nice! It is more elegant.

Answer 3

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)

• Lin Ma: Nice answer, and vote up!