Thread: cannibals and missionaries

  1. #1
    Registered User
    Join Date
    May 2007
    Posts
    6

    cannibals and missionaries

    Can anybody help me with the following problem:

    Write a C program for the missionaries and cannibals problem.
    The rules are(for those who haven't played the game):
    # There are three missionaries and three cannibals on the left bank of a river.
    # They wish to cross over to the right bank using a boat that can only carry two at a time.
    # The number of cannibals on either bank must never exceed the number of missionaries on the same bank, otherwise the missionaries will become the cannibals' dinner!

    I'd be highly grateful if anybody can help me with this.

  2. #2
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    What have you got so far ?

  3. #3
    Registered User
    Join Date
    May 2007
    Posts
    6
    to be honest i've just started working on it. have around a week to work on it.
    the main problem is that i just started programming n i'm still working to get used to it.

  4. #4
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    well, we're not going to give you the answer right away (if at all). Try to solve the problem on paper, write down how you solved it and then translate the solution into code.

  5. #5
    Registered User
    Join Date
    May 2007
    Posts
    6
    I understand that. Honestly, I'm not asking you for answer which i can just copy.
    I also want to learn. I solved the problem on paper, have the algorithm but the thing is I'm very new with programming so I just have a faint idea of converting it into codes.
    I started like 2 weeks ago only.

  6. #6
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    The way you learn is to write programs yourself very often. The more you do that, the faster you learn. In this day and age, you can learn the syntax of various programmings languages right from the internet for free. It's very easy to pick that up, but what can't really be taught is experience.

  7. #7
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    Here are a few guidelines:

    - You somehow need to store where the cannibals/missionaries are (on what bank). Of course you could have 6 different variables but a slightly better approach would be to have 2 arrays, one for each bank (or one for the missionaries and one for the cannibals). The data structure could look like this:

    Code:
    #define CANNIBALS 3
    #define MISSIONARIES 3
    
    #define CANNIBAL 1
    #define MISSIONARY 2
    
    char leftRiverBank[CANNIBALS + MISSIONARIES] = {0};
    char rightRiverBank[CANNIBALS + MISSIONARIES] = {0};
    
    /* put x missionaries on the left river bank */
    int i;
    for (i = 0; i < MISSIONARIES; i++)
    {
      leftRiverBank[i] = MISSIONARY;
    }
    
    /* put y cannibals on the right river bank */
    for (i = 0; i < CANNIBALS i++)
    {
      rightRiverBank[i] = CANNIBAL
    }
    You also need several utility functions, like a function that checks if there is a missionary/cannibal on a side of the river or a function that moves them across with the boat etc.

  8. #8
    Its hard... But im here swgh's Avatar
    Join Date
    Apr 2005
    Location
    England
    Posts
    1,688
    Why is that proffessors give newbies to a language some challenging assignments when they have just began the language syntax? Have they not heard from start from the basics and work upwards?

    When I was at college learning basic C, my first assignment was to input 10 numbers and print back the highest, lowest, product and average. Simple and straightforward. Then they became progressivly more challenging as I learned new features. Has the learnng systen changed dramaticky?
    Double Helix STL

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    You have your algorithm?

    Then write it down in pseudo code, and arrange it into the logical functions for your program.

    I'm thinking functions like "cannibal_aboard(), padre_aboard(), x_river(int direction), might be useful. int's like ls_cannibals, rs_cannibals, ls_padres, rs_padres, might be handy variables.

    Maybe we should make the left and right side padre's a float type, just in case the cannibals have eaten part of them, huh? <just kidding>

    If you've spent 2 weeks on this, and have no code yet, I'd say get busy working on this! Show us what you've got. Work from your algorithm, into pseudo code, and then "flesh it out" into code. Put off the details, for now. Work with the logic, and the flow of execution.

    I've never programmed this puzzle, but have solved it with paper/pencil. Great assignment!
    Last edited by Adak; 05-31-2007 at 02:31 AM.

  10. #10
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    Quote Originally Posted by swgh View Post
    Has the learnng systen changed dramaticky?
    Perhaps. It wouldn't surprise me that there are bad professors, since we definitely know they exist.

    At the same time, there's the other side of things. Students can very well be the problem: "Huh, we talked about it? We didn't see this when I didn't attend class for the last two weeks, or when I skipped the first three assignments."

    So, could be more than one reason for this.

  11. #11
    Registered User
    Join Date
    May 2007
    Posts
    6
    Thanks koni and all you guys. I have started working on the problem.
    I'll get back to you guys when I get stuck again(which i surely will pretty soon), till then please feel free to write your opinions and suggestions.

  12. #12
    Registered User
    Join Date
    May 2007
    Posts
    6
    Thanks ADAk...
    I havent been working on this problem for two weeks... I have started learning C language 2 weeks ago.
    Thanks for the suggestions, i'll need to decode them to understand myself first:P

  13. #13
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Perhaps the intent of the exercise is to try every possible combination of movements, and report those which succeed in getting everyone across within the rules.

    In essence, try a move, check the rules, repeat until someone gets eaten or everyone is across.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  14. #14
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    News to me, but it seems there are two sets of rules for this puzzle.

    The harder of the two is that when the boat's passenger(s), reaches either side of the river, the passenger(s) DO count toward the tally of missionaries and cannibals on that side of the river.

    The easier one is that the boat's passengers who never sets foot on the shore, don't count toward the tally of the shore's missionaries or cannibals, unless they get out of the boat. So a person could stay in the boat, and cross back over the river, and never be included in the tally until /unless he got out of the boat on a shore.

    I'll bet the professor wants the harder one to be solved, of course.

    Salem's suggestion is great, but I believe that's far beyond a 2 week old beginner's class in C! So it seems like some hints may be forthcoming in this thread.

    Like although you need to take a cannibal on the first X of the river, the halfway point will have all 3 missionaries across the river, and all the cannibals back on the original side. THEN the cannibals transport themselves across the river.

    Edit: correction - for the harder problem, two cannibals X the river first, in my solution. All the missionaries will be across the river before all the cannibals make it, but it's not halfway through the X's. That will be the 7th crossing out of 11 needed, before all the missionaries get crossed.
    Last edited by Adak; 05-31-2007 at 04:40 PM.

  15. #15
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    The Harder problem you suggest is not possible, someone is going to get ate, so he probably meant the easier.

Popular pages Recent additions subscribe to a feed