Two water jug problem in C++

In this tutorial, we will learn how to solve the two water jug problem in C++.

PROBLEM STATEMENT:

You are given two unmarked jugs with capacities x and y liters. Determine the moves to obtain exactly n liters of water in any of the two jugs or both by the end.
Given that:
1. There is infinite supply of water.
2. Both the jugs are empty at the beginning.
Operations allowed:
1. Empty /fill a jug completely with water.
2. Pour water from one jug to another until one of the jugs is either empty or full.

SOLUTION:

We will first see the steps to solve the given problem.

1. If it is possible to fill n liters of water using the two jugs with x and y liters.
   It is possible only if
   1. n<x or n<y
   2. n%gcd(x,y) is equal to zero.
2. Fill x completely.
3. Pour x in y.
4. Empty y if it is full.
5. Check if x is empty or not. If x is not empty, repeat step 3-5. If x is empty, repeat steps 2-5.
6. Stop the process when n litres of water is obtained in any of the two jugs or both.

Now, we will implement these steps using C++ code.

#include<bits/stdc++.h>
using namespace std;
int x;
int y;
void show(int a, int b);
int min(int w, int z)
{
if (w < z)
return w;
else
return z;
}
void show(int a, int b)
{
cout << setw(12) << a << setw(12) << b<<endl;
}
void s(int n)
{
int xq = 0, yq = 0;
int t;
cout << setw(15) <<"FIRST JUG"<< setw(15) <<"SECOND JUG"<<endl;
while (xq != n && yq!=n )
{
  if (xq == 0)
  {
    xq = x;
    show(xq, yq);
  }
  else if (yq == y)
  {
    yq = 0;
    show(xq, yq);
  }
  else
  {
    t = min(y - yq, xq);
    yq= yq + t;
    xq = xq - t;
    show(xq, yq);
      }
}
}
int main()
{
int n;
cout << "Enter the liters of water required out of the two jugs: ";
cin >> n;
cout << "Enter the capacity of the first jug: ";
cin >> x;
cout << "Enter the capacity of the second jug: ";
cin >> y;
if(n<x || n<y)
{ if(n%(__gcd(x,y))==0)
    s(n);
  else
  cout<<"This is not possible....\n";  
}
else
  cout<<"This is not possible....\n"; 
}

OUTPUT:

Enter the liters of water required out of the two jugs: 2

Enter the capacity of the first jug: 4

Enter the capacity of the second jug: 3

         FIRST JUG          SECOND JUG
             4                  0
             1                  3
             1                  0
             0                  1
             4                  1
             2                  3

So, we have solved the two water jug problem in C++. I hope you enjoyed it.

Also, read:

• Create all possible strings from a given set of characters in c++
• C++ program to create a text file, open and read a particular line