Puzzle: The Wolf, the Goat, and the Cabbage

In this post I’ll present a solution to a puzzle using Python. I think the primary value of this post is that it provides an example of how to translate an objective and a set of constraints into data structures and functions that can be interpreted by a computer. This problem breaks down into two interrelated parts:

  1. Translate the problem into data structures and functions
  2. Choose a strategy for finding the solution

The solution strategy may be a Monte Carlo technique, a Genetic Algorithm, a Greedy Search, etc. Once you settle on an translation, you may find that another alternative formulation suits the solution strategy better, so you may need to reformulate the translation. It’s safe to assume that your first solutions will be less elegant than later revisions, so keep working things out.

The Puzzle

On a river bank there is a wolf, a goat, and a cabbage. You have a boat that will hold any single animal or vegetable. You would like to transfer both animals and the vegetable to the other side. However, if you leave the wolf and the goat alone on a bank while you ferry the cabbage across, the wolf will eat the goat. Likewise if you ferry the wolf across while leaving the goat with the cabbage. How do you transport all three passengers, one at a time, so that none consume one another?

Partial Spoiler

The first move is the only possible one: you have to take the goat across. In the second move, you may pick up the wolf or the cabbage. Say you ferry the wolf across next, then you have to put the goat in the boat on your return to the first bank. By shuttling back and forth in this manner, you can get all three passengers to the other side. This could also be reformulated as the estranged aunt, the ex, and the brother-in-law traveling between Minneapolis and St. Paul, and made into a painfully awkward indie film about family ties and the importance of whatever.

The Translation

This is my first draft, so it is necessarily inelegant. I would later like to hunt for a solution using Prolog, but my Prolog Foo isn’t there yet. I would also like to make this more flexible by incorporating more actors, an “edibility matrix”, and the possibility of multiple islands instead of just two banks.

I decided to represent the two banks and the boat as lists. I decided to represent the wolf, the goat, and the cabbage as the integers between zero and two; this allows me to use subtraction to see if one eats another. If the absolute value of their difference is one, then the two passengers should not be left alone on a bank together. The one-passenger-only constraint is checked by checking the length of the list. That’s the main idea.

This first function looks at a single bank and returns True if that bank is safe to leave, and False if leaving that bank would result in something being gobbled.

import random as rnd
import scipy.stats
from pylab import *

def compare( x ):
    '''
    Compare each element of `x` against
    every other element of `x`. Items are
    encoded as integers. If one item can eat
    another item, then the absolute value of
    their difference is equal to one. We will
    consider all of `x`; if we find a one
    anywhere, then we will return False,
    otherwise we will return True.
    '''
    # create a temporary list
    tmp = list()
    # determine how many elements are in x
    N = len( x )
    # for each item in x..
    for i in range( N ):
        # compare to every other item in x
        for j in range( i+1, N ):
            # record the absolute value of
            # the difference of the two items
            tmp.append( abs( x[i] - x[j] ) )
    # if there is a 1 in tmp, that means
    # something got eaten, we return False
    if 1 in tmp:
        return False
    # else return True
    else:
        return True

This function utilizes the function above, and it checks the boat and both banks. If it returns True, then the banks and the boat are in a legal state under the constraints of the problem, otherwise it returns False.

def check( x, y, z ):
    '''
    The first conditional counts how many
    things are in the boat. The next makes
    checks to see if anything left on the
    banks can eat anything else.
    '''
    # If there is more than one item in
    # the boat, then return False
    if len( y ) > 1:
        return False
    # If anything on either bank can eat
    # anything else on that bank, then
    # return False
    if len( y ) == 1:
        if compare( x ):
            if compare( z ):
                return True
        return False
    # If the boat has the right number
    # of occupants and the banks are safe
    # then return True
    return True

I didn’t know what to call this function. (I didn’t know what to call any of these functions.) This function takes the current state, and returns a bunch of potential moves, both legal and illegal. The (smooth) moves are encoded as strings. The original (left) bank is X, the boat is Y, and the other (right) bank is Z. I like this because it reminds me of math problems, and because the left-right analogy holds for the letters when you think about the alphabet.

The string "X1R" means “move the one-indexed element of the list x to the right“, ostensibly into the boat. The string "Z0L" means “move the zero-indexed element of the list z to the left, into the waiting boat. The string "YL" and "YR" mean “move the boat to the left,” and “move the boat to the right,” respectively. This was wholly arbitrary, but I thought this struck a nice balance between brevity and readability while debugging.

def think( x, y, z ):
    '''
    This takes the current state and returns
    a slew of potentially legal and illegal moves.
    '''
    # create an empty list of moves
    moves = list()
    # if the boat is empty..
    if len( y )==0:
        # if there is something on the left bank
        if len( x ) > 0:
            # propose to add each item on
            # the left bank to the boat
            for i in range( len( x ) ):
                moves.append( 'X'+str(i)+'R' )
        # if there is something on the right bank
        if len( z ) > 0:
            # propose to add each item on
            # the right bank to the boat
            for i in range( len( z ) ):
                moves.append( 'Z'+str(i)+'L' )
    # if the boat is full..
    else:
        # propose to drop off the items
        # on the boat on either bank
        moves.append( 'YL' )
        moves.append( 'YR' )
    # return the possible moves
    return moves

This monster takes the current state of the banks and the boat, in addition to a potential move, and then returns either the new state, if it is a legal move, or False. We’ll use this guy in a list comprehension with a if-conditional at the end. (An if-conditional as opposed to a three way if-then-conditional.)

def evaluate( x, y, z, mv ):
    '''
    This takes the current state of the original
    bank `x`, the boat `y`, the other bank `z`, and
    some move `mv` encoded as a string. It returns
    the new state of the banks and the boat if the
    move is a legal one, otherwise it returns False.   
    '''
    # turn a string into a list of strings
    mv = [ i for i in mv ]
    # make copies of the banks, x and z,
    # and the boat in the middle, y
    tx, ty, tz = x[:], y[:], z[:]
    # pop off the first move
    start = mv.pop(0)
    # if the first move is from the boat..
    if start == 'Y':
        # take the item from the boat, y,
        # and put it on the left bank, x.
        if mv[0] == 'L':
            tx.append( ty.pop() )
        # take the item from the boat, y, 
        # and put it on the right bank, z.
        if mv[0] == 'R':
            tz.append( ty.pop() )
    # if the first move is from the left bank..
    elif start == 'X':
        # take that item from the left bank, x,
        # and put it on the boat, y.
        ty.append( tx.pop( int( mv.pop(0) ) ) )
    # if the first move is from the right bank..
    elif start == 'Z':
        # take that item from the right bank, z,
        # and put it on the boat, y.
        ty.append( tz.pop( int( mv.pop(0) ) ) )
    # check to see if the state of the
    # boat and the banks is a valid state
    # and return the new states
    if check( tx, ty, tz ):
        return tx, ty, tz
    # otherwise return False
    else:
        return False

Plot twist: we solved the problem, but we could have done that over a beer, or other tasty adult beverage. What’s really interesting now is the performance of the computer in terms of steps taken to solve the problem over a large number of trials. Recall that we’re making legal moves at random with no cost function to guide our hand at picking the optimal move. It turns out that the computer usually takes 25 to 50 steps to solve the problem, while the minimum number of steps is eleven.

def test():
    # the initial state with the wolf (2),
    # the goat (1), and the cabbage (0)
    x = list([0,1,2])
    y = list()
    z = list()
    # a counter
    i = 0
    # start a loop
    while True:
        # increment the counter
        i += 1
        # if you get all of the passengers
        # to the other bank, then stop the loop
        if len( z ) == 3:
            break
        # generate a bunch of moves
        moves = think( x, y, z )
        # pick out the legal moves
        legal = [ mv for mv in moves if evaluate( x, y, z, mv ) ]
        # evaluate a legal move at random
        x, y, z = evaluate( x, y, z, rnd.choice( legal ) )
        # if we go past 1000 steps, then
        # stop the loop and call it a day     
        if i == 1000:
            break 
    # return the number of iterations
    return i

# create a list for the 
# numbers of iterations
times = list()
# for a bunch of times..
for k in range( 10000 ):
    # see how many iterations it
    # takes to solve the problem
    times.append( test() )

When we’re done we can use matplotlib’s plotting capabilities to make a nice histogram of the numbers of iterations required to solve the problem randomly.

counts, bins, patch = hist( times, bins=60, alpha=0.5 )
title("Number of Steps Required to Solve Puzzle")
ylabel("Number of Solutions")
xlabel("Number of Steps for a Solution")
savefig("puzzle_histogram.png",fmt="png",dpi=200)