Yacoby's Wanderings | Problem 15

Project Euler - Problem 15

Problem 15 is defined as:

How many ways are there (without backtracking) from the top left vertex to the bottom right vetex through 20x20 grid.

This can be solved using a decent calculator:

If you view the network as a directional graph, set the state of the starting vertex to 1, and set the state of every other vertex to sum of the states of the incoming vertexes. The result ends up looking something like this:

1 1 1 1
1 2 3 4
1 3 6
1 4

Which of course when rotated by 45 degrees, is Pascal's Triangle. The formula for the value at the nth row and the kth column is:

$\frac{n!}{k!(n-k)!}$

So for a 2x2 square, the formula is:

$\frac{4!}{2!(4 - 2)!} = \frac{4!}{2!^2} = 6<br /><br />$

More generaly for a n² square:

$\frac{2n!}{n!(2n - n)!} = \frac{(2n)!}{n!^2}$

Or in Haskell:

routes n = ( foldl1 (*) [1 .. 2*n] ) `div` ( ( foldl1 (*) [1 .. n] ) ^ 2 )

This can be optimized to reduce the amount of calculations required to by removing n! from the numerator and denominator:

routes n = (foldl1 (*) [n+1 .. 2*n] ) `div` ( foldl1 (*) [1..n] )

Overall I felt it was a rather neat solution