pathfinder

pathfinder.rb

input = []
input << [500]
input << [100, 200]
input << [300, 400, 500]
input << [200, 200, 500, 900]
input << [900, 100, 200, 100, 101]
input << [100, 900, 100, 100, 100, 700]

# n = input.size

# add some for benchmarking
n = 2000
(input.size .. n).each do |i|
  input[i] = Array.new(i+1) { 100 + rand(900) }
end

@sums = [input[0]]

def max_prev_sum_k(i, k)
  return 0 if k == 0
  return k - 1 if k == i
  @sums[i - 1][k] > @sums[i - 1][k - 1] ? k : k - 1
end

(1 .. n - 1).each do |i|
  @sums[i] = Array.new(i + 1, 0)
  (0 .. i).each do |k|
    #    @sums[i][k] = input[i][k] + @sums[i - 1][max_prev_sum_k(i, k)] ## slow 
    @sums[i][k] = input[i][k] + @sums[i - 1][(k == 0 ? 0 : (k == i ? k - 1 : (@sums[i - 1][k] > @sums[i - 1][k - 1] ? k : k - 1)))] ## fast!
  end
end

path = [@sums.last.index(@sums.last.max)]

(n - 1).downto(1) do |i|
  path.unshift max_prev_sum_k(i, path[0])
end

puts path.inspect