current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 2 down vote favorite
2

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)
share|improve this question
1  
Why do you append 0 first? It should be 1. – Raziman T. V. Jan 19 at 9:11
    
@RazimanT.V., zero up ad zero rights, there is no solution, why should be 1? – Lin Ma 2 days ago
    
There is exactly one way to do nothing. nC0 is 1 not 0. – Raziman T. V. 2 days ago
up vote 4 down vote

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.

share|improve this answer
1  
Exercise: Can you modify the code to not require pre_row at all? – Raziman T. V. Jan 19 at 10:27
    
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 2 days ago
    
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 2 days ago
    
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/… – Lin Ma 2 days ago
    
Changing 0 to 1 is not enough, you also need to reset cur in the beginning of the loop if you are appending. – Raziman T. V. 2 days ago
up vote 3 down vote

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

share|improve this answer
    
You are right, coderodde, vote up, but what is wrong in my code? – Lin Ma 2 days ago
up vote 3 down vote

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
share|improve this answer
1  
@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 //. – Vatine 2 days ago
    
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 2 days ago
    
BTW, for your code acc *= i + 1, does it have any logical meaning? Or it is just simply a way to calculate combination formula? – Lin Ma 2 days ago
    
@LinMa It's just easier to do i+1 than range(high+1, high + low + 1). But it is just the combination formula, yes. – Vatine 2 days ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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