Goat, cabbage, wolf¶

farmer = 'Farmer'
wolf = 'Wolf'
goat = 'Goat'
cabbage = 'Cabbage'

initial_state = ({farmer, wolf, goat, cabbage}, set())

goal_state = (set(), {farmer, wolf, goat, cabbage})

def powerset(s):
    from itertools import chain, combinations
    return [set(x) 
            for x in chain.from_iterable(
                combinations(s, r) for r in range(len(s) +1))]

items = {farmer, wolf, goat, cabbage}

subset_pairs = [(L, R) for L in powerset(items) for R in powerset(items)]

len(subset_pairs)

[(L, R) 
 for (L, R) in subset_pairs 
 if L.union(R) == items and L.intersection(R) == set()]

def is_valid_state(state):
    """A state is a 2-tuple of sets (L, R). It is valid if it satisfies our three constraints."""
    # first constraint
    if state[0].union(state[1]) != {farmer, wolf, goat, cabbage}:
        return False
    
    # second constraint
    if state[0].intersection(state[1]) != set():
        return False
    
    # third constraint
    for bank in state:
        if farmer not in bank and (
                (goat in bank and wolf in bank) or
                (goat in bank and cabbage in bank)):
            return False
        
    return True

[state for state in subset_pairs if is_valid_state(state)]

operators = {(items, direction) 
             for items in {(farmer, wolf), 
                           (farmer, goat), 
                           (farmer, cabbage), 
                           (farmer,)}    # the farmer can cross alone.
             for direction in {'left', 'right'}}

operators

def make_move(state, operator):
    """We apply an operator by removing elements from one set 
    and adding them to the other."""
    left, right = state
    items, direction = operator    
    if direction == 'right':
        return (left.difference(items), right.union(items))
    else:
        return (left.union(items), right.difference(items))

def is_valid_move(state, operator):
    """An operator can be applied to a state if everyone crossing 
    the river is on the correct bank."""
    items, direction = operator

    # the river bank where the move starts
    from_bank = 0 if direction == 'right' else 1
    
    return state[from_bank].issuperset(items)

def valid_successors(state):
    succ = []
    for op in operators:
        next_state = make_move(state, op)
        if is_valid_move(state, op) and is_valid_state(next_state):
            succ.append((next_state, op))
    return succ

# represent partial solutions as a tuple of visited states, 
# and list of operators applied so far
queue = [([initial_state], [])]

# the solutions we find go here
solutions = []


while len(queue) > 0:
    # do BFS: take first element from queue:
    visited, oplist = queue.pop(0)
    # last visited is current state:
    current_state = visited[-1]
    for new_state, op in valid_successors(current_state):
        new_visited = visited + [new_state]
        new_oplist = oplist + [op]
        if new_state == goal_state:
            solutions.append((new_visited, new_oplist))
        elif new_state not in visited:
            queue.append((new_visited, new_oplist))

import pandas as pd
from StringIO import StringIO

def print_solution_table(solution):
    sol_buffer = StringIO()

    def print_row(state, move):
        sol_buffer.write(", ".join(state[0])+'\t'+", ".join(state[1])+'\t')
        if move:
            sol_buffer.write(str(" and ".join(move[0])) + ' to the ' + str(move[1]) + '\n')
        
    states, operators = solution
    for state, move in zip(states, operators):
        print_row(state, move)
    last_state = states[-1]
    print_row(last_state, None)
    
    sol_buffer.seek(0)
    df = pd.read_table(sol_buffer, names=['Left bank', 'Right bank', 'move']).replace(float("NaN"), "")
    return df

len(solutions)

print_solution_table(solutions[0])

print_solution_table(solutions[1])