#!/usr/bin/env python3

from collections import deque

class state:
    def __init__(self, left, right, last_move=None):
        self.left = frozenset(left)
        self.right = frozenset(right)
        self.last_move = last_move

    def accessible(self):
        if 'man' in self.left:
            for x in self.left:
                moving = frozenset(['man', x])
                yield state(self.left - moving, self.right | moving,
                            (self, moving, "==>"))
        else:
            for x in self.right:
                moving = frozenset(['man', x])
                yield state(self.left | moving, self.right - moving,
                            (self, moving, "<=="))

    def success(self):
        return not self.left

    def safe(self):
        def tragic(bank):
            BAD = [('cabbage', 'goat'), ('wolf', 'goat')]
            return 'man' not in bank and \
                    any(frozenset(pair) <= bank for pair in BAD)
        return not tragic(self.left) and not tragic(self.right)

    def __str__(self):
        return "left: {}, right: {}".format(
            " & ".join(self.left), " & ".join(self.right)
        )

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

    def __hash__(self):
        return hash(self.left)

def solve():
    init = state(['man', 'cabbage', 'goat', 'wolf'], [])
    Q = deque([init])
    seen = set([init])
    while Q:
        s = Q.popleft()
        for t in s.accessible():
            if t.success():
                return t
            if t.safe() and t not in seen:
                Q.append(t)
                seen.add(t)

def print_solution(s):
    if s.last_move is not None:
        previous, moving, direction = s.last_move
        print_solution(previous)
        print(direction, " and ".join(moving))

print_solution(solve())