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:
- Translate the problem into data structures and functions
- 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.
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?
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.
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
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.
"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
"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 == 'L': tx.append( ty.pop() ) # take the item from the boat, y, # and put it on the right bank, z. if mv == '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)