#!/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(str):
    ''' need the emptySet to be iterable, the rest is sugar and support '''
    def __sub__(self, other):
        return W(''.join( x for x in str(self) if x not in str(other) ))
    def __add__(self, other):
        return W(''.join(set( str(self) + str(other) )))
    def __iter__(self):
        for i in list(str(self)) + ['']:
            yield W(i)
    def __repr__(self):
        return ''.join(sorted(self))
    def __eq__(self, other):
        return repr(self) == repr(other)
    def __contains__(self, other):
        return all( x in str(self) for x in str(other) )

M, F, G, C, _ = [ W(x) for x in list('MFGC')+[''] ]
assert M + F == F + M
assert F + M - F == M
assert sorted([ M, F, _ ]) == sorted([ x for x in M+F ])
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, _, _, [])