shortest_knight_path.rb

# find the shortest knight path 
# in a game of chess on an infinite board

def knight_moves(a, b)
  ratio = a.to_f / b.to_f
  unless (((ratio >= 0.5 && ratio <= 2.0) || (ratio <= -0.5 && ratio >= -2.0)) && ((a+b)% 3 == 0))
    puts 'unreachable'
    -1
  else
    (a+b)/3
  end
end

def knight_path(a, b)
  count = knight_moves(a, b)
  return [] if count <= 0
  
  current = { x: 0, y: 0 }
  goal = { x: a, y: b } 
  mem = []
  result = calculate_knight_path(current, goal, 0, mem)
  puts "count: #{count}, result: #{result}"
end

# TODO
def calculate_knight_path(current, goal, moves, mem)
  puts "current: #{current}, moves: #{moves}"  
  points = frontier(current)
  if points.include? goal
    return moves + 1
  end
    
  min = Float::INFINITY
  ordered_points = points.sort{|p| distance(p, goal) }
  
  # TODO
  # p = ordered_points.first
  # m = calculate_knight_path(p, goal, moves, mem)
end

def frontier(p)
  [{ x: p[:x] + 2, y: p[:y] + 1},
   { x: p[:x] - 2, y: p[:y] + 1 },
   { x: p[:x] + 2, y: p[:y] - 1 },
   { x: p[:x] - 2, y: p[:y] - 1 },
   { x: p[:x] + 1, y: p[:y] + 2 },
   { x: p[:x] - 1, y: p[:y] + 2 },
   { x: p[:x] + 1, y: p[:y] - 2 },
   { x: p[:x] - 1, y: p[:y] - 2 }
  ].select{|p| p[:x] >= 0 && p[:y] >= 0}
end

def distance(p1, p2)
  sum = (p1[:x] - p2[:x]) ** 2 + (p1[:y] - p2[:y]) ** 2
  Math.sqrt(sum).abs
end