Different path for grid move (part 2)

Question

This is a continued discussion from (Different path for grid move) to optimize for space complexity, 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.

I use a dynamic programming method to track count in r-1 steps (using pre_row) and r steps (using cur_row). Here is my code and any advice on code bugs, performance improvements in terms of time complexity, or code style issues are appreciated.

Source code in Python 2.7,

def grid_move(rights, ups):
 pre_row = []
 pre_row.append(0)
 # initialize for zero right and up only
 for i in range(1, ups+1):
 pre_row.append(1)
 cur_row = []
 for r in range(1, rights+1):
 for u in range(0, ups+1):
 if u > 0:
 cur_row.append(pre_row[u] + cur_row[-1])
 else:
 cur_row.append(1)
 pre_row = cur_row
 return cur_row[-1]
if __name__ == "__main__":
 print grid_move(2,3)

• Raziman T V: Why do you append 0 first? It should be 1.
• Lin Ma: @RazimanT.V., zero up ad zero rights, there is no solution, why should be 1?
• Raziman T V: There is exactly one way to do nothing. nC0 is 1 not 0.

Answer 1

The code has a bug: Since you are appending elements, you have to make sure that the array is empty in the beginning. So the cur_row = [] command should be inside the loop.

Also, the number of ways to reach origin from origin is 1. Hence pre_row should have all elements 1 initially. This means that you can just do pre_row = [1] * (ups+1) instead of appending.

Next problem is kind of aesthetic. You are building cur_row at each step and turning pre_row into it in the end. Then it makes sense to fill cur_row before the loop as well, and that will make sure that the code also works for rights == 0.

Once we do these, there is no longer the need to append to cur_row inside the loop. We are sure that the list has the correct size so we can just assign elements.

Finally just remove the if inside the loop.

Combining these we have

def grid_move(rights, ups):
 cur_row = [1] * (ups+1)
 for r in range(1, rights+1):
 pre_row = cur_row
 cur_row[0] = 1
 for u in range(1, ups+1):
 cur_row[u] = pre_row[u] + cur_row[u-1]
 return cur_row[-1]

These should make the code more readable and efficient, and make the recurrence relation clear.

• Raziman T V: Exercise: Can you modify the code to not require pre_row at all?
• Lin Ma: Thanks, but can you explain why the number of ways to reach origin from origin is 1? I think zero up and zero rights have no solution, so should be zero (zero means no solution).
• Lin Ma: BTW, Raziman, I find even if after I initialize first element from 0 to 1, my code returns 6 for grid_move(4,2), however your code returns 15, your code returns the right answer. But I am confused since we have almost identify code? What is wrong with my code for grid_move(4,2) case?
• Lin Ma: BTW, Raziman, as a follow-up, I improved code by using only cur, I post my code here, and your advice is highly appreciated, always. codereview.stackexchange.com/questions/153102/…
• Raziman T V: Changing 0 to 1 is not enough, you also need to reset cur in the beginning of the loop if you are appending.

Answer 2

I believe you have a bug: grid_move(4, 2) is 6, when the right answer should be

$$ \frac{(4 + 2)!}{4! 2!} = \frac{6!}{4!2!} = \frac{6 \times 5}{2} = 15. $$

• Lin Ma: You are right, coderodde, vote up, but what is wrong in my code?

Answer 3

This can be simplified to a closed form, with a few observations.

For an n * m grid, where you start in the lower left corner and have a choice between "move right" and "move up", you will always execute exactly n + m - 2 moves. Of these, n-1 will be "right" and "m-1" will be up.

This is, as it happens, the same as "pick n-1 combinations from (n + m - 2)" elements and should, for low "n and m" be solvable in constant space (if n and m get sufficiently large, they could end up overflowing fixed-size integers and require bignums). In the code below, n - 1 is rights and m - 1 is ups. Depending on the exact Python version, you may need to change range to xrange to get constant space.

Example Python code:

def grid_mode(rights, ups):
 acc = 1
 low = min(rights, ups)
 high = max(rights, ups)
 for i in range(high, (high + low)):
 # We get high, high+1, ... high+low-1 from the range
 # We actually want the product of high+1, ..., high+low
 acc *= i + 1
 for i in range(2, low+1):
 acc //= i
 return acc

• Vatine: @Graipher You're correct, I should've used //= to signal integerness. Due to the numbers, the result will always be an integer, so both /= and //= should end up with the same result in any Python version that supports //.
• Lin Ma: Thanks Graipher, what do you mean "pick n-1 combinations from (n + m - 2)" elements ", I think it should be permutation other than combination, since order matters, and also it should be permutation of (n+m-2) elements (with repetitive n-1 for rights, and m-1 for ups)?
• Lin Ma: BTW, for your code acc *= i + 1, does it have any logical meaning? Or it is just simply a way to calculate combination formula?
• Vatine: @LinMa It's just easier to do i+1 than range(high+1, high + low + 1). But it is just the combination formula, yes.