Solucion of well-known puzzle about river crossing.

graph_search.rb

# Search of graph.
#
# Algorightm of graph construction:
#   Define start state.
#   Define finish state.
#   Define valid state.
#   For each not opened node
#     open node
#   end
#
#   Open node:
#     if node != finish_node
#     For each valid state
#       create new descendant node with that state
#       add node to array of closed nodes
#     end
#     set node as opened
#
#   Valid state:
#     no that state in ancestors
#     no sword-bearers without his kninghts and with other ones

# Attributes:
#   state: global db == state of world. Layout of knights, sword_bearers and boat.
#   parent: previous state
#   step: difference between parent and self.
class Node
  attr_accessor :state, :parent, :childs, :step, :parent_states

  PEOPLE_COUNT = 3

  def initialize(state, step)
    @state = state
    @step = step
    @parent = nil
    @parent_states = []
    @childs = []
  end

  def search
    return [step] if solved?
    return nil if childs.empty?
    childs_result = childs.map(&:search).reject(&:nil?).first
    childs_result ? (childs_result << step) : nil
  end

  def generate_childs
    return true if solved?
    return false unless valid?
    movings.
      select { |x| valid_state? x }.
      map { |x| generate_child x }.
      select(&:valid?).
      each(&:generate_childs)
  end

  def movings
    people = state[state[:bank]]
    first = people[:knights].map { |x| { knights: [x] } }
    first += people[:sword_bearers].map { |x| { sword_bearers: [x] } }
    second = first.dup
    first.product(second).map do |one, two|
      keys = (one.keys + two.keys).uniq
      keys.inject(Hash.new { |h, k| h[k] = Hash.new }) do |r, k|
        r.merge(k => ((one[k] || []) + (two[k] || [])).uniq)
      end
    end
  end

  def generate_child(moving)
    child_state = state[:bank] == :right ?
      right_to_left(moving) :
      left_to_right(moving)
    child = Node.new(child_state, moving)
    child.parent = self
    child.parent_states = parent_states << state
    childs << child
    child
  end

  def solved?
    state[:right][:knights].empty? && state[:right][:sword_bearers].empty?
  end

  def valid?
    no_twin_parents? && left_valid? && right_valid?
  end

  def no_twin_parents?
    states = parent_states[0..-2]
    !states.include?(state)
  end

  def right_valid?
    valid_state?(state[:right])
  end

  def left_valid?
    valid_state?(state[:left])
  end

  def valid_state?(hash)
    (1..PEOPLE_COUNT).inject(true) do |r, sword_bearer|
      x = hash[:sword_bearers].include?(sword_bearer) ?
        (hash[:knights].include?(sword_bearer) || hash[:knights].empty?) : true
      x && r
    end
  end

  def left_to_right(hash)
    result = Hash.new { |h, k| h[k] = Hash.new }
    result[:left][:knights] = state[:left][:knights] -
      (hash[:knights] || []).to_a
    result[:left][:sword_bearers] = state[:left][:sword_bearers] -
      (hash[:sword_bearers] || []).to_a
    result[:right][:knights] = state[:right][:knights].to_a + (hash[:knights] || []).to_a
    result[:right][:sword_bearers] = state[:right][:sword_bearers].to_a +
      (hash[:sword_bearers] || []).to_a
    result[:bank] = :right
    result
  end

  def right_to_left(hash)
    result = Hash.new { |h, k| h[k] = Hash.new }
    result[:right][:knights] = state[:right][:knights] -
      (hash[:knights] || []).to_a
    result[:right][:sword_bearers] = state[:right][:sword_bearers] -
      (hash[:sword_bearers] || []).to_a
    result[:left][:knights] = state[:left][:knights].to_a +
      (hash[:knights] || []).to_a
    result[:left][:sword_bearers] = state[:left][:sword_bearers].to_a +
      (hash[:sword_bearers] || []).to_a
    result[:bank] = :left
    result
  end
end


state = {
  right: { knights: [1, 2, 3], sword_bearers: [1, 2, 3] },
  left:  Hash.new { |h, k| h[k] = Hash.new },
  bank: :right
}

root = Node.new(state, 'first')
root.generate_childs
require 'pp'
pp root.search.reverse