#!/usr/bin/env python3
''' https://github.com/gigasquid/wonderland-clojure-katas/tree/master/fox-goose-bag-of-corn
states = near, in boat, far
M = man, F = fox, G = goose, C = corn
loop detection = current state exists in history of states '''

class W(set):
    def __iter__(self):
        for i in set.__iter__(self):
            yield W(i)
        yield W('')
    def __contains__(self, other):
        return other.issubset(set(self))
    def __or__(self, other):
        return W( set.__or__(self, other ) )
    def __add__(self, other):
        return self | other
    def __sub__(self, other):
        return W( set.difference(self, other))
    def __repr__(self):
        return ''.join([ x for x in str(set(self)) if x.isupper() ])

M, F, G, C, _ = [ W(x) for x in list('MFGC')+[''] ]
assert M | F == F | M
assert (F | M) - F == M
assert _ in F + G
assert G + C in M + G + F + C

def fgc(near, boat, far, history):
    step =  [[repr(x) for x in (near, boat, far)]]
    if step[0] in history:
        return
    for loc in (near, far):
        for evil in (F+G, G+C):
            if evil in loc and M not in loc:
                return
    if far == M + F + G + C:
        for i in history+step:
            print(i)
        raise SystemExit

    if M in near:
        for i in near - M:
            fgc(near - i - M, M + i, far, history + step)
    elif M in boat:
        fgc(near, _, far+boat, history + step)
        fgc(near+boat, _, far, history + step)
    elif M in far:
        for i in far - M:
            fgc(near, M + i, far - i - M, history + step)
    else:
        raise ValueException('Man Overboard!')

fgc(M + F + G + C, _, _, [])