This week's book giveaway is in the Servlets forum.
We're giving away four copies of Murach's Java Servlets and JSP and have Joel Murach on-line!
See this thread for details.
The moose likes Programming Diversions and the fly likes Cross the River: Cannibals and Missionaries Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Cross the River: Cannibals and Missionaries" Watch "Cross the River: Cannibals and Missionaries" New topic
Author

Cross the River: Cannibals and Missionaries

Mark Herschberg
Sheriff

Joined: Dec 04, 2000
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

Joined: Apr 12, 2001
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.


what?
HS Thomas
Ranch Hand

Joined: May 15, 2002
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

Joined: May 15, 2002
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

Joined: May 15, 2002
Posts: 3404

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

Joined: Dec 04, 2000
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

Joined: May 15, 2002
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 ]
Rafael Prado
Ranch Hand

Joined: May 17, 2003
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

Joined: Apr 12, 2001
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 ]
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Cross the River: Cannibals and Missionaries
 
Similar Threads
[very easy]transport the animals
cross the river
what's the factory?
can anyone please briefly teach me how to write a classic game?
how to write the game-CrossingRiver (2)