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

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

def fgc(near, far, history):
    step = [near, far]
    if step in history:
        return
    unmanned, = [ x for x in step if not M <= x ]
    if F|G <= unmanned or G|C <= unmanned:
        return
    if far == M | F | G | C:
        print('Solution')
        for i in history + [step]:
            print([ ''.join(list(x)) for x in i ])

    if M <= near:
        for i in [ set(x) for x in near ]:
            fgc(near - i - M, far|M|i, history + [step])
    else:
        for i in [ set(x) for x in far ]:
            fgc(near|M|i, far - i - M, history + [step])

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