### Challenge: Lattice Paths

Posted on: July 19, 2016 10:15:52 PM

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.

Program.cs
```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);
}
}
}
```

No comments yet, be the first to leave one.

Recent Blog Activity
Blog Archive