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);
        }
    }
}

Challenge: Longest Collatz Sequence

Posted on: July 15, 2016 12:30:43 AM

This challenge wants you to find the longest collatz series between 1 and 1000000. A collatz series is defined by:
n → n/2 (n is even)
n → 3n + 1 (n is odd)

Example: n = 13
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
Program.cs
using System;

namespace ProjectEuler_14
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            const int MaxNum = 1000000;
            int highestCollatzSeriesCount = 0;
            int numWithHighestSeries = 0;
            // a cache can be used because all the series number eventually will get to
            // a series that's already been calculated; therefore, this will save a lot
            // of calculation time
            int[] cache = new int[MaxNum + 1];

            // 1 has a collatz series count of 1
            cache[1] = 1;

            // start the loop at 2 since, in theory, all numbers end with 1
            for (int i = 2; i < MaxNum; i++)
            {
                int count = 0;
                // use a long because int will likely overflow at higher numbers
                long collatz = i;
                do
                {
                    //n → n/2 (n is even)
                    //n → 3n + 1(n is odd)
                    if (collatz % 2 == 0)
                    {
                        collatz /= 2;
                    }
                    else
                    {
                        collatz = (collatz * 3) + 1;
                    }

                    count++;
                    // we can break the loop if collatz=1 or collatz > i
                    // because if it is less than i, it's been cached
                } while (collatz != 1 && collatz > i);

                // add the cached number to the total count
                count += cache[collatz];

                // cache the value
                cache[i] = count;

                if (count > highestCollatzSeriesCount)
                {
                    highestCollatzSeriesCount = count;
                    numWithHighestSeries = i;
                }
            }

            // print out the result
            Console.WriteLine("Number with highest collatz series below {0}: {1} with {2} in series.", MaxNum, numWithHighestSeries, cache[numWithHighestSeries]);
        }
    }
}

Since memory wasn't a huge concern, I decided to cache the collatz sequence counts for every calculation so that I am not wasting CPU cycles repeating calculations. This ended up making the total run time to be less than 1 second whereas without caching took roughly 30 seconds.

Challenge: Largest Product in a Grid

Posted on: July 14, 2016 2:38:18 AM

This challenge wants you to find the largest product in a 20x20 grid that is 4 numbers in all directions (up, down, left, right, and all diagonals). This was pretty straight forward, I went with a brute force method.

Program.cs
namespace ProjectEuler_11
{
    internal class Program
    {
        private static int[,] _data =
        {
            {08,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91,08},
            {49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00},
            {81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65},
            {52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91},
            {22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80},
            {24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50},
            {32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70},
            {67,26,20,68,02,62,12,20,95,63,94,39,63,08,40,91,66,49,94,21},
            {24,55,58,05,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72},
            {21,36,23,09,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95},
            {78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14,09,53,56,92},
            {16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57},
            {86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58},
            {19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40},
            {04,52,08,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66},
            {88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69},
            {04,42,16,73,38,25,39,11,24,94,72,18,08,46,29,32,40,62,76,36},
            {20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16},
            {20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54},
            {01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48}
        };

        private static int GetLargerHorizontalProduct(int multipleCount, int[,] data, int x, int y, int rows, int cols, int largestProduct)
        {
            // make sure we have enough colums to get the number of values we need
            if (x + multipleCount >= cols)
            {
                return largestProduct;
            }

            int product = data[x, y];

            for (int i = x + 1; i < multipleCount + x; i++)
            {
                product *= data[i, y];
            }

            return product > largestProduct ? product : largestProduct;
        }

        private static int GetLargerLeftDiagnolProduct(int multipleCount, int[,] data, int x, int y, int rows, int cols, int largestProduct)
        {
            if (x + multipleCount >= cols || y - multipleCount < 0)
            {
                return largestProduct;
            }

            int product = data[x, y];

            for (int i = x + 1, j = y - 1; i < x + multipleCount; i++, j--)
            {
                product *= data[i, j];
            }

            return product > largestProduct ? product : largestProduct;
        }

        private static int GetLargerProduct(int multipleCount, int[,] data, int rows, int cols, int largestProduct, int x, int y)
        {
            largestProduct = GetLargerHorizontalProduct(multipleCount, data, x, y, rows, cols, largestProduct);
            largestProduct = GetLargerVerticalProduct(multipleCount, data, x, y, rows, cols, largestProduct);
            largestProduct = GetLargerRightDiagnolProduct(multipleCount, data, x, y, rows, cols, largestProduct);
            largestProduct = GetLargerLeftDiagnolProduct(multipleCount, data, x, y, rows, cols, largestProduct);
            return largestProduct;
        }

        private static int GetLargerRightDiagnolProduct(int multipleCount, int[,] data, int x, int y, int rows, int cols, int largestProduct)
        {
            // make sure we have enough room to get the number of values we need
            if (x + multipleCount >= cols || y + multipleCount >= rows)
            {
                return largestProduct;
            }

            int product = data[x, y];

            for (int i = x + 1, j = y + 1; i < x + multipleCount; i++, j++)
            {
                product *= data[i, j];
            }

            return product > largestProduct ? product : largestProduct;
        }

        private static int GetLargerVerticalProduct(int multipleCount, int[,] data, int x, int y, int rows, int cols, int largestProduct)
        {
            // make sure we have enough rows to get the number of values we need
            if (y + multipleCount >= rows)
            {
                return largestProduct;
            }

            int product = data[x, y];

            for (int i = y + 1; i < y + multipleCount; i++)
            {
                product *= data[x, i];
            }

            return product > largestProduct ? product : largestProduct;
        }

        private static void Main(string[] args)
        {
            const int multipleCount = 4;
            int rows = _data.GetLength(0);
            int cols = _data.GetLength(1);
            int largestProduct = 0;

            for (int x = 0; x < rows; x++)
            {
                for (int y = 0; y < cols; y++)
                {
                    largestProduct = GetLargerProduct(multipleCount, _data, rows, cols, largestProduct, x, y);
                }
            }

            System.Console.WriteLine("Largest multiple found: {0}", largestProduct);
        }
    }
}

Challenge: Highly Divisible Triangular Number

Posted on: July 13, 2016 2:45:35 AM

This challenge wants you to return the first triangular number that has over 500 factors. This challenge was a 2 part, first you have to be able to calculate out a "triangular number" which they define as a natural number added upon itself (similar to Fibonacci numbers) so that the 7th number in the series would be 1+2+3+4+5+6+7 or 28. The second part is being able to quickly calculate all the factors of a number. This was relatively straight forward, so I'll just post the code, there are comments in certain areas as to why I chose to do it like I did.

Program.cs
using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ProjectEuler_12
{
    internal class Program
    {
        private static HashSet GetMultiples(long num)
        {
            // use a hashset to guarantee uniqueness
            HashSet multiples = new HashSet { 1L, num };

            long root = (long)Math.Sqrt(num);

            // we only need to loop up to the square root of the num
            // because we're getting both the low and high factor of the num at once
            // no number could be higher than root*root
            for (long i = 2; i <= root; i++)
            {
                if (num % i == 0)
                {
                    multiples.Add(i);
                    multiples.Add(num / i);
                }
            }

            return multiples;
        }

        private static void Main(string[] args)
        {
            IEnumerable triangularNumbers = TriangularNumberGenerator();

            int multipleCount = 0;
            using (var enumerator = triangularNumbers.GetEnumerator())
            {
                long count = 0;
                long highestMultipleCountAchieved = 0;

                while (multipleCount < 500)
                {
                    enumerator.MoveNext();
                    count++;

                    multipleCount = GetMultiples(enumerator.Current).Count;

                    if (multipleCount > highestMultipleCountAchieved)
                    {
                        highestMultipleCountAchieved = multipleCount;
                        Debug.WriteLine("Number: {2}, Index: {0}, Multiple Count: {1}", count, highestMultipleCountAchieved, enumerator.Current);
                    }
                }

                Console.WriteLine("First triangular number index to have 500 multiples: {0}\r\nTriangular Number: {1}", count, enumerator.Current);
            }
        }

        /// <summary>
        /// The sequence of triangle numbers is generated by adding the natural numbers.
        /// </summary>
        /// <returns></returns>
        private static IEnumerable TriangularNumberGenerator()
        {
            long prevNum = 0;
            long sum = 0;

            while (true)
            {
                sum += ++prevNum;

                // use of yield return lets us go up as high as we need and only
                // as high as we need in this infinite series
                yield return sum;
            }
        }
    }
}

Challenge: Number Letter Counts

Posted on: July 9, 2016 2:02:04 PM

This challenge wants you to get the count of the number of letters in the numbers 1 to 1000. This was a bit of an extra challenge for me because it wants the numbers in a "British compliance" format. This means the word 'and' is included in the number. I didn't do any research on the exact specifics on when the 'and' should be used, I just looked at their example of how to handle the hundreds because we're only trying to get to 1000.

IntToWordHelper.cs
using System.Collections.Generic;
using System.Text;

namespace ProjectEuler_17
{
    public static class IntToWordHelper
    {
        private const string And = "and";
        private const string Space = " ";

        private static readonly string[] BaseNumbers =
        {
            "zero",
            "one",
            "two",
            "three",
            "four",
            "five",
            "six",
            "seven",
            "eight",
            "nine",
            "ten",
            "eleven",
            "twelve",
            "thirteen",
            "fourteen",
            "fifteen",
            "sixteen",
            "seventeen",
            "eighteen",
            "nineteen"
        };

        private static readonly string[] HundredMultiplierNames =
        {
            null, // pad the array so the values line up properly
            "hundred",
            "thousand",
            "million",
            "billion"
        };

        private static readonly string[] TensNames =
                {
            null, // pad the array so the values line up properly
            null,
            "twenty",
            "thirty",
            "forty",
            "fifty",
            "sixty",
            "seventy",
            "eighty",
            "ninety"
        };

        public static string ConvertToWord(int number, bool includeAnd = false)
        {
            List result = new List();

            int[] intArray = GetIntArray(number);

            if (intArray.Length == 0)
            {
                return BaseNumbers[0];
            }

            if (intArray.Length == 1)
            {
                return BaseNumbers[intArray[0]];
            }

            int index = 0;
            int hundredsMultiplierIndex = 0;
            while (index < intArray.Length)
            {
                // take 3 numbers at a time
                int one = intArray[index++];
                int ten = index < intArray.Length ? intArray[index++] : 0;
                int hundred = index < intArray.Length ? intArray[index++] : 0;

                string words = ProcessNumber(hundred, ten, one, includeAnd);

                if (hundredsMultiplierIndex++ > 0 && !string.IsNullOrEmpty(words))
                {
                    words += Space + HundredMultiplierNames[hundredsMultiplierIndex];
                }

                if (!string.IsNullOrEmpty(words))
                {
                    result.Add(words);
                }
            }

            // the words are reversed at this point
            result.Reverse();
            return string.Join(Space, result);
        }

        private static int[] GetIntArray(int num)
        {
            List listOfInts = new List();
            while (num > 0)
            {
                listOfInts.Add(num % 10);
                num = num / 10;
            }

            // the array is reversed, but this helps
            return listOfInts.ToArray();
        }

        private static string ProcessNumber(int hundred, int ten, int one, bool includeAnd)
        {
            StringBuilder sb = new StringBuilder();

            if (hundred > 0)
            {
                sb.Append(BaseNumbers[hundred]).Append(Space).Append(HundredMultiplierNames[1]);

                if (includeAnd)
                {
                    if (ten > 0 || one > 0)
                    {
                        sb.Append(Space).Append(And);
                    }
                }

                sb.Append(Space);
            }

            if (ten > 0)
            {
                if (ten == 1)
                {
                    return sb.Append(BaseNumbers[(ten * 10) + one]).ToString();
                }

                sb.Append(TensNames[ten]).Append(Space);
            }

            if (one > 0)
            {
                sb.Append(BaseNumbers[one]);
            }

            return sb.ToString().Trim();
        }
    }
}

You'll notice that I handle the number in groups of 3, this is because hundreds are always labeled the same regardless of where it is. This allows me to use far less code than would otherwise be needed. The next bit of code needed is the actual counting of the words with the loop of numbers.

Program.cs
using System;

namespace ProjectEuler_17
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            int count = 0;
            for (int i = 1; i <= 1000; i++)
            {
                string word = IntToWordHelper.ConvertToWord(i, true);

                count += word.Replace(" ", "").Length;
            }

            Console.WriteLine("Count: {0}", count);
        }
    }
}

Lastly, as a good practice, some unit tests to prove the functionality.

Tests.cs
using NUnit.Framework;

namespace ProjectEuler_17.Tests
{
    [TestFixture]
    public class Tests
    {
        private static object[] TestValues =
        {
            new object[] {0, "zero", false},
            new object[] {11, "eleven", false},
            new object[] {20, "twenty", false},
            new object[] {47, "forty seven", false},
            new object[] {673, "six hundred seventy three", false},
            new object[] {8172, "eight thousand one hundred seventy two", false},
            new object[] {900000002, "nine hundred million two", false},
            new object[] {123456789, "one hundred twenty three million four hundred fifty six thousand seven hundred eighty nine", false},
            new object[] {int.MaxValue, "two billion one hundred forty seven million four hundred eighty three thousand six hundred forty seven", false}, //2 147 483 647
            new object[] {4019, "four thousand nineteen", false},
            new object[] {28600, "twenty eight thousand six hundred", false },
            new object[] {0, "zero", true},
            new object[] {11, "eleven", true},
            new object[] {20, "twenty", true},
            new object[] {47, "forty seven", true},
            new object[] {673, "six hundred and seventy three", true},
            new object[] {8172, "eight thousand one hundred and seventy two", true},
            new object[] {900000002, "nine hundred million two", true},
            new object[] {123456789, "one hundred and twenty three million four hundred and fifty six thousand seven hundred and eighty nine", true},
            new object[] {int.MaxValue, "two billion one hundred and forty seven million four hundred and eighty three thousand six hundred and forty seven", true}, //2 147 483 647
            new object[] {4019, "four thousand nineteen", true},
            new object[] {28600, "twenty eight thousand six hundred", true },
            new object[] {342, "three hundred and forty two", true }
        };

        [Test, TestCaseSource("TestValues")]
        public void Euler17Test(int number, string expectedResult, bool includeAnd)
        {
            string result = IntToWordHelper.ConvertToWord(number, includeAnd);

            Assert.That(result, Is.EqualTo(expectedResult));
        }
    }
}