Challenge: Maximum Path Sum

Posted on: July 29, 2016 2:00:43 AM
This challenge wants you to find the maximum sum of a triangle of numbers by only moving to downward adjacent numbers. In this example, the maximum sum is 23:
3
7 4
2 4 6
8 5 9 3
The challenge triangle is 15 rows large. This wouldn't be hard or take long to brute force to find the answer, but we want to be able to do it in a more clever way that can easily handle much larger triangles quickly. The challenge itself says that another challenge later on is the same problem, but scaled out to a triangle with 100 rows, which you couldn't brute force. I was able to accomplish this using a learning algorithm, also known as dynamic programming. Here is my code with the triangle hard coded in:
Program.cs
using System;

namespace ProjectEuler_18
{
    internal class Program
    {
        private static int[][] GetGreatestPathSum(int[][] triangle, int index)
        {
            if (index < triangle.Length - 1)
            {
                triangle = GetGreatestPathSum(triangle, index + 1);
            }

            if (index - 1 < 0)
            {
                return triangle;
            }

            int[] top = triangle[index - 1];
            int[] bottom = triangle[index];
            int[] result = new int[top.Length];

            for (int i = 0; i < top.Length; i++)
            {
                result[i] = Math.Max(top[i] + bottom[i], top[i] + bottom[i + 1]);
            }

            triangle[index - 1] = result;

            return triangle;
        }

        private static void Main(string[] args)
        {
            string triangle =
@"75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23";

            string[] triangleLines = triangle.Split(new char[] { '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries);
            int[][] intTriangle = new int[triangleLines.Length][];

            for (int i = 0; i < triangleLines.Length; i++)
            {
                string[] numberStrings = triangleLines[i].Split(' ');
                int[] numbers = new int[numberStrings.Length];

                for (int x = 0; x < numberStrings.Length; x++)
                {
                    numbers[x] = int.Parse(numberStrings[x]);
                }

                intTriangle[i] = numbers;
            }

            int sum = GetGreatestPathSum(intTriangle, 0)[0][0];

            Console.WriteLine("Greatest path sum: {0}", sum);
        }
    }
}
GetGreatestPathSum will call itself until it is at the bottom row of the triangle. It will then calculate the maximum paths the row before could take to that row and replace the previous row with the results. It will then pass this value back so that as it unwinds the stack, the triangle value at [0][0] will eventually be the greatest path value.

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