trolls.rb

map = [
  [8, 8, 4, 4, 5],
  [4, 9, 6, 4, 8],
  [8, 6, 4, 1, 2],
  [4, 8, 2, 6, 3],
  [0, 6, 8, 8, 4]
]

look = lambda { |position, visited, coins, path|
  if visited.include? position
    return false 
  end
  coins -= map[position[0]][position[1]]
  if coins < 0
    visited.delete position
    return false
  end
  if position[0] == 0 and position[1] == 4 
    return true if coins == 0
    puts "#{coins} #{path}" #Show possible end game win scenarios
    visited.delete position
    return false
  end

  visited.push [position[0], position[1]]
  deltas = [
    [-1, 0, 'n'], 
    [0, 1, 'e'], 
    [1, 0, 's'],
    [0, -1, 'w'],
  ]

  deltas.each do |delta|
    delta_y, delta_x, direction =  delta
    new_y = position[0] + delta_y
    new_x = position[1] + delta_x
    next if new_y < 0 or new_y > 4 or new_x < 0 or new_x > 4
    return true if look.call([new_y, new_x], visited, coins, path + direction)
  end
  visited.delete position
  return false
}

found = look.call([4, 0], [], 35, "")
puts found