Problem 015: Lattice paths

From Project Euler:

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

There is a very fast solution for this problem using combinatorics. It's a very interesting approach, but since I didn't think of it and swiped it from somewhere else, I'll leave it as an exercise to you to figure that one out.

What I did was approach this as a dynamic programming problem. For each point in the lattice, the only ways to get there are from the left or from the top. An edge case (pun intended) is along the left and top edges, for every point there is only one possible way to get there. So for each point the number of paths $P(x, y)$ is:
$$
P(x, y) = \left\{
\begin{array}{ll}
1 & x = 0\ or\ y = 0 \\
P(x - 1, y) + P(x, y - 1) & otherwise
\end{array}
\right.
$$
At first glance this might look like a recursive solution, however that will be very inefficient since we'll end up calculating several values many times. Instead, we'll use a dynamic programming approach to build up a grid of values, starting from one edge and working our way across. Once we've filled the grid, we return the value in the bottom right corner.

(defn count-routes [width height]
  (loop [x 0
         y 0
         grid {}]
    (if (and (== x 0) (== y height))
      (grid [(- width 1) (- height 1)])
      (recur (mod (+ x 1) width)
             (if (== x (- width 1))
               (+ y 1)
               y)
             (assoc grid
                    [x y]
                    (+ (if (> x 0) (grid [(- x 1) y]) 1)
                       (if (> y 0) (grid [x (- y 1)]) 1)))))))

This runs super fast:

$ lein run
Processing...
137846528820
"Elapsed time: 7.410219 msecs"