In this challenge, the goal is to calculate the number of lattice paths in a square grid. A lattice path is define as: A path composed of connected horizontal and vertical line segments, each passing between adjacent lattice points. They have a lovely image on the challenge site showing an example of lattice paths in a 2x2 grid.

With this problem, it helped that I have been working on some path finding algorithms for a game I'm developing. So I know that lattice paths can be easily calculated on a square grid by using Pascal's Triangles. The equation to find a node in Pascal's Triangle is: Where *n* is the row number in the triangle and *k* is the node number to select. In a Pascal Triangle, the lattice path number will be at 2 times the number of cells in the row and in the middle of the triangle. So for a 4x4 grid, the lattice paths count will be a *n=8* and *k=4*.

using System; using System.Numerics; namespace ProjectEuler_15 { internal class Program { private static BigInteger Factorial(int n) { BigInteger b = 1; for (int i = n; i > 1; i--) { b *= i; } return b; } private static BigInteger GetLatticePathCount(int squareSize) { // lattice path counts of a square can be found using // pascal's triangle. The number of lattice paths will // be the center value of pascal's triangle at the 2x row number // of the square size. // formula for pascal's triangle: // n! // ________ // k!(n-k)! int n = 2 * squareSize, k = squareSize; var result = Factorial(n) / (Factorial(k) * Factorial(n - k)); return result; } private static void Main(string[] args) { var latticeCount = GetLatticePathCount(20); Console.WriteLine("Number of lattice paths in a 20x20 grid: {0}", latticeCount); } } }

Recent Blog Activity

Blog Archive