project euler problem 67

problem67.rb

require 'debugger'
require 'awesome_print'

# project euler problem 67 depends on problem 18

# maximum path sum
# use a bottom up strategy
# split into subproblems
# store subproblem result
# don't recompute subproblem


# use a bottom up strategy
# flip over the triangle

# 8 5 9 3
# 2 4 6
# 7 4
# 3

# let's assume the max total path_sum is known from the 1st row to the number 4 in the 2nd row
# at 4 choose max of two paths, 5 or 9 -> 9

# formula:
# array(i,j) = array(i,j) + max( array(i-1, j), array(i-1, j+1) )

# apply the formula to every array(i,j) and keep the most recent result of each subproblem

# 8 5 9 3          =  [ 8, 5, 9, 3 ]
# 2 4 6                 [ 2+max(8,5), 4+max(5,9), 6+max(9,3)]
#                      =  [ 10, 13, 15 ]
# 7 4                    [ 7+max(10,13), 4+max(13,15)]
#                      =  [ 20, 19 ]
# 3                       [ 3+max(20,19)]
#                      =  [ 23 ]

NUM = ARGV[0]
DEBUG = ARGV.include?"debug"

input = File.open("18.txt").readlines
input = File.open("67.txt").readlines if NUM != nil and NUM == "67"

triangle = []
path_sum_triangle = []

# load triangle
# init path sum triangle
input.each do |row|
  triangle << row.split.map(&:to_i)
  path_sum_triangle << []
end

def path_sum(triangle, path_sum_triangle=[], row=0, index=0, total=0)

  return 0 if triangle[row] == nil or triangle[row][index] == nil

  return  total = total + path_sum_triangle[row][index] if path_sum_triangle[row][index] != nil

  #  left adjacent
  left  = path_sum(triangle, path_sum_triangle, row + 1, index, total)

  # right adjacent
  right = path_sum(triangle, path_sum_triangle, row + 1, index + 1, total)

  #  max(left, right)
  max = [left, right].max

  if DEBUG
    ap "at #{triangle[row][index]}"
    ap "left #{left}"
    ap "right #{right}"
    ap "max(left, right) -> #{max}"
    ap "add #{max} + #{triangle[row][index]} -> #{max + triangle[row][index]}"
  end

  # path_sum_triangle contains the the calculated path sum
  path_sum_triangle[row][index] = max + triangle[row][index]

end

ap triangle
max_sum = path_sum( triangle, path_sum_triangle )
ap path_sum_triangle
ap max_sum