fox, goose, beans river-crossing puzzle

gistfile1.rb

require 'set'

# I want a set that does a bit more than the standard set
class SpecializedSet < Set
  def self.new(*members)
    super members.flatten
  end

  # a bit terse :P
  # this returns all possible subsets (combinations) of the set
  def subsets
    1.upto(size).flat_map {|n| to_a.combination(n).to_a}.map {|m| self.class.new(m)}
  end

  # formatting for outputting a string
  def to_s
    size > 0 ? to_a.join(', ') : 'nothing'
  end
end

class RiverBank < SpecializedSet
  # is everything okay on the riverbank?
  def okay?
    # fox eats goose
    return false if self == RiverBank.new('fox', 'goose')
    # goose eats beans
    return false if self == RiverBank.new('goose', 'beans')
    # can't leave them all together
    return false if self == RiverBank.new('fox', 'goose', 'beans')
    # the other combinations are okay
    true
  end

  # a more descriptive name
  def number_of_things_on_the_bank
    size
  end
end

class Boat < SpecializedSet
  # the boat can only hold two things
  CAPACITY = 2

  # the boat is okay if the man is there and the boat isn't overload
  def okay?
    on_board?('man') and not overloaded?
  end

  # a convenience method
  def overloaded?
    number_of_things_on_the_boat > CAPACITY
  end

  # a more descriptive name
  def on_board?(entity)
    member?(entity)
  end

  # a more descriptive name
  def number_of_things_on_the_boat
    size
  end
end

# a method to move things across the river
def cross(current_bank, destination_bank, boat)
  # save who is on the boat for comparisons later
  previous_passengers = boat.dup

  # everyone on the boat gets off
  puts "#{boat} get off of the boat, joining #{destination_bank}"
  destination_bank = destination_bank + boat
  boat.clear

  # if all 4 are on the other side, we're done!
  if destination_bank.number_of_things_on_the_bank == 4
    puts "everything is across"
  # not done yet, we'll have to go back across the other way
  else
    # swap banks (our new destination is where we were before)
    destination_bank, current_bank = current_bank, destination_bank

    # find a valid group of passengers to put on the boat
    passengers = current_bank.subsets.find do |passengers|
      # see if we can take these passengers from the river bank and
      (current_bank - passengers).okay? and
      # see if we can put these passengers on the boat and
      (boat + passengers).okay? and
      # make sure we aren't repeating our crossings e.g. the man and
      # goose could safely cross indefinitely, but that's not interesting.
      # need to make sure things are progressing
      (passengers != previous_passengers)
    end

    # passengers get on the boat
    current_bank = current_bank - passengers
    boat = boat + passengers
    puts "#{passengers} get on the boat and crosses the river, leaving #{current_bank} behind"
    # go back across the river
    cross(current_bank, destination_bank, boat)
  end
end

###
#
# Everything is set up, now lets actually run the scenario
#
###


# initial conditions
east_bank = RiverBank.new('man', 'fox', 'goose', 'beans')
west_bank = RiverBank.new
boat = Boat.new

# load the boat
passengers = east_bank.subsets.find {|passengers| (east_bank - passengers).okay? and (boat + passengers).okay?}
boat = boat + passengers
east_bank = east_bank - passengers
puts "#{passengers} get on the boat, leaving #{east_bank} behind"

# start going across the river
cross(east_bank, west_bank, boat)


# OUTPUT:
# man, goose get on the boat, leaving fox, beans behind
# man, goose get off of the boat, joining nothing
# man get on the boat and crosses the river, leaving goose behind
# man get off of the boat, joining fox, beans
# fox, man get on the boat and crosses the river, leaving beans behind
# fox, man get off of the boat, joining goose
# goose, man get on the boat and crosses the river, leaving fox behind
# goose, man get off of the boat, joining beans
# beans, man get on the boat and crosses the river, leaving goose behind
# beans, man get off of the boat, joining fox
# man get on the boat and crosses the river, leaving fox, beans behind
# man get off of the boat, joining goose
# goose, man get on the boat and crosses the river, leaving nothing behind
# goose, man get off of the boat, joining fox, beans
# everything is across