Untitled

class State
  attr_accessor :value, :parent, :cost, :distance
  def initialize(value, distance, parent)
    @value, @distance, @parent, @cost = value, distance, parent, 0
  end
  def to_s; value; end
end

def search(strategy, current, final)
  return false if current.nil?
  return true  if current.value == final

  strategy.produce(current)
  search(strategy, strategy.choice, final)
end

# Best-first
class BestFirstStrategy < Array
  attr_reader :visited
  def initialize(state_space)
    @state_space = state_space
    @visited     = []
  end

  def produce(state)
    @state_space.each do |current_state|
      if current_state.parent == state.value
        current_state.cost = current_state.distance + state.cost
        push(current_state)
      end
    end
  end

  def choice
    node = min_by{ |n| n.cost };
    delete_if{ |n| n.value == node.value }
    @visited.push(node) unless node.nil?
    node
  end
end

# state space
ss = []
ss << State.new(:arad,          0,  nil)
ss << State.new(:zerind,       75,  :arad)
ss << State.new(:timisoara,   118,  :arad)
ss << State.new(:sibiu,       140,  :arad)
ss << State.new(:oradea,       71,  :zerind)
ss << State.new(:sibiu,       151,  :oradea)
ss << State.new(:fagaras,      99,  :sibiu)
ss << State.new(:rimnicu,      80,  :sibiu)
ss << State.new(:bucharest,   211,  :fagaras)
ss << State.new(:pitesti,      97,  :rimnicu)

def find_parent(ss, value)
  ss.select do |s|
    s.value == value
  end.first
end

strategy = BestFirstStrategy.new(ss)
puts "Found? #{search(strategy, ss.first, :bucharest)}"

goal = strategy.visited.select{ |s| s.value == :bucharest }.first
puts goal
s = goal
while s != nil
  p s.value
  s = find_parent(ss, s.parent)
end