Project Euler - Problem 15

Welcome to week 15 of my Project Euler series.

Problem 15:

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

Details:

Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 2020 grid?

Code:

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

class Problem0015

{

static void Main(string[] args)

{

Console.WriteLine(binomialCoefficient(40,20));

Console.Read();

}

public static long binomialCoefficient(int n, int k)

{

long c = 1;

for (int i = 0; i < k; i++)

{

c = c * (n - i);

c = c / (i + 1);

}

return c;

}

}

Solution:

The code for this one is short, sweet, and to the point.  The journey there was not however. This one required a lot of research on my part to come to the answer. Once I was there and it all started to come back however it was painfully obvious. I really hate how hindsight has 20/20 vision. It would be so much more useful to have that kind of clarity before hand.

What I ended up going with was the equation for a simple Binomial Equation as it was the fastest of the options available and the most straight forward. I simply had to implement  in C#.  Simple right?  Once you have a grasp of C# and binomial coefficients it really is.  The only real question that was left over was, what are n and k in this example?  In reading some interesting articles about path finding, I found people using this equation to solve the number of paths from one side of a 2d map to the other.  k was the length of on of the sides and n was the number of steps from one side to the other.  Plop those in the proper place in your equation and you have yourself an answer.

Until next time...

Enjoy!