Due date: Thursday, February 7, 2008.

Ex. 1 Write a python or elisp function that solves the problem of the missionaries and cannibals. See an example of the implementation of the goat-wolf-cabbage problem in the following files, as discussed in class:
goat.py
goat.el

Problem 3 missionaries and 3 cannibals are traveling together. They encounter a river they must cross and there is one boat that can hold up to 2 people at a time, 1 person crossing also being allowed (but the boat doesn't cross by itself). A state is considered safe if on neither side of the river the number of cannibals exceeds the number of missionaries because they will eat the missionaries if that's the case. Note that a special case with all 3 missionaries on one side and all 3 cannibals on the other is still considered safe.

Implementation suggestions (you can choose not to follow them if you have better ideas). The state can be represented by 3 numbers, M for the missionaries on the initial side, C for the number of cannibals on the same side, and B for where the boat is (can be 0/1 or true/false). The number of missionaries and cannibals on the other side is 3-M and 3-C and doesn't need to be stored (or you can store all 5 value if that seems easier). You can group the 3 of them in a list to identify a state.

Note. The problem is solvable with a linear search without backtracking, but you have to make sure that the child states where 2 people are moved are generated and evaluated before those that move just one person at a time.

The problem can be implemented according to a similar model to the goat problem. You could also store the initial state and the path in global variables.

Lisp - External file If you write this in Lisp, it might be a good idea to write the code in one buffer an do the evaluation in a different one. The following function call:
(load "filename")
can be used to load the elisp file "filename.el" and evaluate everything stored in it in the same time. 2 optional parameters can be added as true for noerror and nomessage. The first one being true will not report an error if the file doesn't exist and the second one being true avoids a printing of a message at the start and at the end of the loading process.

This option can avoid having to evaluate each function one by one if the program is big and would separate the code from the evaluation.

Turn in: all the functions in one python/ elisp file, by email only.