2
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ Why do you append 0 first? It should be 1. \$\endgroup\$ – Raziman T V Jan 19 '17 at 9:11
  • \$\begingroup\$ @RazimanT.V., zero up ad zero rights, there is no solution, why should be 1? \$\endgroup\$ – Lin Ma Jan 20 '17 at 2:22
  • \$\begingroup\$ There is exactly one way to do nothing. nC0 is 1 not 0. \$\endgroup\$ – Raziman T V Jan 20 '17 at 6:07
4
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Exercise: Can you modify the code to not require pre_row at all? \$\endgroup\$ – Raziman T V Jan 19 '17 at 10:27
  • \$\begingroup\$ 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). \$\endgroup\$ – Lin Ma Jan 20 '17 at 2:23
  • \$\begingroup\$ 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? \$\endgroup\$ – Lin Ma Jan 20 '17 at 4:42
  • \$\begingroup\$ 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/… \$\endgroup\$ – Lin Ma Jan 20 '17 at 5:32
  • \$\begingroup\$ Changing 0 to 1 is not enough, you also need to reset cur in the beginning of the loop if you are appending. \$\endgroup\$ – Raziman T V Jan 20 '17 at 6:09
3
\$\begingroup\$

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. $$

\$\endgroup\$
  • \$\begingroup\$ You are right, coderodde, vote up, but what is wrong in my code? \$\endgroup\$ – Lin Ma Jan 20 '17 at 4:33
3
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ @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 //. \$\endgroup\$ – Vatine Jan 19 '17 at 13:27
  • \$\begingroup\$ 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)? \$\endgroup\$ – Lin Ma Jan 20 '17 at 2:31
  • \$\begingroup\$ BTW, for your code acc *= i + 1, does it have any logical meaning? Or it is just simply a way to calculate combination formula? \$\endgroup\$ – Lin Ma Jan 20 '17 at 2:32
  • \$\begingroup\$ @LinMa It's just easier to do i+1 than range(high+1, high + low + 1). But it is just the combination formula, yes. \$\endgroup\$ – Vatine Jan 20 '17 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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