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: Pascal Triangle Node Equation 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);
        }
    }
}

Comments


No comments yet, be the first to leave one.

Leave a Comment