2
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ That is correct. I am not very familiar with Python style rules, so perhaps someone else can help you with that. \$\endgroup\$ – Raziman T V Jan 20 '17 at 6:11
5
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Alex Jan 20 '17 at 13:25
  • \$\begingroup\$ Nice idea Peilonrayz, mark your reply as answer to benefit other people who has similar issues in the future. \$\endgroup\$ – Lin Ma Jan 22 '17 at 22:15
5
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ Looks nice! It is more elegant. \$\endgroup\$ – Lin Ma Jan 20 '17 at 22:32
4
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ Nice answer, and vote up! \$\endgroup\$ – Lin Ma Jan 22 '17 at 22:15

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.