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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: