Time to count!

This problem has less to do with programming and more to do with combinatorics. What might someone who has no experience with combinatorics do to attempt this problem? I suppose you could say it’s an exercise in recursive thinking, or something. To me it is too much “obviously” a combinatorics problem.

Approach with Combinatorics

A key model is that you can imagine there must “m” right-moves, and “n” down-moves. No more, no less. The only thing left is what order those moves can appear in (right right down, down right right, etc.). All possible orders are valid.

A few ways to model this. So there are a=m+n moves to make, and n of those must be down moves (and implicitly, the remaining m must be right moves), so of the a total moves, we have to choose n to be down moves. So the answer is a-choose-n. (Well OK, a detail of the question is that we’ve already made 1 down-move and 1 right-move, essentially, based on the definition of the problem and where the “robot” is. So subtract both by 1, it’s (a-2) choose (n-1).

Towards a Solution

Now, uh, what’s a-choose-n? That’s a good question. The answer is that this is sort of exactly the motivating exercise. A lot of combinatorics is learning the basic tools, like n-choose-k, and see how problems reflect opportunities to use those tools.

So I implemented n-choose-k in a terrible fashion. Numerical stability is definitely a concern. Python helps alleviate that concern. For other numeric-ish problems, I’ve collected them here.

def factorial(x):
    p = 1
    for i in range(1, x+1):
        p *= i
    return p

class Solution(object):
    def uniquePaths(self, m, n):
        # We move everything "forward"
        # because our robot and goal occupy spaces
        m -= 1
        n -= 1
        
        # Attempt at numerical stability
        a = m+n
        s = min(m,n)
        
        # a!/(a-s)!
        res = 1
        for i in range((a-s)+1, a+1):
            res *= i
        
        # X/s!
        res /= factorial(s)
        return res