COMP 210, Spring 2001
Homework 9 : Missionaries and Cannibals
First half due Nov.03 (sat) 23:59 (see below).
Completed program due Nov.07 (wed), at start of class.

Your solution file: Make sure a copy of your solutions is on your owlnet account in your class sub-folder comp210/hw09-halfway.ss, and comp210/hw09.ss, so that if necessary the labby can open and run your program.

You are NOT required to show the template for your programs (woo-hoo!). However, your functions should still follow the template, as appropriate. And of course, each function should still have a contract and purpose, and reasonable test cases.

Before you tackle the homework, remind yourself of our General Advice, Advice on Homeworks (in particular: staple and provide questions), and the Grading Guidelines.

Do exercises 32.2.1 -- 32.2.7.

Warning This problem is manageable only if taken in bite-sized chunks. Start on this homework promptly.
In particular: Finish the first 4 exercises (including test cases, etc) by Saturday 23:59. Leave this work in your owlnet account, in a file titled comp210/hw09-halfway.ss. Leave that file untouched after Saturday; complete your homework in a different file.
(When grading the entire homework, labbies will look at the timestamp of that file, and will check that it contains code substantially the same as the corresponding part of your final submission. Up to 30% off if it doesn't. Minor changes are okay; adding (say) most of your test cases is not considered minor.)

Clarifications (these will make sense only after you've read the problems completely):

• For problem 3, just generate all successor states, even if some of them aren't sensical (e.g. having -1 people on a side of the river). (Problem 4 will filter out the illegal and nonsense states.)
• For problem 6: The picture given helps illustrate the described process. It shows the starting state, below that all the states reachable in one trip (stating that two of them are illegal). Ideally, below that it would show not just the successors from one of the three legal states, but rather the successors of all legal states of the previous layer, i.e. all the states reachable in two boat-trips. (That would best illustrate the process.) After three iterations, you'll have all the states reachable in exactly three boat-trips.
• You can also problem 8, for 1pt of extra credit. If you do, note how it changes the running-time of your program. Also answer: How many different legal states are there?
• You do not need to use any set-struct! for this assignment. Let me strengthen that: Do not use any exclamation points (!s) in your code.
• Note: You should be able to change either of the constants MC or BOAT-SIZE and get results for the corresponding problem (w/o needing to change any other code at all). For bigger boat-trip sizes, can cannibals outnumber missionaries? I don't see an important reason to go one way or the other; for standard comparison of results let's go with:
  Yes, two cannibals and a missionary will cooperate on the treacherous rapids.
  (In fact, you could even have a boolean constant MUTINY_POSSIBLE?, which switches this effect on and off. Probably only changes two lines in your code.)