Starting in the top left corner of a 2 x 2 grid, there are 6 routes (without backtracking) to the bottom right corner.
How many routes are there through a 20 x 20 grid?
Picture is always a huge help to find correct the solution. Let's see the pattern here, with another picture
Warning: If you don't understand art, don't look at that picture.
It's a solution for 3 x 3 grid. We trying to process it by steps:
[0, 0]. There is just one case to be at the start so we put
1to that point.
[1, 0]or right
[0, 1], and we put
1on the edges of the second diagonal line.
[1, 1]we can reach either from
[0, 1]or from
[1, 0], so there are two routes, and so on.
If you just output the numbers from each diagonal line you'll get:
1 1 1 1 2 1 1 3 3 1
It's famous Pascal's triangle. Each element in this triangle obtained by sum of two closest elements from the upper row.
To get desired result we need to sum these numbers again, until we get one number. But it's also numbers from Pascal's triangle.
1 3 3 1 4 6 4 10 10 20
We can treat Pascal's triangle as a sequence, and each row is an element. Then the following function calculates next row:
(defn routes-extend [lst] (let [size (count lst)] (for [i (range (inc size))] (if (or (= 0 i) (= size i)) 1 (+ (nth lst (dec i)) (nth lst i))))))
(routes-extend ) => [1 1] (routes-extend [1 1]) => [1 2 1]
Now we can build infinite sequence of Pascal's triangle rows:
(iterate routes-extend )
3 x 3 grid we had 7 diagonals, each of them represented one row.
Take a guess. For
n x n grid we need to get
2 * n + 1 row. And take it
middle element, which, of course, will be with the index
That's the final solution:
(let [n 20 d (inc (* n 2))] (nth (last (take d (iterate routes-extend ))) n))
P.S Two points I want to admit here. First of all, drawing pictures and trying to understand problem with pictures is a powerful technique that must be used for every problem.
Second of all, you can see that our algorithm has complexity of
O(n^2). But ideal
O(1) with usage binomial coefficient