WaTER JuGgggggg ProBlem

After a long time i am writing post in my blog. Hereafter i am planning to  post one algorithm on each day. It will be useful to me and peoples who are reading my blog also. I will try guys. I am not sure. Today i am discussing abt most famous puzzle (water jug problem.)
Question:

Given two vessels, one of which can accommodate a liters of water and the other which can accommodate b liters of water, determine the number of steps required to obtain exactly c liters of water in one of the vessels. You have infinite supply of water.

At the beginning both vessels are empty. The following operations are counted as ‘steps’:

• emptying a vessel,
• filling a vessel,
• pouring water from one vessel to the other, without spilling, until one of the vessels is either full or empty.

For example , you have 3 litres of water jug and 5 litres capacity of water jug, users wants 4 litres in any of jugs means , how you will get it. Here the following processes will help u to get 4 litres.

assume A-5, B-3
                          A              B
fill ()                  5               0
transfer()            2               3
empty()              2               0
transfer()            0               2
fill()                   5               2
transfer()            4               1
 
wow. finally u got 4 litres in one jug. I hope u understand the above processes. Next we will discuss how to write programs for getting no. of steps to reach final output.

Assume A-5, B-3, C-4

if(A>C)  we can get  C litres of water in A
if(B>C) we can get C litres of water in B
if both (A and B > C) we can get C litres of water in A or B

Algorithm is ,

if A>C & B<C)  transfer A->B until you get C litres of water in A
and viceversa.
in last case. if both are bigger than C means, transfer from A->B or B->A.

in first case (A>C), first fill 5 to A, and transfer to B upto it reaches the capacity and

return the transferred to A and reduces the current amount in A .

Now I hope you understand the logic.

Now we will write program for this.

Program:

#include<iostream>
#include"Jug.h"
using namespace std;
int main()
{
 Jug j1(3,0),j2(5,0);

 int no=4;
 int count;
 count=j2.make(no,j1); // do comparisons which objects passes , other object as argument. i am very lazy doing like these things.

 if(!count)
  cout<<"failed to make"<<endl;
 else
  cout << "no. of steps : " << count << endl;

}

program2: jug.cpp

#include "Jug.h"
#include<iostream>
using namespace std;
int count=0;
Jug::Jug(int c,int curr)
{
 this->Capacity=c;
 this->Current=curr;
}

Jug::~Jug(void)
{
}
int Jug::make(int no,Jug &V2)
{

 if(CheckGCD(Capacity,V2.Capacity)!=1 || Capacity< no)  // we have to check if gcd is exist or not.
 {
  cout<< "Solution not exist" << endl;
 
  return 0;
 }
 while(Current!=no)  // until u get the 4
 {
  ++count;
 
  if(!Current)
  {
   Current=Capacity;   // if empty means fill the jug with full capacity
 
   cout<<"fill() of high quantity vessel"<<endl;
  }
 
  cout<<"current: "<<Current<<endl;
    
  cout<<"transfer()"<<endl;
  Current=Current-V2.transfer(Current);// transfer the amount of water in Jug 1
 
  if(!Current)
 
   cout<<"empty() of high quantity vessel"<<endl;
  if(V2.Current==V2.Capacity)
    {
     V2.empty();
    
     cout<< "empty() of less quantity vessel" <<endl;
    }
 }
 cout<<"current"<<Current<<endl;
 return count;
}

int Jug::transfer(int amount)
{
 int transferred=0;
 if(Current+ amount > Capacity )
 {
  transferred=Capacity-Current;
 
  Current=Capacity;
  cout<<"fill() of less quantity vessel" << endl;
 
  return transferred;
 }
 else

 {
  Current=Current+ amount;

  cout<<"fill() of less quantity vessel" << endl;
  return amount;
 }

}
void Jug::empty()
{
 Current=0;
}
int CheckGCD(int a,int b)
{
 return b? CheckGCD(b, a % b) : a;
}

Jug.h contains declarations for all the functions.

int CheckGCD(int, int);
class Jug
{
 int Capacity,amount,Current;
public:
 Jug(int , int);
 ~Jug(void);
 void empty();
 int transfer(int );
 int make(int , Jug &);

};

reply if any test cases are wrong in this program.


References:

                  http://amrendra.in/2012/09/13/water-jug-problem/