Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A linear time solution for the ArrayHopper problem.
numbers = File.read(ARGV.first).split.map &:to_i
best_path = [0]
loop do
current_pos = best_path.last
max_hop = numbers[current_pos]
candidates = (1..max_hop).map { |hop| current_pos + hop }
if candidates.empty?
best_path = ["failure"]
break
end
if candidates.any? { |pos| pos >= numbers.length }
best_path << "out"
break
end
best_path << candidates.max_by { |pos| [numbers[pos] + pos, pos] }
end
puts best_path.join ", "
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment