Maximum Sum path Triangle and get the numbers which were added C#

Question

I'm trying to get the maximum Sum from Top to Bottom of the Triangle Input should be like this

                      5
                    94 48
                   95 30 96
                 77 71 26 67
                97 13 76 38 45
              07 36 79 16 37 68
             48 07 09 18 70 26 06
           18 72 79 46 59 79 29 90
          20 76 87 11 32 07 07 49 18
         27 83 58 35 71 11 25 57 29 85
        14 64 36 96 27 11 58 56 92 18 55
       02 90 03 60 48 49 41 46 33 36 47 23
      92 50 48 02 36 59 42 79 72 20 82 77 42
     56 78 38 80 39 75 02 71 66 66 01 03 55 72
    44 25 67 84 71 67 11 61 40 57 58 89 40 56 36
   85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52
  06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15
27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93

Output should be:

Maximum total: 1320
Path (for example) : 55 - 48 -30 - etc

The path should be the number which I added together to get the result 1320. am able to find the SUM (1320) but I cannot find a way to find all the number that were summed up. My code returns all numbers not only those were summed up.

static void Sum()
    {
        int[,] list = new int[18, 19];
        int[,] list2 = new int[18, 19];

        string input = @"55
                        94 48
                       95 30 96
                     77 71 26 67
                    97 13 76 38 45
                  07 36 79 16 37 68
                 48 07 09 18 70 26 06
               18 72 79 46 59 79 29 90
              20 76 87 11 32 07 07 49 18
            27 83 58 35 71 11 25 57 29 85
           14 64 36 96 27 11 58 56 92 18 55
         02 90 03 60 48 49 41 46 33 36 47 23
        92 50 48 02 36 59 42 79 72 20 82 77 42
      56 78 38 80 39 75 02 71 66 66 01 03 55 72
     44 25 67 84 71 67 11 61 40 57 58 89 40 56 36
   85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52
  06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15
27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93";
        var charArray = input.Split('\n');

        for (int i = 0; i < charArray.Length; i++)
        {
            var numArr = charArray[i].Trim().Split(' ');

            for (int j = 0; j < numArr.Length; j++)
            {
                int number = Convert.ToInt32(numArr[j]);
                list[i, j] = number;
                list2[i, j] = number;
            }
        }

        StringBuilder path = new StringBuilder();
        for (int i = 16; i >= 0; i--)
        {
            for (int j = 0; j < 18; j++)
            {
                //list[i, j] = Math.Max(list[i, j] + list[i + 1, j], list[i, j] + list[i + 1, j + 1]);
                if (list[i, j] + list[i + 1, j] > list[i, j] + list[i + 1, j + 1])
                {
                    if (list2[i, j] > 0)
                        path.Append(list2[i, j] + " - ");
                    if (list2[i+1, j] >0)
                        path.Append(list2[i+1, j] + " - ");

                    list[i, j] = list[i, j] + list[i + 1, j];
                }
                else
                {
                    //path.Append(list2[i, j] + " - " + list2[i + 1, j + 1]+ " - ");
                    if (list2[i, j] > 0)
                        path.Append(list2[i, j] + " - ");
                    if (list2[i + 1, j] > 0)
                        path.Append(list2[i + 1, j] + " - ");

                    list[i, j] = list[i, j] + list[i + 1, j + 1];
                }
            }
        }

        Console.WriteLine(string.Format("Maximum total: {0} \n Path {1}", list[0, 0], path));

I have been trying for 4 days to solve it for 4 day but I failed, I appreciate your help. Thank you

Answer 1

"...but I cannot find a way to find all the number that were summed up"

You are so close. You maintain all the information you need to be able to construct the path through the pyramid. list looks like this after the nested for loops. Can you think of a simple way to traverse list to find the path?

1320 
1265 1130 
1171 1061 1082 
1076 1031 986  925  
999  903  960  813  858  
902  890  884  754  775  813  
895  854  805  682  738  694  745  
793  847  796  664  644  668  660  739  
719  775  717  618  585  543  589  631  649  
643  699  630  607  553  522  536  582  554  631  
566  616  512  572  482  466  511  509  525  509  546  
489  552  465  476  454  455  448  453  433  384  491  467  
487  445  462  416  383  406  364  407  400  348  342  444  426  
348  395  372  414  332  347  253  322  328  328  225  260  367  384  
292  220  317  334  293  272  216  251  245  262  204  224  257  312  292  
248  195  145  250  222  172  205  129  190  205  146  135  135  217  256  219  
33   163  120  98   165  124  121  94   75   143  98   129  134  62   118  167  108  
27   2    92   23   8    71   76   84   15   52   92   63   81   10   44   10   69   93   

Answer 2

A different approach to dynamic programming is to do a depth first search since the pyramid is a just a tree. This corresponds to the "brute force" technique in the blog @peterduniho referenced. The basic idea is very simple: you examine each and every path from the root (55) to the leaf nodes (27, 2, etc..).

I setup scaffolding to get you going. You might find this representation of the data a little easier to work with since you don't have to think so much about indices and off-by-one errors and you can concentrate more on how to solve the problem. It also makes using Visual Studio's debugging features easier (you can put a breakpoint in the code and look at descendants and descendants of descendants, etc.. for example)

If you are not familiar with recursion, the key thing to note in the code is that DepthFirstSearch calls itself.

(I think dynamic programming is the better way to solve this problem but I am just posting this as an alternative)

    public void Solve()
    {
        string input = 
                                @"55
                                94 48
                               95 30 96
                             77 71 26 67
                            97 13 76 38 45
                          07 36 79 16 37 68
                         48 07 09 18 70 26 06
                       18 72 79 46 59 79 29 90
                      20 76 87 11 32 07 07 49 18
                    27 83 58 35 71 11 25 57 29 85
                   14 64 36 96 27 11 58 56 92 18 55
                 02 90 03 60 48 49 41 46 33 36 47 23
                92 50 48 02 36 59 42 79 72 20 82 77 42
              56 78 38 80 39 75 02 71 66 66 01 03 55 72
             44 25 67 84 71 67 11 61 40 57 58 89 40 56 36
           85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52
          06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15
        27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93";

        var tree = input.Split('\n')
            .Select(line => line.Trim()
                .Split(' ')
                .Select(s => new Node(int.Parse(s.Trim())))
                .ToArray())
            .ToArray();

        for (var i = 0; i < tree.Length-1; i++)
        {
            for (var j = 0; j < tree[i].Length; j++)
            {
                tree[i][j].Descendants.Add(tree[i + 1][j]);
                tree[i][j].Descendants.Add(tree[i + 1][j+1]);
            }
        }
        var root = tree[0][0];
        int maxSum = 0;
        DepthFirstSearch(tree[0][0],  ImmutableList<Node>.Empty.Add(root), 0, ref maxSum);
    }


    private void DepthFirstSearch(Node root, ImmutableList<Node> path, int runningSum, ref int maxSum)
    {
        CheckBaseCase(root, path, ref maxSum);
        foreach(var node in root.Descendants)
        {
            runningSum += node.Value;
            DepthFirstSearch(node, path.Add(node), runningSum, ref maxSum);
        }
    }

    private void CheckBaseCase(Node root, ImmutableList<Node> path, ref int maxSum)
    {
        // Fill me in!
    }

   [DebuggerDisplay("Value = {Value}, DescendantCount={Descendants.Count}")]
   class Node
   {
       public Node(int value)
       {
           Value = value;
       }
       public int Value{ get; }
       public List<Node> Descendants { get; } = new List<Node>();
   }

Answer 3

Given the homework nature of the question, I am loathe to solve it outright. Any answer that did so would be doing you and your teacher a disservice.

That said, given that you're aware of the dynamic-programming approach described at https://www.mathblog.dk/project-euler-18/, I hope it's helpful to provide some insight regarding what your solution should look like, without actually writing the solution for you.

So in particular, let's consider the algorithm described. The essence of the algorithm is that it resolves all of the subproblems at the bottom of your triangle, folding (or "collapsing") the result from the bottom row into the next row above.

The key is to note that when this is done, for each value in the next row above that is updated, it's updated by adding one or the other of the values left or right from the row immediately below. If you want to be able to display the path that the maximal solution takes through the triangle, you just need to remember at each row from which direction the new, maximal value was calculated.

This is easily done by introducing a new array with the same dimensions as the original, but where instead of the values from the input, you store in the array some indication as to whether the value was calculated by summing a value from the left or right in the row below (naturally, this array won't need any actual data in the bottom-most row…you can either just ignore the values there, or you can actually make the array one row smaller than the original data's array).

Then once you complete the algorithm and have reached the top of the numeric array, you'll also have this sort of "bread-crumbs" array that tells you how you got there. Starting at the top row, which has only one element, you can look at the bread-crumbs array to recall which element from the next row down was added to that element.

With that information, you now know which element from the second row was used. And the bread-crumbs array tells you which element from the row below that (the third row) was used. And so on.

There are other ways to design your data structure to achieve the same goal. But they will all boil down to the same basic idea: storing somewhere the information of how each sum was calculated, so that you can reproduce that later.

It should not be hard for you to modify the code you have already, to include this additional array and then to use that later to recall the path that was taken.

Finally, in the spirit of the dynamic-programming aspect of this, I'll point out that if you build your output string as you go along, you don't even need a multidimensional array. Instead, you just start with an array holding strings, which is as long as the next-to-last row, and where the first string stored in each array element is simply the number that was added to the current element in the next-to-last row.

At each new row, you will replace each string by prepending (i.e. inserting at the beginning) the original number that was in the previous row's location which was used for the current sum. You need to track the original number – which is easy because you already maintain two copies of the array in your code.

And I'll note that this "keep just a one-dimensional array" technique can work for the running totals as well. I.e. the only two-dimensional array you really need is the one that has the original data. At each iteration, you only care about the most recent row, so you just need a one-dimensional array for that row.