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 (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)
share|improve this question
1  
That is correct. I am not very familiar with Python style rules, so perhaps someone else can help you with that. – Raziman T. V. 2 days ago
    
Thanks for the confirmation, Raziman. – Lin Ma 2 days ago
up vote 4 down vote accepted

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)
share|improve this answer
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 2 days ago
    
Nice idea Peilonrayz, mark your reply as answer to benefit other people who has similar issues in the future. – Lin Ma 6 hours ago
up vote 5 down vote

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]
share|improve this answer
    
Looks nice! It is more elegant. – Lin Ma 2 days ago
up vote 4 down vote

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)

share|improve this answer
    
Nice answer, and vote up! – Lin Ma 6 hours 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.