Solution: Farmer Crosses River Puzzle

def is_everyone_across?
  @item_positions.values.all? { |x| x == :crossed }
end
# farmer move by himself or take another one (only one)
def move(item)
  if @item_positions[item] == :crossed
    @item_positions[:farmer] = @item_positions[item] = :not_crossed
  else
    @item_positions[:farmer] = @item_positions[item] = :crossed  
  end    
  
  @direction = @direction == :forward ? :backward : :forward  
end
def undo_move(item)
  if @item_positions[item] == :crossed
    @item_positions[:farmer] = @item_positions[item] = :not_crossed
  else
    @item_positions[:farmer] = @item_positions[item] = :crossed  
  end  
  @direction = @direction == :forward ? :backward : :forward  
end
def is_safe?
  # OK if farmer is there
  
  items_not_crossed = @item_positions.collect{ |x, y| x if y.to_s == "not_crossed" }.compact
  items_crossed = @item_positions.collect{ |x, y| x if y.to_s == "crossed" }.compact
  
  [items_crossed, items_not_crossed].each do |items_at_one_side|
    
    # false if one side wolf and sheep
    # false if one side sheep and cabbage
    return false if items_at_one_side.include?(:sheep) && items_at_one_side.include?(:cabbage) && !items_at_one_side.include?(:farmer)      
    return false if items_at_one_side.include?(:sheep) && items_at_one_side.include?(:wolf) && !items_at_one_side.include?(:farmer)      
  end
  
  return true
end
def was_done_before?
  @moving_log.values.any?{ |x|
     x[:farmer] == @item_positions[:farmer] && 
     x[:sheep] == @item_positions[:sheep] && 
     x[:wolf] == @item_positions[:wolf] &&
     x[:cabbage] == @item_positions[:cabbage]   
  }
end
def is_item_with_farmer?(item)
  @item_positions[item] ==  @item_positions[:farmer]
end
def print_moving_log
  @moving_log.keys.sort.each do |key|
    action_str = "Step #{key}" 
    
    item_statuses =  @moving_log[key]    
    items_not_crossed = item_statuses.collect{ |x, y| x if y.to_s == "not_crossed" }.compact
    items_crossed = item_statuses.collect{ |x, y| x if y.to_s == "crossed" }.compact
    if key > 0
      prev_statuses = @moving_log[key - 1]
      prev_not_crossed = prev_statuses.collect{ |x, y| x if y.to_s == "not_crossed" }.compact
      prev_crossed = prev_statuses.collect{ |x, y| x if y.to_s == "crossed" }.compact
      
      diff_crossed = items_crossed - prev_crossed
      diff_not_crossed = items_not_crossed - prev_not_crossed
      
      if diff_not_crossed.empty?
        action_str += " <= #{diff_crossed}"          
      else
        action_str += " #{diff_not_crossed} =>"        
      end
      
    end
    puts action_str
    
    format_str = "       #{items_crossed.inspect} |~~~| #{items_not_crossed.inspect}"
    puts format_str
  end
  
end
@item_positions = { :farmer => :not_crossed, :wolf => :not_crossed, :sheep => :not_crossed, :cabbage => :not_crossed }
@items = [:farmer, :wolf, :sheep, :cabbage]
@step = 1
@direction = :forward
@moving_log = { 0 => @item_positions.dup } # moving log starts with all in one side
def cross
  
  if is_everyone_across?
    print_moving_log
    puts "Done!"
    return # exit out of recursion
  end
  @items.each do |item|
    
    next unless is_item_with_farmer?(item)    
    # next if item == :farmer && @direction == :forward
    
    move(item) 
    
    if is_safe? && !was_done_before?
             
      @moving_log[@step] = @item_positions.dup
      
      @step += 1
    
      cross();  # next step, recursive
    
    else
      undo_move(item); # "not safe, revert"         
    end
  
  end  
end
cross()