0

Here's the problem:

Given an m x n array, get the number of different paths from the top left corner to the bottom right corner, if you can only move down, right, and diagonally down & right.

Here's my memoized recursive solution, which is relatively straightforward. It works because the number of paths from position (m1, n1) is equivalent to # paths one unit to the right + # paths one unit down + # paths one unit diagonally:

def numberOfPaths(m, n, cache = {}):
    if (m < 1 or n < 1):
        return 0
    if (m == 1 and n == 1):
        return 1
    if ((m, n) not in cache):
        cache[(m, n)] = numberOfPaths(m - 1, n, cache) + numberOfPaths(m, n - 1, cache) + numberOfPaths(m - 1, n - 1, cache)
    return cache[(m, n)]

Now I want to write a combinatorial solution. If there were no diagonals, this would be easy. You have to move m - 1 units to the right, n - 1 units down, so the number of combinations is just (m - 1 + n - 1) choose (m - 1).

The diagonals complicate it a little bit, but I figure that I can get the # paths with 0 diagonals + # paths with 1 diagonal + ... + # paths with min(m, n) - 1 diagonals (since that's the maximum number of diagonals that are possible; any more and the diagonals would go off of the grid).

To calculate each term, I can just do (m + n - 2 - d) choose d (since there are m + n - 2 - d positions where right, down, or diagonals could go [diagonals take up two spots]) and multiply it by (m + n - 2 - 2 * d) choose (m - 1 - d) -- the number of ways that you can arrange the remaining down/right movements.

def combinatorial(m, n):
    factorial = math.factorial
    def combination(n, k):
        return factorial(n) / (factorial(k) * factorial(n - k))
    paths = 0
    for i in range(0, min(m, n)):
        # for 0 through min(m, n) - 1 diagonals,
        # sum up the number of combinations that exist with that number of diagonals
        paths = paths + combination(m + n - 2 - i, i) * combination(m + n - 2 - 2 * i, m - 1 - i)
    return int(paths)

This works in a lot of cases (particularly square grids), but why does this fail on some inputs -- for example, m = 18, n = 88? numberOfPaths returns 399615234030198251385775, while combinatorial returns 399615234030198283304960 (a slightly larger number). Any tips?

-2

Got it. Turns out it was due to floating point imprecision in the combination function. I replaced the function with:

def combination(n, k):
    return factorial(n) // factorial(k) // factorial(n - k)

and now it works. Sanity restored.

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.