Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# Cross the River: Cannibals and Missionaries

Mark Herschberg
Sheriff
Posts: 6037
This question is easy to moderate. I somtimes ask it as an interview question.
3 missionaries and 3 cannibals are are one bank of a river and all need to cross it. There is a single boat which can old two people. The piranhas in the river have ruled out swimming for these wandering souls.
The catch (there's always a catch), is that if the cannibals ever outnumber the rather tasty missionaries on a particular bank, the outnumbered missionary(ies) will find themselves transfered up to the celestial branch office. How do you get all of them across (intact)?
--Mark

Greg Harris
Ranch Hand
Posts: 1012
there is a game website with this particular problem in flash... i cannot remember the name, though. it also has the knight's tour and a couple other cool thought provoking games (one with elevators). i would love to see that site again if anyone knows what i am talking about.
the way their game works is that someone has to drive the boat, so there always has to be at least 1 cannibal or 1 missionary in the boat. as an added bonus, if you get to shore and the total number of cannibals (on shore and in boat) out-number the missionaries, then you lose.
i will give someone else a try since i have seen this before.

HS Thomas
Ranch Hand
Posts: 3404
1 cannibal, 1 missionary cross
missionary returns
1 cannibal 1 missionary cross
cannibal returns
2 missionaries cross
cannibal returns
2 cannibals cross
1 cannibal returns
2 cannibal cross

Lets see if this adds up : x=cannibal; 0=missionary

Oh no , loose on the second crossing. Don't cannibals have a code of honor to maintain.Add an extra clause that that it is a race with a bonus at the end of it , so there's no time to be wasted eating fat missionary.
regards
[ August 17, 2003: Message edited by: HS Thomas ]

HS Thomas
Ranch Hand
Posts: 3404
1 cannibal, 1 missionary cross
missionary returns
2 cannibals cross
cannibal returns
2 missionaries cross
cannibal returns
2 missionaries cross
1 cannibal returns
2 cannibal cross
This might work !
No it doesn't. This is hard.
[ August 17, 2003: Message edited by: HS Thomas ]

HS Thomas
Ranch Hand
Posts: 3404

x
U
[ August 17, 2003: Message edited by: HS Thomas ]

Mark Herschberg
Sheriff
Posts: 6037
That is correct. Now some of the top candidates will note the following:
Originally posted by HS Thomas:

Now in this case, you made use of the asymmetry in the problem. But what can you can do is solve just have the problem (up to where I put the break). Then you note that the next step flips the state and you can simply reverse/reflect the steps to solve the second half.

--Mark

HS Thomas
Ranch Hand
Posts: 3404
Bravo!
Note the attempt to furtively cook a cannibal should the mission to keep cannibal numbers less than missionary numbers fail ?
x <------------- cannibal
U <------------- blackened pot
^v^ <------------- fire
That's clever , Mark. I didn't realise that flipping the numbers would get there faster.
Now I can see the skewed mirror image in my example.
Is there a theory to explain that problem solving strategy ?
regards
[ August 17, 2003: Message edited by: HS Thomas ]

Ranch Hand
Posts: 33
Originally posted by Greg Harris:
there is a game website with this particular problem in flash... i cannot remember the name, though. it also has the knight's tour and a couple other cool thought provoking games (one with elevators). i would love to see that site again if anyone knows what i am talking about.

It's Plastelina Games.
That elevator puzzle is really cool.

Greg Harris
Ranch Hand
Posts: 1012
thanks, rafael! i have missed those games.
WOW... they have added a lot since i was there last.
[ August 18, 2003: Message edited by: Greg Harris ]