Homework Six

Missionaries and Cannibals

``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. She 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 who were 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. Strong suggestions (some of which will require additional helper functions):

1. Design a data structure that represents each state in the ``game,'' using define-struct. Determine the initial and final state of the game.
2. Design a function which takes a state, and returns all possible successor states (including states in which the cannibals get to enjoy a meal). Design a function which takes a list of states, and returns a list¹ of states reachable in one additional crossing.
3. Design a function that accepts a state, and determines whether it is a legal (i.e. nobody gets eaten) state. Design a function that takes a list of states, and returns a list of those which are legal states.
4. Design a function that takes a state, and determines if it is the final state. Design a function that takes a list of states, and returns a list of those which are final states.
5. Finally, design a search 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.

   Note: If your program generates all possible states after (say) 7 moves before generating any of the possible states after 8 moves, then you don't need to worry about checking whether you've been in the same state twice. (If you want to add this check, do so only after you've completed the program. How much does this decrease the time needed to run the program?)

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

Be sure to test each of your functions individually, as you write them. Include these tests in what you submit. (Presenting a function without test data makes the graders very skeptical about whether the function actually works.) Policy change: You do not need to include templates in what you hand in, for this and future homeworks. Of course, if you are going to write more than one (say) list function, then writing the template for yourself anyway saves you time & typing, right? Also, the template helps remind you what pieces you have available to work with, so even in generative recursion the template still can spur ideas. If you write an incorrect function that the template would have fixed, we will deduct double points. You should of course still include contracts, short descriptions of each non-obviously-named functions and arguments, and test each function as you go.