Assignment 8: Missionaries and Cannibals

Before you tackle the homework, remind yourself of our General Advice, Advice on Homeworks, and Grading Guidelines. Above all, keep your work neat and honest.

This week's assignment is a single project. You receive 12pts for completing the project. For partial credit, see below.

``Once upon a time, three missionaries were being guided through a jungle by three cannibals to the nearest mission station. After some time, they arrived at a wide river, filled with deadly snakes and fish. There was no way to cross the river without a boat. Fortunately, they found a row boat with two oars after a short search. Unfortunately, the boat was too small to carry all of them. It could barely carry two people at a time. Worse, because of the river's width there was no way to bring the boat back other than to row it back.

``Since the missionaries could not trust the cannibals they had to figure out a plan to get all six of them safely across the river. Luckily one of the missionaries had taken Comp 210 at Rice University and knew how to solve their problem. He devised a Scheme program to search a solution, implemented it on her laptop, ran it and used the computed solution to get them all safely to the other side of the river.''

What was the problem? The kind of cannibals in the story kill and eat missionaries as soon as there are more cannibals than missionaries at some place. Thus, our Comp 210 graduate had to devise a plan that guaranteed that there were never any missionaries in the minority at either side of the river, or in the boat. However, the cannibals can be trusted to cooperate otherwise (they won't abandon any potential food, just as the missionaries won't abandon any potential converts).

Implement a Scheme program that finds a solution to the problem.

1. Design a data representation for each state of the river crossing.
2. Determine the initial and final state of the game.
3. Design a function which consumes a state and returns a list of all possible successor states, i.e., states reachable with one crossing. This list may include states in which the cannibals get to enjoy a meal.
4. Define a generalized version that consumes a list of states, and returns a list of states reachable with one additional crossing.
5. Design a function that accepts a state, and determines whether it is a legal (i.e. nobody gets eaten) state.
6. Design a generalized function that consumes a list of states and returns the sub-list of legal states.
7. Design a function that consumes a state and determines if it is the final state.
8. Design a generalized version that consumes a list of states and returns the sub-list of final states.
9. Finally, design a function that generates moves in the ``game'' until it has found a final state. Its result is the list of boat trips that the group has to make in order to get everyone from one side of the river to the other.

Hints: If the final program utilizes the first half-dozen functions, it will generate all states reachable with, say, seven crossings before it generates all those states reachable with eight crossings. Therefore you do not have to worry about cycles in solution attempts. Why are there cycles and why is this a problem for a computer program?

You might wish to write the program in three stages. Your first program should represent states in a manner that allows the program to find out whether a final state is reachable. This first program can return true if it is possible. Then, for the second edition, you must create state representations that include the list of crossings that got the the group to this state. Of course, for the initial state this is just the empty list. For the third, final, and completely optional stage (that is, if you complete it, you will learn something but you won't get credit for it) eliminate all those states that represent solution attempts in which the same state would be reached (at least) twice. If you implement this third edition, you might wish to determine whether this measure saves time and how much it saves.

You are welcome and encouraged to use Scheme's library functions as you see fit. This includes such operations as append, filter, foldl, foldr, map, etc. It will make your life easier.

Product: Your program must be annotated with

1. a concise description of your data representation for river crossings; you may wish to include a paragraph on how a state represents "reality";
2. a note for each function contract that concisely (in one line) specifies which design recipe you used to develop the function
   You do not have to turn in the program examples, the templates, or the tests.
   Of course, that does not mean that you don't need to go through these stages as you develop the program!
3. the result of your program.

Warning: The program can take about a minute to run on the Ryon Sparcs (or, if you mistakenly have an infinite loop, much, much longer).

Partial Credit: If you do not get the program to work, state so at the top of your solution. Turn in your complete work for each of the functions you finished instead. That is, show your data definition, contract, program examples, template, function definition, and test cases. Alternatively, show the programs or data definitions from which you abstract. We will give up to nine points for partial solutions, if they show you made a systematic effort for each sub-problem.

Suggestion: You are now capable of tackling the final project.