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

since the man continues to loop over the four states, can we use that?
yes, however not as legibly as 04.py
'''

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

def ls(a):
    ''' sometimes you need to carry nothing '''
    return [ set(x) for x in a ] + [ set() ]

def fgc(step, history):
    #print([ ''.join(list(x)) for x in step ])
    near, ntf, far, ftn = step
    if step in history:
        return
    for loc in (ntf, ftn):
        if len(loc) > 2:
            return
    for loc in (near, far):
        for evil in (F|G, G|C):
            if evil <= loc and not M <= loc:
                return
    if far == M | F | G | C:
        print('done')
        for i in history+[step]:
            print([ ''.join(list(x)) for x in i ])
        raise SystemExit

    loc = len(history)
    loc, nxt = [ x % 4 for x in [ loc, loc + 1 ] ]
    if loc in ( 0, 2 ):
        for i in ls(step[loc] - M):
            new = [ set(list(x)) for x in step ]
            new[loc] -= i | M
            new[nxt] |= i | M
            fgc(new, history + [step])
    else:
        new = [ set(list(x)) for x in step ]
        new[nxt] |= new[loc]
        new[loc]  = set()
        fgc(new, history + [step])


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