• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Liutauras Vilda
  • Campbell Ritchie
  • Tim Cooke
  • Bear Bibeault
  • Devaka Cooray
Sheriffs:
  • Jeanne Boyarsky
  • Knute Snortum
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Ganesh Patekar
  • Stephan van Hulst
  • Pete Letkeman
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Ron McLeod
  • Vijitha Kumara

Cross the River: Cannibals and Missionaries  RSS feed

 
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
 
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.
 
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 ]
 
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 ]
 
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!