Answer to Question #329606 in Python for Toilet Gamer

Question

Consider the Farmer-Wolf-Goat-Cabbage Problem described below:

Farmer-Wolf-Goat-Cabbage Problem

There is a farmer with a wolf, a goat and a cabbage. The farmer has to cross a river with all three things. A small boat is available to cross the river, but farmer can carry only one thing with him at a time on the boat. In the absence of farmer, the goat will eat the cabbage and wolf will eat the goat. How can the farmer cross the river with all 3 things?

Initial state: (L, L, L, L)

Operators:

1.      Move farmer and wolf to the opposite side of river if goat and cabbage are not left alone.

2.      Move farmer and goat to the opposite side of river.

3.      Move farmer and cabbage to the opposite side of river if wolf and goat are not left alone.

4.      Move farmer alone to the opposite side of river if wolf and goat or goat and cabbage are not left alone.

Goal state: (R, R, R, R)

Write a Python program that uses breadth-first search algorithm to solve the above problem.

Answer 1

farmer, goat, cabbage, wolf = ("farmer", "goat", "cabbage", "wolf")
carryables = (goat, cabbage, wolf, None)

forbiddens = (set((goat, cabbage)), set((wolf, goat)))


def mayhem(cfg):
    for shore in cfg[0]:
        if farmer not in shore:
            for forbidden in forbiddens:
                if shore.issuperset(forbidden):
                    return True
    return False


def done(cfg):
    left, right = cfg[0]
    return left == set()


def ferry(cfg, item):
    left, right = [set(x) for x in cfg[0]]
    if farmer in left:
        src, dst = left, right
    else:
        src, dst = right, left
    if item and not item in src:
        return None
    desc = "    The farmer goes -->" if farmer in left else "    The farmer goes <--"
    src.remove(farmer)
    dst.add(farmer)
    if item:
        src.remove(item)
        dst.add(item)
        desc += " with the " + item
    else:
        desc += " alone"
    return ((left, right), desc)


def printcfg(cfg, level=0):
    left, right = cfg[0]
    verdict = "(Not allowed)" if mayhem(cfg) else "(Ok)"
    print(level+1, ", ".join(left), "~~~~~", ", ".join(right), cfg[1], verdict)


def onegeneration(cfg):
    followups = []
    for item in carryables:
        followup = ferry(cfg, item)
        if not followup: continue
        followups.append(followup)
    return followups


def generate(cfg, level=0):
    solutionstack.extend([None] * (level - len(solutionstack) + 1))
    solutionstack[level] = cfg[1]
    printcfg(cfg, level)
    childs = onegeneration(cfg)
    for child in childs:
        if mayhem(child):
            continue
        if child[0] in previouscfgs:
            continue
        previouscfgs.append(child[0])
        generate(child, level + 1)


cfg = ((set((farmer, goat, cabbage, wolf)), set()), "")
previouscfgs = [cfg[0]]
solutionstack = []
print("Trace of the recursive solution-finding process:")
print("     L      L      L       L  RIVER")
generate(cfg)
print("   RIVER    R       R       R     R")
print("\n\nThe solution to the problem:")
for step in solutionstack:
    if step:
        print("  ", step)