1
\$\begingroup\$

I just completed Project Euler problem 18 which is a dynamic programming question through a graph of a triangle of numbers. The goal is to find the path from top to bottom of the triangle that has the largest sum.

In the example below the path is 3->7->4->9.

Say the numbers in the triangle are:

   3
  7 4
 2 4 6
8 5 9 3

I built a jagged array that looks like:

int[][] triangleNumbers = new int[4][]
{
    new int[] {3},
    new int[] {7, 4},
    new int[] {2, 4, 6},
    new int[] {8, 5, 9, 3},
};

Then I made a custom object TriangleNode and converted the numbers into TriangleNodes. Then I went through and connected the lower left and lower right nodes to their parent so I could graph traverse them easily.

//build triangle graph    
TriangleNode[][] triangleGraph = new TriangleNode[triangleNumbers.Length][];

for(int row = 0; row < triangleNumbers.Length; row++)
{
    triangleGraph[row] = new TriangleNode[triangleNumbers[row].Length];
    for(int col = 0; col < triangleNumbers[row].Length; col++)
    {
            //create the Node and save the value
        triangleGraph[row][col] = new TriangleNode(triangleNumbers[row][col]);
    }
}

//connect triangle graph
for(int row = 0; row < triangleGraph.Length; row++)
{
    for(int col = 0; col < triangleGraph[row].Length; col++)
    {
        if(row + 1 == triangleGraph.Length)
        {
                    //bool for easy graph traversing to check if I'm at the bottom row
            triangleGraph[row][col].IsEnd = true;
        }
        else
        {
                    //hook up the Left/Right pointers
            triangleGraph[row][col].Left = triangleGraph[row + 1][col];
            triangleGraph[row][col].Right = triangleGraph[row + 1][col + 1];
        }
    }
}

Obviously this is a ton of code just to build the graph.

Is there an easier way to build this graph? The requirements are that each TriangleNode holds its value and Left/Right pointers to the Nodes in the row directly below. I was thinking there might be some voodoo magic via LINQ to turn the triangleNumbers[][] into the triangleGraph[][], then some more voodoo to hook up the Left/Right pointers.

\$\endgroup\$
  • 2
    \$\begingroup\$ You can throw out a lot of code lad :) The array of arrays is already a tree (you do not need a graph). It is not uncommon to use an array as an underlying data structure for a tree/heap, particularly when the structure is well-defined and does not change, which is the case here. JUST UPDAT THE RUNNING SUM IN PLACE working bottom to top. It is destructive, but all you want is one number. The parent-child relationship is easily defined with indexes and you already spelled it out in code. \$\endgroup\$ – Leonid Apr 20 '12 at 20:45
  • \$\begingroup\$ @Leonid, right, I see what you're saying. To find the solution, I did exactly what you're saying, but with my custom graph. Which made it not destructive (undestructive ?), but I suppose that doesn't matter very much huh. \$\endgroup\$ – jb. Apr 20 '12 at 20:51
  • \$\begingroup\$ Yes, see for instance a comment by magicdead at blog.functionalfun.net/2008/08/… \$\endgroup\$ – Leonid Apr 20 '12 at 20:55
1
\$\begingroup\$

I don't know about "LINQ voodoo", but you could do this in one pass if you reversed the order you're processing the rows. Something like this:

        //build triangle graph    
        var triangleGraph = new TriangleNode[triangleNumbers.Length][];

        for (int row = triangleNumbers.Length - 1; row >= 0; row--)
        {
            triangleGraph[row] = new TriangleNode[triangleNumbers[row].Length];
            for (int col = 0; col < triangleGraph[row].Length; col++)
            {
                //create the Node and save the value
                bool isEnd = row == triangleNumbers.Length - 1;
                triangleGraph[row][col] = new TriangleNode(triangleNumbers[row][col])
                                              {
                                                  IsEnd = isEnd,
                                                  Left = isEnd ? null : triangleGraph[row + 1][col],
                                                  Right = isEnd ? null : triangleGraph[row + 1][col + 1]
                                              };
            }
        }

I'll admit, I didn't test

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.