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.

Lets try solving it

Before calculating  steps, lets check what can we say if its possible or not given the values of a, b and c.
Its not possible if c > a and c > b, because then we are not having a vessel capable of holding c liters of water.
Its also not possible when c is not a multiple of hcf of a and b, because in that case we wont be able to make c liters ever.

Once its clear if its possible or not calculating minimum number of steps is easy.
If its possible then there are always 2 ways to do it, may be with different number of steps. What we do is, we recursively fill one bucket lets say a and empty it in b, and when b is full in between the process, we empty it, and again pour from a, and do this till the time we have c liters of water in either a or b, or both depending upon condition c < capacity of that vessel.
Second way would be to begin with b first. We will fill vessel b first , and start emptying it in a, and in case a is full in between we will empty a , and again pour water from b into a.

Example

Lets say we have 3 liters vessel A and 5 liters vessel B and we want to store 4 liters water C

Checking if its possible or not:
we can easily see 4 < 5 and also 4 is multiple of 1 (HCF of 5 and 3)

Lets try and fill 4 liters of water

Way 1.
We will repeatedly fill A and pour it in B
A = 3 and B = 5
                   Vessel A            Vessel B         Steps
initially              0                  0               0
Fill A                 3                  0               1
Pour A in B            0                  3               2
Fill A again           3                  3               3
Pour A in B            1                  5               4
Empty B                1                  0               5
Pour A in B            0                  1               6
Fill A                 3                  1               7
Pour A in B            0                  4               8
So we have 4 liters in B by way 1 in 8 steps.

Way 2.
We will repeatedly fill B and pour it in A
A = 3 and B = 5
                   Vessel A            Vessel B         Steps
initially              0                  0               0
Fill B                 0                  5               1
Pour B in A            3                  2               2
Empty A                0                  2               3
Pour B in A            2                  0               4
Fill B                 2                  5               5
Pour B in A            3                  4               6
So we have 4 liters in B by way 2 in 6 steps.

Here’s the piece of C++ code for checking and calculating the number of steps required.


/*
checking if its possible to fill C liters of water
in either of two vessels of capacity a and b with
infinite supply of water.
*/
bool check(int a,int b,int c){
    //boundary cases
    if(c>a && c>b)){
        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
    return false;
}

/*
calculating steps
Method:  Start filling A and pouring it in B,
in case B is full in between empty it, and
again pour from A, and repeat the process.
*/
int steps(int A,int B,int C){
    int steps = 0;
    int capacityA = A;
	int capacityB = B;
	int temp;
	//starting with empty buckets
    A= 0;
    B= 0;
    //repeating till either one of A and B has C liters of water
    while(A!=C && B!= C){
        //if A is empty, Fill A by supply of water
        if(A==0){
            A = capacityA;
            steps+=1;
        }else if(B==capacityB){
            //If B is full, in between the processempty it

            B=0;
            steps+=1;
        }else{
            /*
            Else, pour from A to B
            amount of water to be poured depends on how much B can hold
            which would be volume left in B or capacity of A, whichever is less
            */
            temp = min(capacityB-B,A);
            B+=temp;
            A-=temp;
            steps+=1;
        }

    }
    return  steps;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s