Posts Tagged ‘prob15’

Problem 15 – Counting

July 3, 2009

When I first read problem 15, about counting the number of paths from one corner of a grid to the opposite corner, I knew there was some clever counting way to do it. I couldn’t quite remember what the clever way was, but I thought about it for a while, and remembered it.

Any path from the upper left to lower right corner consists of a sequence of moves right or down. We can denote any path as a sequence of Rs and Ds. In an n\times m grid, to start in one corner and go to the other, there must be exactly n Rs, and m Ds. So we can think of a path as a string of Rs and Ds, whose length is n+m, and so that exactly m of the letters are D (equivalently, exactly n are Rs). So we have n+m “spots” in which to put m Ds, meaning there are \binom{n+m}{m}=\frac{(n+m)!}{n!m!}=\frac{(m+1)\cdots(m+n)}{n!} paths. This gives us a constant-time (essentially) algorithm for computing the number of paths.

I didn’t give this problem too much more thought after that. Moving and finishing teaching a summer class occupied my time. But then Friday rolled around, and nobody else has written about this problem, so I thought I should. As I started coding, I realized there were some interesting things to say. Well, interesting when you’ve been grading Calculus exams for a few hours.

Here’s the code I wrote that computes the number of paths using the second formula above (which has fewer multiplications than the first):

import sys,time

def solve(n, m):
    """ Number of paths in through a grid 

    Return (number of paths, time to compute)
    t = time.time()
    prod = lambda x,y: x*y
    prange = lambda x,y: reduce(prod,xrange(x,y+1),1)
    fact = lambda y: prange(1,y)
    ret = prange(m+1,m+n) // fact(n)
    t = time.time() - t
    return (ret, t)

if __name__ == "__main__":
    args = map(int, sys.argv[1:3])
    print solve(*args)

There’s a few things to note here. The first is apparent in the code, the “*args” in the last line. What this does is “unpack” a tuple. The line above it makes a list (of length two), and I want to pass this to my solver function. But my solver function takes two arguments, not a list of length two. So I use the “*” to unpack my list. Pretty nice syntactic sugar. For (slightly) more on this topic, see the tutorial.

The other thing to notice only becomes apparent when you run the code. The value that gets printed as the answer (not the time part, but just the number of paths part), ends with an extra “L”. This indicates that the answer is a long integer. This happens, with this code, even if the final answer isn’t really that big. The in-between steps are big enough to cause the long integer to show up.

Next, I thought I’d see how easy it was to code up a solution that didn’t use this counting argument, but just counted the number of paths recursively. If you have an n\times m block, and are in the upper left, you can move either right (making an (n-1)\times m block), or down (making an n\times (m-1) block). So the total number of paths is the sum of the number of paths of these smaller blocks. There’s a base case when one of the parameters is 1. Then you have a 1\times m block, say, and there are m+1 routes through it (m+1 choices for when to move down). Here’s the essential bits of the code I wrote:

def worker(n,m):
    if n == 1 or m == 1:
        return max(n,m) + 1
    return worker(n-1,m) + worker(n,m-1)

But this take a loong time to run. The solution using the counting argument takes less than 0.0001 seconds to run on my computer (on the 20×20 input of the stated problem). This second solution takes… minutes (enough time to write, or at least edit, a post). Thinking about why, while the program continues to churn, we realize some improvements can be made. For starters, \text{worker(n,m)}=\text{worker(m,n)}. To use this, I figure I’ll store results as I compute them, so that I can just use them (instead of re-calculating them) if I need them again later (rather like my solution for problem 14). Here’s what I rigged up:

class Worker:
    def __init__(self):
        self.mem = {}
    def __getitem__(self,t):
        sm,lg = min(t), max(t)
        if (sm,lg) in self.mem:
            return self.mem[(sm,lg)]
        if sm == 1:
            self.mem[(1,lg)] = lg + 1
            return lg + 1
        ret = self[(sm-1,lg)] + self[(sm,lg-1)]
        self.mem[(sm,lg)] = ret
        return ret

def solve(n, m):
    w = Worker()
    return w[(n,m)]

This is still slower than the counting-trick solution, by more than a factor of 10 for the 20×20 input. Still, that’s fractions of a second, a big improvement on the code without any memory. Plus it lets me play with defining classes, and operator overloading. The function “__getitem__” in my class allows me to use the [] notation on an object of my class. I think I kinda like the way c++ does this better, where you define a function “operator[]”. That way you don’t have to remember the name of the function. But whatever, this works. Now that I’ve done it once, I imagine I’ll be able to remember the name.