#!/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 '''

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

isSub = lambda a,b: all( x in b for x in a )
sub   = lambda a,b: ''.join([ x for x in a if x not in b ])
ls    = lambda a:   iter(list(a)+[''])

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

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

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