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:

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.