A* search, maybe useful someday

astar.rb

require 'set'

def heuristic(start, goal)
  {
    start: 5, # Not given in the diagram but probably not important.
    a: 4,
    b: 2,
    c: 4,
    d: 4.5,
    e: 2,
    f: 0,
  }[start]
end

def neighbors(n)
  {
    start: %i(a d),
    a: %i(start b),
    b: %i(a c),
    c: %i(b f),
    d: %i(start e),
    e: %i(d f),
    f: %i(d e),
  }[n]
end

def dist(a, b)
  {
    start: {a: 1.5, d: 2},
    a: {start: 1.5, b: 2},
    b: {a: 2, c: 3},
    c: {b: 3, f: 4},
    d: {start: 2, e: 3},
    e: {d: 3, f: 2},
    f: {c: 4, e: 2},
  }[a][b]
end

def reconstruct(prev, current)
  path = [current]
  while prev.include?(current)
    current = prev[current]
    path << current
  end
  path.reverse
end

def a_star(start, goal)
  closed = Set.new
  open = Set.new([start])
  prev = {}

  g_score = Hash.new(1.0 / 0.0)
  g_score[start] = 0

  f_score = Hash.new(1.0 / 0.0)
  f_score[start] = heuristic(start, goal)

  until open.empty?
    current = open.min_by { |x| f_score[x] }
    puts "The set is #{open.map { |x| [x, f_score[x]] }} - we choose #{current}"

    return reconstruct(prev, current) if current == goal

    open.delete(current)
    closed.add(current)

    neighbors(current).each { |neighbor|
      next if closed.include?(neighbor)
      tentative_g_score = g_score[current] + dist(current, neighbor)
      if !open.include?(neighbor)
        open.add(neighbor)
      elsif tentative_g_score >= g_score[neighbor]
        next
      end

      prev[neighbor] = current
      g_score[neighbor] = tentative_g_score
      f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, goal)
      puts "We just set f(#{neighbor}) to #{g_score[neighbor]} + #{heuristic(neighbor, goal)} = #{f_score[neighbor]}"
    }
  end

  nil
end

puts a_star(:start, :f)

astar2.rb

module Heap refine Array do
  def heappush(e)
    self << e
    heapup(size - 1)
  end

  def heappop
    first.tap {
      self[0] = pop
      heapdown(0)
    }
  end

  def heapup(i)
    until i == 0 || (self[i] <=> self[(i - 1) / 2]) >= 0
      self[(i - 1) / 2], self[i] = [self[i], self[(i - 1) / 2]]
      i = (i - 1) / 2
    end
  end

  def heapdown(i)
    loop {
      l = self[2 * i + 1]
      r = self[2 * i + 2]
      smallest = self[i]
      smallest_i = i
      if l && (smallest <=> l) > 0
        smallest = l
        smallest_i = 2 * i + 1
      end
      if r && (smallest <=> r) > 0
        smallest = r
        smallest_i = 2 * i + 2
      end
      break if smallest_i == i
      self[i], self[smallest_i] = [self[smallest_i], self[i]]
      i = smallest_i
    }
  end
end end

using Heap

def astar(start, heuristic, neighbors)
  frontier = [
    [heuristic[start], start],
  ]
  prev = {}

  dist = Hash.new(1.0 / 0.0)
  dist[start] = 0

  until frontier.empty?
    _f, current = frontier.heappop

    return dist[current] if heuristic[current] == 0

    neighbors[current].each { |neighbor|
      new_dist = dist[current] + 1
      next if new_dist >= dist[neighbor]

      frontier.heappush([new_dist + heuristic[neighbor], neighbor])
      prev[neighbor] = current
      dist[neighbor] = new_dist
    }
  end

  raise "no path from #{start}"
end

def adjacent((y, x))
  [
    [y - 1, x],
    [y + 1, x],
    [y, x - 1],
    [y, x + 1],
  ].select { |ny, nx| OPEN[ny][nx] }
end