## Project Euler Problem #15

### January 29, 2010

Read the details of the problem here

Summary

Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?

Solution

Compared to that palava I went through the Project Euler Problem #14 this was very easy indeed!

Solved it by noting that the number of paths to a corner is simply the sum of the paths to the adjacent corners. This gave Pascal’s Triangle values across the diagonals. This is used for binomial expansions and calculating combinations. It can be generated using the following formula:

combination(n, r) = n!/(n-r!)r! – i.e. Ways of picking r elements from n

Solving for: n = 40, r = 20
= 40! / (40-20)!20!
= 40! / 20!20!
= 13 * 20 * 21 * 23 * 29 * 31 * 33 * 37

If you don’t want to do this by hand, Groovy listops make it a straightforward one-liner. Note that it’s only necessary to divide by 20! once as the other division is being done by starting at 21 for the 40! element.

```BigInteger answer =
(21..40).inject(1G) { p, n -> p * n } / (2..20).inject(1G) { p, n -> p * n }
```

Runs in 0.42 seconds. It’s quicker by a factor of 20 to use a recursive factorial routine than the listops but then it wouldn’t be as Groovy!

Conclusion

Quick to write in Groovy for a one off calculation as simple as this one.