Connect graph from 2D array

Question

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.

• Leonid: 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.
• jb.: @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.
• Leonid: Yes, see for instance a comment by magicdead at blog.functionalfun.net/2008/08/…

Answer 1

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