class Model:
    Man = "M"
    Wolf = "W"
    Sheep = "S"
    Cabbage = "C"
    def __init__(self, left, right):
        self.left = set(left)
        self.right = set(right)

    def __eq__(self,other):
        return other.left == self.left and other.right == self.right

    def __repr__(self):
        return "(%s,%s)" % ( repr(self.left), repr(self.right))

    def pretty(self):
        return ",".join(self.left) + " <-> " + ",".join(self.right)

class Simulator:
    invalid_states = [ set({Model.Wolf,Model.Sheep}), set({Model.Sheep, Model.Cabbage}) ]
    all_entities = set([Model.Man, Model.Wolf, Model.Sheep, Model.Cabbage])

    def simulate(self, state, stack=[]):
        stack = stack + [state]
        if state.right == Simulator.all_entities:
            return stack

        nextStates = []
        if Model.Man in state.left:
            for obj in state.left:
                nextStates.append( Model(state.left - set([Model.Man,obj]) , state.right | set([Model.Man,obj]) ) )
        else:
            for obj in state.right:
                nextStates.append( Model(state.left | set([Model.Man, obj]) , state.right - set([Model.Man,obj]) ) )

        nextStates = filter(
                lambda s: not(
                    s in stack or
                    any([ any([ invalid_state <= m for invalid_state in Simulator.invalid_states ]) and Model.Man not in m for m in [s.left,s.right] ])
                )
            , nextStates) #Remove invalid and previous states.

        for s in nextStates:
            m = self.simulate(s,stack)
            if m is not None:
                return m

        return None


if __name__ == "__main__":
    sim = Simulator()
    result = sim.simulate(Model(Simulator.all_entities,[]))
    i = 0
    for state in result:
        print("%d: %s" % (i,state.pretty()))
        i+=1