The assignment specifies that "When a cannibal or
missionary arrives at
the river bank, he MUST get on the boat..." She then prints out that she
got on the boat. So what do we do if two cannibals arrive, get in the
boat, and then 4 missionaries arrive? We have to get the cannibals out of
the boat to make room for three missionaries to go, right? Should we
print that the cannibals get out? Or should we have everyone wait on the
bank until there's a valid combination, and then everyone in the valid
combination gets in the boat?
Certainly, the best solution is to have everyone wait on the bank
until there's a valid combination. The actual wording of the problem
does seem to prohibit it, though.
To the extent that it's reasonably possible, both cannibals and
missionaries should be served on a more or less first-come-first-
served basis. That is, you needn't queue them explicitly, but your
solution shouldn't involve deliberately delaying people who could be
sent across right away.
Given that caveat, I think it's reasonable to have everyone wait on
the bank until a complete valid boatload is available, and then allow
boarding. Note, however, that it's probably more complicated this
way, because you do want to ensure that everyone has finished boarding
before the boat starts moving.
Also note that if you have people board right away, and not wait on
the bank in this manner, the bit I posted yesterday about only needing
to know the total number of missionaries to avoid getting stuck is no
longer true - you need to know the total number of cannibals as well,
for reasons that should hopefully be fairly clear.
--
- David A. Holland | VINO project home page:
dholland(a)eecs.harvard.edu |
http://www.eecs.harvard.edu/vino