4
\$\begingroup\$

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 matrix dp to track number of path. For example, dp[i][j] means if we move i steps right and j steps up.

Any advice on code bugs, smarter ideas in terms of algorithm time complexity or code style advice is appreciated.

def move_right_up_count(rights, ups):
    dp = [[0] * (ups+1) for _ in range(1+rights)]
    for i in range(1,rights+1):
        dp[i][0] = 1
    for j in range(1, ups+1):
        dp[0][j] = 1
    for i in range(1, rights+1):
        for j in range(1, ups+1):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[-1][-1]

if __name__ == "__main__":
    print move_right_up_count(2,3)
\$\endgroup\$
  • 5
    \$\begingroup\$ Smarter algorithm: prove that the answer is equal to (u+r)!/(u!r!) \$\endgroup\$ – Raziman T V Jan 17 '17 at 6:46
  • \$\begingroup\$ @RazimanT.V., I agree with you the direct count method is a very cool idea, vote up. For my original code and question, do you have any comemnts? \$\endgroup\$ – Lin Ma Jan 18 '17 at 7:59
  • 1
    \$\begingroup\$ It's pretty good, you could modify it to use a 2*n array instead of m*n though \$\endgroup\$ – Raziman T V Jan 18 '17 at 8:02
  • \$\begingroup\$ @RazimanT.V., nice idea and vote up. I make improvements based on your new idea and any advice is appreciated. Refer here => codereview.stackexchange.com/questions/153012/… \$\endgroup\$ – Lin Ma Jan 19 '17 at 8:36
  • \$\begingroup\$ I added a little bit more content you may find interesting. \$\endgroup\$ – coderodde Jan 19 '17 at 9:35
4
\$\begingroup\$

PEP 8

PEP 8 complains about this line:

for i in range(1,rights+1):

You should have a single space after the comma and before rights+1:

for i in range(1, rights+1):

Straight to business

Taking on the advice of Raziman T. V.: you are allowed to move \$u\$ steps up and \$r\$ steps right. Now denote a move upward by u and the move to the right by r. The total number of moves is \$u + r\$. Next, every valid path is a string of length \$u + r\$ containing \$u\$ characters u and \$r\$ characters r; clearly, any such string denotes a valid path.

Now, you can permute a string of length \$u + r\$ in \$(u + r)!\$ ways. However, since all us (respectively, rs) are equal, you divide \$(u + r)!\$ by \$u!r!\$ since there is \$u!\$ ways to permute the subsequence of \$u\$ characters u and each of them are equal; same for characters r.

The above leads to

$$\frac{(u + r)!}{u!r!},$$

and, finally, to the code

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)


def count_paths(r, u):
    return factorial(r + u) / factorial(r) / factorial(u)

Edit

You can optimize the above a little bit:

def count_paths_v2(r, u):
    min_ru, max_ru = min(r, u), max(r, u)
    value = 1
    for i in range(max_ru + 1, r + u + 1):
        value *= i
    return value / factorial(min_ru)

count_paths performs \$(u + r) + u + r\$ steps, and count_paths_v2 only \$\min(u, r) + (r + u) - \max(r, u).\$

Cleaning a bit

What comes to your version, you can write it a little bit more succintly:

def move_right_up_count(rights, ups):
    grid = [[1 for _ in range(rights + 1)] for _ in range(ups + 1)]
    for y in range(1, ups + 1):
        for x in range(1, rights + 1):
            grid[y][x] = grid[y - 1][x] + grid[y][x - 1]
    return grid[-1][-1]

Hope that helps.

\$\endgroup\$
  • \$\begingroup\$ Thanks coderodde, I agree with you the direct count method is a very cool idea, vote up. For my original code and question, do you have any comemnts? \$\endgroup\$ – Lin Ma Jan 18 '17 at 7:59
  • 1
    \$\begingroup\$ @LinMa No, unfortunately that's all I can say. :( \$\endgroup\$ – coderodde Jan 18 '17 at 8:48
  • \$\begingroup\$ It is ok, and I have make a new post for some new ideas, if you have any advice on it, it will be great. :) Refer to => codereview.stackexchange.com/questions/153012/… \$\endgroup\$ – Lin Ma Jan 19 '17 at 8:37

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.