CS 151 Assignment 2 — Missionaries and Cannibals

The purpose of this assignment is to give you some practice with basic Python programming. Your job is to implement the missionaries and cannibals puzzle in Python using state space search. Recall that in this puzzle there are three missionaries and three cannibals who need to cross a river. There is a boat, but it can hold at most two people. An additional constraint is that there must never be more cannibals than missionaries on either side of the river.

1. Read sections 3.1-4.11 of your textbook (pp. 27-90), and supplementary reading #2 (Solving Problems by Searching, by Russell and Norvig). If you don't have the reading packet yet, you can purchase it from Kathy Sheldon in the Pomona CS/Math office (Millikan 220) for $10.

2. The files Search.py and Queues.py implement a general state space search algorithm in Python. Save this code in your own directory and study it until you understand how it works.

3. WaterJug.py is an implementation of a problem called the water jug puzzle. Save this code to your own directory, and study it until you understand how the PitcherState class works with the search routine.

   In this puzzle you are given a three-quart pitcher and a four-quart pitcher. Either pitcher can be filled up completely from a faucet. The entire contents of either pitcher can be poured down a drain. Water may be poured from one pitcher to the other. When pouring, as soon as the pitcher being poured into is full, the pouring stops. There is no additional measuring device and the pitchers have no markings to show partial quantities. A typical problem might be: What steps are required to go from two empty pitchers to exactly two quarts in the four-quart pitcher? To solve this problem using breadth-first search, you would type:

   BreadthFirst(PitcherState(0, 0), PitcherState(0, 2))

4. Using the PitcherState class as a model, write a MissionaryState class that implements the missionaries and cannibals problem. You should not change Search.py or Queues.py. Once implemented, you can conduct a search by calling BreadthFirst or DepthFirst as follows:

   BreadthFirst(MissionaryState(3, 3, 1), MissionaryState(0, 0, 0))
   

Customizing Emacs for CS 151

If you like the color scheme I use in class for editing Python code, here are instructions for customizing Emacs in the same way. This also defines the keyboard shortcuts CTRL-c c and CTRL-c u, which make it easy to comment and uncomment regions of Python code. Let me know if you have questions about anything.

Turning in your homework