home—info—lectures—exams—archive
hw-ec01
Missionaries and Cannibals
breadth-first search
You are NOT required to show the template for your programs.
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.
Do exercises
32.2.1 -- 32.2.7.
Warning
This problem is manageable only if taken in bite-sized chunks.
(At which point, each chunk is quite easy.)
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 do 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.)
home—info—lectures—exams—archive
rad�ford.edu