• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Cross the River: Cannibals and Missionaries

 
Mark Herschberg
Sheriff
Posts: 6037
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

x
U
[ August 17, 2003: Message edited by: HS Thomas ]
 
Mark Herschberg
Sheriff
Posts: 6037
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 ]
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic