triangle kata - recursion

triangle_recursion.rb

# https://github.com/Tarqwyn/Kata-Triangle

# This test is all about finding the shortest route. 
# Given we have triangle, find the shortest path expressed as a sum of the values from top to bottom. 
# At each step you may move to adjacent numbers on the row below.

triangle = [
   [2],
  [3,4],
 [6,5,7],
[4,1,8,3]
]
# answer 11 (2 + 3 + 5 + 1)

triangle1 = [
   [1],
  [4,3],
 [8,2,6],
[2,3,9,7]
]
# answer 9 (1 + 3 + 2 + 3)

triangle2 = [
   [3],
  [6,4],
 [3,4,7],
[3,8,3,6]
]
# answer 14 (3 + 4 + 4 + 3)

triangle3 = [
   [2],
  [9,6],
 [4,5,8],
[1,2,3,6]
]
# answer 15 (2 + 6 + 5 + 2)

triangle5 = [[2], [3,4], [6,5,7], [4,1,2,3], [4,2,8,1,2],[5,4,8,7,3,2]]
# answer 16

triangle6 = [[2], [3, 4], [6, 5, 7], [4, 1, 2, 3], [4, 2, 2, 1, 2], [5, 4, 8, 4, 3, 2], [6, 5, 9, 1, 4, 3, 2]]
# answer 18

big = [
  [55],
  [94, 48],
  [95, 30, 96],
  [77, 71, 26, 67],
  [97, 13, 76, 38, 45],
  [07, 36, 79, 16, 37, 68],
  [48, 07, 9, 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, 6, 48, 53, 18, 74, 98, 15],
  [27, 02, 92, 23, 8, 71, 76, 84, 15, 52, 92, 63, 81, 10, 44, 10, 69, 93]
]

def parse_triangle(triangle)
  num_paths = 2 ** (triangle.length - 1)
  puts "Possible paths = #{num_paths}\n"

  paths = paths(triangle)

  results = []
  paths.map do |path| 
    results << {
      sum: path.inject(0){|sum,x| sum + x },
      path: path.join(",")
    }
  end

  answer = results.min_by{|k| k[:sum] }
  puts "Answer = #{answer}"
end

def paths(triangle, row = 0, col = 0, partial_path = [], paths = [])
  if row == triangle.length
    paths << partial_path
  else
    partial_path << triangle[row][col]
    new_path = partial_path.clone
    
    paths(triangle, row+1, col, partial_path, paths) 

    if row + 1 < triangle.length
      paths(triangle, row+1, col+1, new_path, paths)  
    end
  end

  paths
end

# parse_triangle(triangle)
# parse_triangle(triangle1)
# parse_triangle(triangle2)
# parse_triangle(triangle3)
# parse_triangle(triangle5)
# parse_triangle(triangle6)
parse_triangle(big)