#!ruby
#
# 2006-06-08 by Laza
# License: enjoy the software and don't complain
#

#
# This software solves Japanese RiverIQGame 
#       See: http://freeweb.siol.net/danej/riverIQGame.swf
#
# Rules:
#   - Only 2 persons on the raft at a time
#   - The father can not stay with any of the daughters without their mother’s presence
#   - The mother can not stay with any of the sons without their father’s presence
#   - The thief (striped shirt) can not stay with any family member if the Policeman is not there
#   - Only the Father, the Mother and the Policeman know how to operate the raft
#

#
# Utilities
#


#
# +def_enum+ defines constants, much like C/C++ enum
#
#       def_enum :OPEN, :CLOSED, :HIGH, :LOW
#
# is equivalent to 
#       OPEN   = :OPEN
#       CLOSED = :CLOSED
#       ...
#
def def_enum *constant_names
    constant_names.each{|sym|
        eval "#{sym.id2name} = :#{sym.id2name}"
    }
end


class Array
    def rest
        self[1..-1]
    end
    #
    # Utility to output [:a,:b,:c] into "[ a b c ]"
    #
    def output_symbols
        "[ "+self.collect{|x| x.to_s}.join(" ") + " ]"
    end
end


#
# JapaneseGamePosition - stores position in an a 3-element array:
#       [ [left river bank] [boat] [right river bank] ]
# Each element is an array of symbols, e.g. [:Policeman, :Father, :Daughter2 ]
#
class JapaneseGamePosition < Array
    BANK1 = 0
    BOAT  = 1
    BANK2 = 2

    def self.[](*args)
        self.new(*args)
    end

    def initialize(arg1, arg2, arg3)
        super [arg1, arg2, arg3]
        resort
    end
    
    def bank1;      self[0];    end
    def boat;       self[1];    end
    def bank2;      self[2];    end
    
    def embark_from_bank( bank, actors )
        opposite_bank bank  # check argument
        raise ArgumentError, "Too many actors"  if actors.length > 2 || actors.length == 0
        
        t = self[bank] - actors
        if t.length != self[bank].length - actors.length
            raise ArgumentError, "Removing #{actors.inspect} from #{self[bank].inspect}"
        end
        self[bank] = t
        
        raise ArgumentError, "Embarking on a boat that is not empty" if ! boat.empty?

        self[1] = actors
        resort
        self
    end
    
    def disembark_to_bank( bank )
        opposite_bank bank  # check argument
        raise ArgumentError, "Too many actors"  if boat.length > 2 || boat.length == 0

        t = (self[bank] + boat).uniq
        if t.length != self[bank].length + boat.length 
            raise ArgumentError, "Duplicates in #{boat.inspect} + #{self[bank].inspect}"
        end
        
        self[bank] = t
        self[BOAT] = []
        resort
        self
    end
    
    
    def opposite_bank( bank )
        case bank
        when BANK1:     BANK2
        when BANK2:     BANK1
        else    raise ArgumentError, "Must be BANK1 or BANK2"
        end
    end
    
    def resort
        [bank1, boat, bank2].each{|arr|
            arr.replace( arr.sort_by{|x| x.to_s} )
        }
    end
    
    def clone
        JapaneseGamePosition[ bank1.clone, boat.clone, bank2.clone ]
    end
    
    def to_s
        line1 = "-> " + bank1.output_symbols + "\n"
        line2 = ( boat.empty?  ?  ""  :  "   " + boat.output_symbols + "\n")
        line3 = "   " + bank2.output_symbols + "\n"
        line1 + line2 + line3
    end
    
end

#
# JapaneseGame - game solver
#    This is a typical tree-search algorithm with early pruning, 
#    which remembers visited states avoiding duplicating work.
#
class JapaneseGame
    
    # Starting and ending position can be changed, and rules too
    attr_accessor   :starting_position, :ending_position, 
                    :elimination_rules, :visited
    
    Actors = [:Mother, :Daughter1, :Daughter2, :Father, :Son1, :Son2, :Policeman, :Robber]
    def_enum   *Actors     # Mother = :Mother; Daughter1=:Daughter1...
    Civilians = Actors.select{|x| x != Robber && x!= Policeman}
    
    #
    # Only Mother, Father, and Policeman can operate the boat
    # 
    BoatCapetains = [ Mother, Father, Policeman ]
    
    
    def initialize()
        
        # position
        @starting_position = JapaneseGamePosition[
            Actors.clone,   # Bank1
            [],             # Boat
            []              # Bank2
        ];
        
        @ending_position = JapaneseGamePosition[
            [],             # Bank1
            [],             # Boat
            Actors.clone    # Bank2
        ];                
        
        #
        # Rules for eliminating moves:
        # E.g. When Mother is present with either Son1 or Son2 without Father
        #       then the move is illegal.        
        #
        
        @elimination_rules = [
            { :present=>Robber, :with=>Civilians,    :without=>Policeman },
            { :present=>Mother, :with=>[Son1, Son2], :without=>Father },
            { :present=>Father, :with=>[Daughter1, Daughter2], :without=>Mother },
        ]
        
        @visited = []
        
    end

    #
    # Check if @elimination_rules apply
    #
    def check( actors_on_one_bank )
        actors = actors_on_one_bank
        
        @elimination_rules.each{|rule|
            if actors.include?( rule[:present] )  &&
               rule[:with].any?{|x| actors.include? x } &&
               ! actors.include?( rule[:without] )
               return false
            end
        }
        return true
    end
    
    #
    # Check that only authorized persons can operate the boat
    #
    def check_boat( actors_in_boat )
        actors_in_boat.any?{|x| BoatCapetains.include? x }
    end
    
    
    #
    # This is the entry function
    #
    def run
        next_step  @starting_position, @ending_position, JapaneseGamePosition::BANK1
    end
    
 
    #
    # next_step() - recursive search:
    #   - if start position equals end position, we have found the solution
    #   - generate all legal moves
    #   - for each move, call next_step() recursively
    #   - if the position/configuration is already visited, skip it
    #
    # Returns an array of moves that solve the proble, or 'nil' if there is no solution. 
    # Each move is an array of boat passengers (actors)
    # e.g.  Move:   [:Father, :Policeman]
    #       Moves:  [  [:Father, :Policeman], [:Policeman], [:Policeman, :Robber] ]
    #
    def next_step( start_pos, end_pos, from_river_bank, level = 0 )

        return [] if start_pos == end_pos
        return false if visited? [from_river_bank, start_pos]   # Remeber this position
    
        from = from_river_bank
        to   = start_pos.opposite_bank( from )  # "to" must be opposite of "from"

        each_move(start_pos, from){|move|
            next_pos = start_pos.clone          # clone - do not modify original position..
                                                # .. that would affect subsequent moves
            next_pos.embark_from_bank   from, move
            next_pos.disembark_to_bank  to

            if check(next_pos[from])  &&  check(next_pos[to])
                moves = next_step( next_pos, end_pos, to, level+1 )
                if moves
                    return [move] + moves
                end
            end
        }
        
        return false
    end
    
    #
    # Check if the position has already been visited.
    # If not, remember it!
    #
    def visited?( position )
        if @visited.include? position
            true
        else
            @visited << position
            false
        end
    end
    
    def output( position )
        puts position.to_s
    end



    #
    # Generate all possible moves, with one or two persons on the boat
    #
    def each_move( position, from )
        
        # Pick one or two actor from one field (from), 
        # and move them to the other field (to)
        
        # First try two actors
        a = position[from]
        for i in 0 ... a.length-1
            for j in i+1 ... a.length
                yield [a[i], a[j]]  if check_boat([a[i], a[j]])
            end
        end

        # Then try only one actor
        for i in 0 ... a.length
            yield [a[i]] if check_boat([a[i]]) 
        end
    end

    def collect_moves( position, from )
        moves = []
        each_move( position, from ){|m| 
            moves << m 
        }
        moves
    end

end





if __FILE__ == $0
    g = JapaneseGame.new
    
    #
    # Solve the game
    #
    moves = g.run
    
    #
    # Print the solution
    #
    if moves
        
        pos = g.starting_position.clone
        g.output( pos )
        
        moves.each_with_index{|move, i|
            puts
            puts "#{i+1}. Move #{move.output_symbols}"
            puts
            pos.embark_from_bank(i%2*2, move)
            pos.disembark_to_bank((i+1)%2*2)
            g.output(pos)
        }
    else
        puts "Failed!"
    end
end