Project Euler Problems 18 and 67

Problem 18 and problem 67 are the same problems. The difference being that problem 67 cannot be brute forced. These problems are given a triangle on numbers starting at the top and moving to adjacent numbers on the row below, find the path with the maximum sum.

My first thought was building a tree and using a greedy algorithm to find the path. However, a little thought, and sketching out trees, will show that you can easily build a tree where a greedy algorithm will fail to find maximum path. So what we need to no is traverse the tree and calculate the maximum value for each node. We can do the going down and then scan for the largest value form the nodes that form the bottom of the triangle, or go from the bottom up which causes the root node to have the largest value.

For my solution the triangle represented as an array of arrays. Where each element represents a row of the triangle, and each row is one element longer than the previous. Also each element e[r,i] has to be compared to the elements e[r+1,i] and e[r+1, i+1] where r is index of the row and i the index of the element in that row. The code is as follows.

# receives the table generated from readTable and calculate the largest
# value. The calculation starts with the second to the last table row and
# modifies every element e[r,i] = e[r,i] + max( e[r+1,i], e[r+1, i+1] ).
#
def calcTable( table )
  (table.length - 2).downto(0){ |r|
      table[r].each_with_index{ |val, idx|
          table[r][idx] =
              table[r][idx] + max(
                 table[r+1][idx],
                 table[r+1][idx+1])     
      }        
 }    
table[0][0]
end