Solution to the Water Jug problem in C++

water_jug.cpp

/**
 * Based on the paper "A Heuristic for Solving the Generalized Water Jug Problem 
 * Florin Leon, Mihai Zaharia, Dan Galea
 */

#include <iostream>

using namespace std;

class Jug{
  int capacity;
	int value;
public:
	Jug(int n)
	{
		capacity = n;
		value = 0;
	}

	void Fill()
	{
		value = capacity;
	}

	void Empty()
	{
		value = 0;
	}

	bool isFull()
	{
		return value >= capacity;
	}

	bool isEmpty()
	{
		return value == 0;
	}

	//A[B] -> Transfer contents of B to A until A is full
	void operator[](Jug &B)
	{
		int old_value = value;

		value = value + B.value;
		value = value > capacity?capacity:value;

		B.value = B.value - (value - old_value);
	}

	int getValue()
	{
		return value;
	}
};


int gcd(int n,int m)
{ 
	if(m<=n && n%m == 0)
		return m;
	if(n < m)
		return gcd(m,n);
	else
		return gcd(m,n%m);
}

bool check(int a,int b,int c){
    //boundary cases
	if(c>a){
		cout<<"A can't hold more water than it's capacity!\n";
        return false;
    }
    //if c is multiple of HCF of a and b, then possible
    if(c % gcd(a,b) == 0){
        return true;
    }
    //if c is not multiple of HCF of a and b, then not possible
	cout<<"Can't reach this state with the given jugs\n";
    return false;
}

void solve(Jug A, Jug B, int result)
{
	while(A.getValue() != result)
	{
		if(!A.isFull() && B.isEmpty()){
			cout<<"Fill B\n";
			B.Fill();
			cout << "(A, B) = (" << A.getValue() << ", " << B.getValue() << ")\n";
		}
		if(A.isFull()){
			cout<<"Empty A\n";
			A.Empty();
			cout << "(A, B) = (" << A.getValue() << ", " << B.getValue() << ")\n";
		}
		cout<<"Pour from B into A\n";
		A[B];
		cout << "(A, B) = (" << A.getValue() << ", " << B.getValue() << ")\n";
	}
}

int main()
{
	int a, b, result;

	cout<<"Enter capacity of A\n";
	cin >> a;
	cout<<"Enter capacity of B\n";
	cin >> b;

	do{
	cout<<"Enter required water in A:\n";
	cin >> result;
	}
	while(!check(a,b,result));

	Jug A(a), B(b);
	
	cout << "\n(A, B) = (" << A.getValue() << ", " << B.getValue() << ")\n";
	solve(A, B, result);
	cout<<"Done!"<<endl;

	#ifdef _WIN32
	system("pause");
	#endif

	return 0;
}

//Water Jug Problem
#include
#include
#include<math.h>
using namespace std;

int xcapacity;
int ycapacity;

void display(int a, int b, int s);
int min(int d, int f){
if(d<f)
return d;
else
return f;
}

int steps(int n){
int x=0, y=0, step=0;
int temp;
cout<<setw(60)<<"Vessel A \tVessel B \tSteps:"<<endl;
while(x!=n){
if(x==0){
x=xcapacity;
step+=1;
cout<<"Fill x";
display(x,y,step);
}
else if(y==ycapacity){
y=0;
step++;
cout<<"Empty Y:";
display(x,y,step);
}
else{
temp= min(ycapacity-y,x);
y=y+temp;
x=x-temp;
step++;
cout<<"Pour X in Y";
display(x,y,step);
}
}
return step;
}
void display(int a, int b, int s){
cout<<setw(16)<<a<<setw(15)<<b<<setw(15)<<s<<endl;
}

int main(){
int n,ans;
cout<<"Enter the liters(GOAL) of water required to be filled in Vessel 1:";
cin>>n;
cout<<"Enter the capacity of the vessel:";
cin>>xcapacity;
cout<<"Enter the capacity of the second vessel:";
cin>>ycapacity;
ans=steps(n);
cout<<"Steps Required:"<<ans<<endl;
return 0;

}