2
\$\begingroup\$

Missionaries and cannibals problem is a well known Toy Problem to learn basic AI techniques.

I implemented it using iterative deepening depth-first search algorithm. My state is represented by a 3-element vector <A,B,C> where A represents the side of the boat (0/1), B and C represents the number of cannibals and missionary on the left hand side of the bank.

#include <bits/stdc++.h>

using namespace std;
/*
SOLUTION TO 3 CANNIBAL and 3 MISSIONARIES PROBLEM 
USING ITERATIVE DEEPENING DEPTH FIRST SEARCH
https://en.wikipedia.org/wiki/Missionaries_and_cannibals_problem
*/

//state initial state (0,3,3) Side Of the Boat 0->Right/1 /Cannibal/Missionary on right hand side 
vector < pair < int, pair<int,int> > > newStatesSet(pair< int, pair < int, int > > state){
  //generating all possible states from a given initial state
  vector < pair< int, pair< int, int> > > newStatesSet;
  int C = state.second.first, M = state.second.second;

  if(state.first==0){
    if(C>=1)
      newStatesSet.push_back(make_pair(1, make_pair( C-1 ,M  )));
    if(M>=1)
      newStatesSet.push_back(make_pair(1, make_pair( C   ,M-1)));
    if(C >= 2)
      newStatesSet.push_back(make_pair(1, make_pair( C-2, M   )));
    if(C >= 1 && M >=1 )
      newStatesSet.push_back(make_pair(1, make_pair( C-1, M-1 )));
    if(M >= 2)
      newStatesSet.push_back(make_pair(1, make_pair( C  , M-2 )));
  }
  else{
    C = 3- C;
    M = 3- M;

    if(C >= 1)
      newStatesSet.push_back(make_pair(0, make_pair(3- C+ 1 ,3- M  )));
    if(M >= 1)
      newStatesSet.push_back(make_pair(0, make_pair(3- C   ,3- M+ 1)));
    if(C >= 2)
      newStatesSet.push_back(make_pair(0, make_pair(3- C+ 2, 3- M   )));
    if(C >= 1 && M >=1 )
      newStatesSet.push_back(make_pair(0, make_pair(3- C+ 1, 3- M+ 1 )));
    if(M >= 2)
      newStatesSet.push_back(make_pair(0, make_pair(3- C  , 3- M+ 2)));
  }
  return newStatesSet;
}

bool validState(pair<int, pair<int, int> > state){
  int C = state.second.first, M = state.second.second;
  if(C > M && M!=0)
    return false;
  C = 3- C, M = 3- M;
  if(C > M && M!=0)
    return false;
  return true;
}

//source node , goal node , depth , answer if found is stored here
bool  depthLimitedSearch(pair<int, pair<int, int> > source, pair<int, pair<int, int> > goal, int depth, vector<pair<int, pair<int,int> > > &ans){

  if(source==goal)
    return true;

  if(depth<=0)
    return false;

  vector <pair<int, pair<int,int> > > leafs = newStatesSet(source);
  for(int i=0; i<leafs.size(); i++)
    if(validState(leafs[i])){
      if(depthLimitedSearch(leafs[i], goal, depth-1, ans)){
        ans.push_back(leafs[i]);
        return true;
      }
    }
}

string form(int stateNos,string character){
  string rep="";
  for(int i=1; i<=3; i++)
    if(stateNos>=i)
      rep.append(character);
    else
      rep.append(" ");
  return rep;
}

void displayState(pair<int, pair<int, int> > state){
  string rep = "";
  rep.append(form(state.second.first,"C"));
  rep.append(form(state.second.second,"M"));
  for(int i=1; i<=6; i++){
    if(state.first==0 && i==2)
      rep.append("B");
    else
    if(state.first==1 && i==5)
      rep.append("B");
    else
      rep.append(" ");
  }
  rep.append(form(3-state.second.first,"C"));
  rep.append(form(3-state.second.second,"M"));
  cout<<rep<<endl;
}

void iterativeDeepeningSearch(pair<int, pair<int, int> > source, pair<int, pair<int, int> > goal){

  vector< pair<int , pair<int, int> > > ans;
  for(int i=1 ; i <= 25 ;i++){
    vector<pair<int, pair<int, int> > >vec;
    depthLimitedSearch(source,goal,i,vec);
    if(vec.size()>0){
      ans=vec;
      break;
    }
  }
  cout<<"C and M represents cannibals and Missionaries \n respectively and B represents the location of boat\n";
  displayState(source);
  for(int i=ans.size()-1; i>=0; i--)
    displayState(ans[i]);
}

int main()
{ 
  pair<int, pair<int, int> > source = make_pair(0,make_pair(3, 3 ));
  pair<int, pair<int, int> > goal   = make_pair(1,make_pair(0, 0 ));
  iterativeDeepeningSearch(source,goal);
}

The code can also be found here.

It produces the following output:

CCCMMM B          
C  MMM    B CC    
CC MMM B    C     
   MMM    B CCC   
C  MMM B    CC    
C  M      B CC MM 
CC MM  B    C  M  
CC        B C  MMM
CCC    B       MMM
C         B CC MMM
CC     B    C  MMM
          B CCCMMM

What do you think is wrong with this code, and how can it be improved? What edge cases have I overlooked, if any? How can I make it less complicated?

\$\endgroup\$
2
  • \$\begingroup\$ Is this not a bad state? C M B CC MM Seems lime the M on the left back is being eaten. \$\endgroup\$ Sep 16, 2015 at 14:05
  • \$\begingroup\$ No, If the number of C's and M's are equal on any side then it is considered a good state. Ie Nos(C)== Nos(M) is a good state. \$\endgroup\$ Sep 16, 2015 at 14:24

1 Answer 1

2
\$\begingroup\$

First and foremost, do not use namespace::std. Please google for it, you will find a lot of answers.


Please include all the necessary headers. A first glance tells me that the following is missing:

#include <string> // std::string
#include <utility> // std::pair
#include <vector> // std::vector

Why are you using pair>? Have a look at tuples: http://www.cplusplus.com/reference/tuple/tuple/

std::tuple<bool, size_t, size_t>

Have a look at your function arguments and declare those const who are not modified. Also you are always passing a copy rather a reference so you should either be dooing one of the following.

foo(const type &bar)
foo(type &bar)

Try to add a space between control flow instructions like for, while and friends. Therewith you can readily differentiate them from functions.


Depending on the C++ version you are using you want to consider using range based loops for C++11 and higher. Then a loop like this one:

vector <pair<int, pair<int,int> > > leafs = newStatesSet(source);
for(int i=0; i<leafs.size(); i++)
    if(validState(leafs[i])) {
        if(depthLimitedSearch(leafs[i], goal, depth-1, ans)){
            ans.push_back(leafs[i]);
            return true;
        }
    }
}

becomes this

std::vector<std::tuple<bool, size_t, size_t> > leafs = newStatesSet(source);
for (auto &leaf : leafs)
    if (validState(leaf)) {
        if (depthLimitedSearch(leaf, goal, depth-1, ans)){
            ans.push_back(leaf);
            return true;
        }
    }
}

If you need the index often or reverse loops, then use iterators

for (int i=ans.size()-1; i>=0; i--)
    displayState(ans[i]);

then becomes

for (auto it=ans.rbegin(); it != ans.rend(); ++it) 
    displayState(*it);

More a personal thing than anything else but still. Your if ladders are really confusing. Whenever i see stuff like

if (C >= 1)
    // Stuff C==1
if (C >= 2)
    // Stuff C>=1

I cringe inwardly. In that setting it is really easy to miss the first clause for C >= 2. So why not do

if (C == 1)
    // Stuff C==1
else if (C >= 2)
    // Stuff C==1
    // Stuff C>=1

I know it is repetitive, but at least the control flow is really clear.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.