# Goat, cabbage, wolf¶ [image source: http://xkcd.com/1134]

## How to formulate this as a search problem?

1. What states exist and how do we encode them?
2. What operators can we define to transition between states?
3. What control strategy do we use to find a solution?

## 1. Encoding and state space¶

Let $Items$ be the set of objects in our search problem: $Items = \{Farmer, Wolf, Goat, Cabbage\}$

We encode the state as a pair of sets $(L, R)$, with $L, R \subseteq Items$, representing the position of the farmer, animals and vegetable on the two banks of the river.

The initial state is $s_0 = (\{Farmer, Wolf, Goat, Cabbage\}, \emptyset)$.

The goal state is $s_n = (\emptyset, \{Farmer, Wolf, Goat, Cabbage\})$.

Note that we do not explicitly encode the location of the boat (the farmer always moves with the boat)

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

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

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


### How many different states can we encode this way?¶

We have two subsets of a total of four items, i.e., $2^4 \cdot 2^4 = 256$ possible combinations.

Aside: This is a very small search space -- the number of possible chess board configurations is $O(10^{43})$ 

 Claude Shannon (1950). "Programming a Computer for Playing Chess". Philosophical Magazine 41 (314).

In :
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)

Out:
256


### Valid states (I)

However, most of the 256 combinations do not represent valid states. Two implicit constraints:

1. Everyone must be at one bank of the river at all times: $L \cup R = \{Farmer, Wolf, Goat, Cabbage\}$
2. Nobody can be at both banks at the same time: $L \cap R = \emptyset$

(our state is actually a partition of a 4-element set into two disjoint subsets)

This leaves $2\cdot S(4,2) + 2 = 16$ possible states.

$S(n, k)$ is a Stirling number of the second kind, giving the number of ways that a set with $n$ elements can be partitioned into $k$ non-empty subsets.

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

Out:
[(set(), {'Cabbage', 'Farmer', 'Goat', 'Wolf'}),
({'Cabbage'}, {'Farmer', 'Goat', 'Wolf'}),
({'Wolf'}, {'Cabbage', 'Farmer', 'Goat'}),
({'Goat'}, {'Cabbage', 'Farmer', 'Wolf'}),
({'Farmer'}, {'Cabbage', 'Goat', 'Wolf'}),
({'Cabbage', 'Wolf'}, {'Farmer', 'Goat'}),
({'Cabbage', 'Goat'}, {'Farmer', 'Wolf'}),
({'Cabbage', 'Farmer'}, {'Goat', 'Wolf'}),
({'Goat', 'Wolf'}, {'Cabbage', 'Farmer'}),
({'Farmer', 'Wolf'}, {'Cabbage', 'Goat'}),
({'Farmer', 'Goat'}, {'Cabbage', 'Wolf'}),
({'Cabbage', 'Goat', 'Wolf'}, {'Farmer'}),
({'Cabbage', 'Farmer', 'Wolf'}, {'Goat'}),
({'Cabbage', 'Farmer', 'Goat'}, {'Wolf'}),
({'Farmer', 'Goat', 'Wolf'}, {'Cabbage'}),
({'Cabbage', 'Farmer', 'Goat', 'Wolf'}, set())]


### Valid States (II)

Additional explicit constraint given in the problem description:

• The wolf cannot be left alone with the goat, nor the goat with the cabbage.

We define a function that detects valid states.

In :
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.union(state) != {farmer, wolf, goat, cabbage}:
return False

# second constraint
if state.intersection(state) != 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

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

Out:
[(set(), {'Cabbage', 'Farmer', 'Goat', 'Wolf'}),
({'Cabbage'}, {'Farmer', 'Goat', 'Wolf'}),
({'Wolf'}, {'Cabbage', 'Farmer', 'Goat'}),
({'Goat'}, {'Cabbage', 'Farmer', 'Wolf'}),
({'Cabbage', 'Wolf'}, {'Farmer', 'Goat'}),
({'Farmer', 'Goat'}, {'Cabbage', 'Wolf'}),
({'Cabbage', 'Farmer', 'Wolf'}, {'Goat'}),
({'Cabbage', 'Farmer', 'Goat'}, {'Wolf'}),
({'Farmer', 'Goat', 'Wolf'}, {'Cabbage'}),
({'Cabbage', 'Farmer', 'Goat', 'Wolf'}, set())]


## 2. Operators¶

The set of operators comprises the farmer crossing the river with at most one item, in either direction.

Each operator is a pair $(Boat, d)$, where $Boat \in \{\{Farmer\}, \{Farmer, Cabbage\}, \{Farmer, Goat\}, \{Farmer, Wolf\}\}$ and $d \in \{left, right\}$

Hence, we have $8$ operators for this problem.

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

operators

Out:
{(('Farmer',), 'left'),
(('Farmer',), 'right'),
(('Farmer', 'Cabbage'), 'left'),
(('Farmer', 'Cabbage'), 'right'),
(('Farmer', 'Goat'), 'left'),
(('Farmer', 'Goat'), 'right'),
(('Farmer', 'Wolf'), 'left'),
(('Farmer', 'Wolf'), 'right')}


An operator generates a new state by moving elements from one set to the other. For a state $s=(L,R)$ and an operator $o=(Boat,d)$, we let

$make\_move( s, o ) = \left\{ \begin{array}((L \setminus Boat, R \cup Boat) & \text{if}~~d = right \\ (L \cup Boat, R \setminus Boat) & \text{if}~~d = left \end{array} \right.$

In :
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))


We define the conditions under which an operator $o=(Boat,d)$ can be applied to a state $s=(L,R)$:

• If $d = right$, $Boat \subseteq L$ must hold
• otherwise, $Boat \subseteq R$

I.e., we can only move items that are actually there.

In :
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)


Given a starting state, we can enumerate all valid successor states using the operators.

In :
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


## 3. Control strategy¶

As a control strategy, we choose breadth-first search.

Does our encoding of state and operators by itself guarantee a systematic search?

In :
# 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))


## Examining our solutions¶

In :
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)+'\t'+", ".join(state)+'\t')
if move:
sol_buffer.write(str(" and ".join(move)) + ' to the ' + str(move) + '\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

In :
len(solutions)

Out:
2

In :
print_solution_table(solutions)

Out:
Left bank Right bank move
0 Cabbage, Wolf, Goat, Farmer Farmer and Goat to the right
1 Wolf, Cabbage Goat, Farmer Farmer to the left
2 Cabbage, Wolf, Farmer Goat Farmer and Cabbage to the right
3 Wolf Cabbage, Goat, Farmer Farmer and Goat to the left
4 Wolf, Goat, Farmer Cabbage Farmer and Wolf to the right
5 Goat Cabbage, Wolf, Farmer Farmer to the left
6 Goat, Farmer Cabbage, Wolf Farmer and Goat to the right
7 Cabbage, Wolf, Goat, Farmer

8 rows × 3 columns

In :
print_solution_table(solutions)

Out:
Left bank Right bank move
0 Cabbage, Wolf, Goat, Farmer Farmer and Goat to the right
1 Wolf, Cabbage Goat, Farmer Farmer to the left
2 Cabbage, Wolf, Farmer Goat Farmer and Wolf to the right
3 Cabbage Wolf, Goat, Farmer Farmer and Goat to the left
4 Cabbage, Goat, Farmer Wolf Farmer and Cabbage to the right
5 Goat Cabbage, Wolf, Farmer Farmer to the left
6 Goat, Farmer Cabbage, Wolf Farmer and Goat to the right
7 Cabbage, Wolf, Goat, Farmer

8 rows × 3 columns