Comp210: Principles of Computing and Programming
Fall 2004 -- Homework #10

Readings: Sections 25-32 in HTDP for generative recursion

Sections 33-43 in HTDP for mutation.

All problems will require all (applicable) steps from the design recipe, including a template. Before you tackle the homework, remind yourself of our General Advice, Advice on Homeworks (in particular: staple and provide questions), and the Grading Guidelines.

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.

Generative Recursion: Missionaries and Cannibals

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.

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

For Exercise 32.2.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 Exercise 32.2.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 Exercise 32.2.8, for 15 pts 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.)

Points:

Exercise 32.2.1: 5 pts

Exercise 32.2.2: 10 pts

Exercise 32.2.3: 15 pts

Exercise 32.2.4: 15 pts

Exercise 32.2.5: 10 pts

Exercise 32.2.6: 15 pts

Exercise 32.2.7: 15 pts

85 total points plus 15 extra credit