Breadth-First Search heuristics to find solution to Water Jug Challenge

Question

I started learning AI recently. In AI, searches should be avoided and everything in AI is a search problem.

One of the easiest problem where we could use general AI search techniques is the water jug problem which states:

You are given two jugs, a 4-gallon one and a 3-gallon one. Neither has any measuring markers on it. There is a tap that can be used to fill the jugs with water. How can you get exactly 2 gallons of water into the 4-gallon jug?

I solved it using the BFS technique:

#include <bits/stdc++.h>

using namespace std;

vector <pair<int,int> > newStatesSet(pair<int,int> state){
  //generating all possible states from a given initial state
  vector<pair<int,int> > newStates;
  if(state.first==0 && state.second==0){
    newStates.push_back(make_pair(3,0));
    newStates.push_back(make_pair(0,4));
    newStates.push_back(make_pair(3,4));
  }
  if(state.first!=0 && state.second==0){
    newStates.push_back(make_pair(state.first,4));
    newStates.push_back(make_pair(0,state.first));
    if(state.first<3){
      newStates.push_back(make_pair(3,0));
      newStates.push_back(make_pair(3,4));
    }
  }
  if(state.first==0 && state.second!=0){
    int transferQuantity;
    if(state.second>3)
      transferQuantity=3;
    else
      transferQuantity=state.second;
    newStates.push_back(make_pair(transferQuantity,state.second-transferQuantity));
    newStates.push_back(make_pair(3,state.second));
  }
  if(state.first!=0 && state.second!=0){
    newStates.push_back(make_pair(0,state.second));
    newStates.push_back(make_pair(state.first,0));
    if(state.second<4){
      int transferQuantity1=state.second+state.first;
      int transferQuantity2;
      if(transferQuantity1>4){
        transferQuantity2=transferQuantity1-4;
        transferQuantity1=4;
      }
      else
        transferQuantity2=0;
      newStates.push_back(make_pair(transferQuantity2,transferQuantity1));
    }
    if(state.first<3){
      int transferQuantity1=state.second+state.first;
      int transferQuantity2;
      if(transferQuantity1>3){
        transferQuantity2=transferQuantity1-3;
        transferQuantity1=3;
      }
      else
        transferQuantity2=0;
      newStates.push_back(make_pair(transferQuantity1,transferQuantity2));
    }
  }
  return newStates;
}

bool checkGoal(pair<int,int> x,int sum){
  if(x.second==sum)
    return true;
  return false;
}

void reverseTraversal(map <pair<int,int>,pair<int,int> > parent,pair<int,int> initialState,pair<int,int> goalState){
  if(initialState != goalState){
    reverseTraversal(parent,parent[initialState],goalState);
  }
  cout<<"("<<initialState.first<<","<<initialState.second<<")"<<endl;
}

int main()
{
  //capacity (3,4)  
  //open list
  queue <pair<int,int> > Q;
  pair <int,int> parNode;
  //contains all the states
  map < pair<int,int> ,int > occured;
  //contains parent
  map < pair<int,int>,pair<int,int> > parent;

  Q.push(make_pair(0,0));
  while(Q.empty()!=true){
    parNode=Q.front();
    Q.pop();
    if(checkGoal(parNode,2))
      break;
    occured[parNode]++;
    vector <pair<int,int> > leafs = newStatesSet(parNode);
    for(int i=0;i<leafs.size();i++){
      if(occured[leafs[i]]==0){
        Q.push(leafs[i]);
        parent[leafs[i]]=parNode;
      }
    }
  }
  reverseTraversal(parent,parNode,make_pair(0,0));
}

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

---

Improvements based on suggestion can be found here

Answer 1

I think that the function that computes new states could be simplified in this way:

vector <pair<int,int> > newStatesSet(pair<int,int> state){
  //generating all possible states from a given initial state
  vector<pair<int,int> > newStates;

  if (state.first < 3) {
    newStates.push_back(make_pair(3, state.second));
  }
  if (state.second < 4) {
    newStates.push_back(make_pair(state.first, 4));
  }
  if (state.first > 0) {
    newStates.push_back(make_pair(0, state.second));
  }
  if (state.second > 0) {
    newStates.push_back(make_pair(state.first, 0));
  }
  if (state.second > 0 && state.first < 3) {
    newStates.push_back(make_pair(std::min(3, state.first + state.second),
                        std::max(state.second - (3 - state.first), 0)));
  }
  if (state.first > 0 && state.second < 4) {
    newStates.push_back(make_pair(std::max(state.first - (4 - state.second), 0),
                        std::min(4, state.second + state.first)));
  }

  return newStates;
}

Note that with this function a new state is generated from the previous state by considering a single operation. So, for instance, from the state (0, 0) it produces (3, 0) and (0, 4), but not (3, 4) (which will be generated later) as in your function. I think that this reflect more correctly the idea that each state is derived from the previous one with a single step.

Answer 2

I have not checked your code for correct output, just for coding-related issues. Here are some comments.

Avoid using std

• Nix using namespace std. Read up on the rationale here.

Pre-allocate vector size when you know roughly how large it will be

• Rather than rushing a number of push_back operations when you know how many, or roughly how many, you will need, preallocate the vector first. In newStatesSet you know the size you will make vector newStates so you should call reserve after the declaration and before you start your push_backs. Otherwise the vector likely has to relocate after the first 2 pushes (std::vector tends to double each time memory must be reallocated, so you'll usually go from 2 to 4 to 8 and so on....)

Brevity

• You can shorten checkGoal like so:

  bool checkGoal(pair<int,int> x,int sum){ return (x.second==sum); }

  Also consider restructuring the arguments to take x.second directly as an int value parameter rather than unnecessarily passing the whole pair. Both these adjustments should improve performance as well as code readability.

Avoid side effects

• reverseTraversal is a void that makes some changes to state and also prints something out. You generally want to do one or the other in a function. It's best not to have print statements scattered throughout functions.

---

Additional Possible improvements:

Reference to const can be better than passing by value

• Since you don't seem to manipulate your input parameter in newStatesSet, you should consider passing it by reference to const rather than by value. I may be wrong that this would improve performance since a pair of ints shouldn't be that large, but you can benchmark to confirm.

Try making local copies of oft-used class members

• Looking at newStatesSet, I think you might consider making a local variable copy of state.first and state.second since you access them often. Whether this improves performance is compiler dependent.