The Two Water Jug Puzzle

Related: Uva 571 Jugs ()
http://www.geeksforgeeks.org/two-water-jug-puzzle/

You are at the side of a river. You are given a m litre jug and a n litre jug where 0 < m < n. Both the jugs are initially empty. The jugs don’t have markings to allow measuring smaller quantities. You have to use the jugs to measure d litres of water where d < n. Determine the minimum no of operations to be performed to obtain d litres of water in one of jug.
The operations you can perform are:

1. Empty a Jug
2. Fill a Jug
3. Pour water from one jug to the other until one of the jugs is either empty or full.

There are several ways of solving this problem including BFS and DP. In this article an arithmetic approach to solve the problem is discussed. The problem can be modeled by means of Diophantine equation of the form mx + ny = d which is solvable if and only if gcd(m, n) divides d. Also, the solution x,y for which equation is satisfied can be given using the Extended Euclid algorithm for GCD.
For example, if we have a jug J1 of 5 litre (n = 5) and another jug J2 of 3 litre (m = 3) and we have to measure 1 litre of water using them. The associated equation will be 5n + 3m = 1. First of all this problem can be solved since gcd(3,5) = 1 which divides 1 (See this for detailed explanation). Using the Extended Euclid algorithm, we get values of n and m for which the equation is satisfied which are n = 2 and m = -3. These values of n, m also have some meaning like here n = 2 and m = -3 means that we have to fill J1 twice and empty J2 thrice.
Now to find the minimum no of operations to be performed we have to decide which jug should be filled first. Depending upon which jug is chosen to be filled and which to be emptied we have two different solutions and the minimum among them would be our answer.

Solution 1 (Always pour from m litre jug into n litre jug)

1. Fill the m litre jug and empty it into n litre jug.
2. Whenever the m litre jug becomes empty fill it.
3. Whenever the n litre jug becomes full empty it.
4. Repeat steps 1,2,3 till either n litre jug or the m litre jug contains d litres of water.

Each of steps 1, 2 and 3 are counted as one operation that we perform. Let us say algorithm 1 achieves the task in C1 no of operations.

Solution 2 (Always pour from n litre jug into m litre jug)

1. Fill the n litre jug and empty it into m litre jug.
2. Whenever the n litre jug becomes empty fill it.
3. Whenever the m litre jug becomes full empty it.
4. Repeat steps 1, 2 and 3 till either n litre jug or the m litre jug contains d litres of water.

Let us say solution 2 achieves the task in C2 no of operations.

Now our final solution will be minimum of C1 and C2.

Now we illustrate how both of the solutions work. Suppose there are a 3 litre jug and a 5 litre jug to measure 4 litres water so m = 3,n = 5 and d = 4. The associated Diophantine equation will be 3m + 5n = 4. We us pair (x, y) to represent amounts of water inside 3 litre jug and 5 litre jug respectively in each pouring step.

Using Solution 1, successive pouring steps are:

(0,0)->(3,0)->(0,3)->(3,3)->(1,5)->(1,0)->(0,1)->(3,1)->(0,4)

Hence the no of operations you need to perform are 8.

Using Solution 2, successive pouring steps are:

(0,0)->(0,5)->(3,2)->(0,2)->(2,0)->(2,5)->(3,4)

Hence the no of operations you need to perform are 6.

Therefore we would use solution 2 to measure 4 liters of water in 6 operations or moves.

int gcd(int a, int b)

{

    if (b==0)

       return a;

    return gcd(b, a%b);

}

 

/* fromCap -- Capacity of jug from which

              water is poured

   toCap   -- Capacity of jug to which

              water is poured

   d       -- Amount to be measured */

int pour(int fromCap, int toCap, int d)

{

    // Initialize current amount of water

    // in source and destination jugs

    int from = fromCap;

    int to = 0;

 

    // Initialize count of steps required

    int step = 1; // Needed to fill "from" Jug

 

    // Break the loop when either of the two

    // jugs has d litre water

    while (from != d && to != d)

    {

        // Find the maximum amount that can be

        // poured

        int temp = min(from, toCap - to);

 

        // Pour "temp" litres from "from" to "to"

        to   += temp;

        from -= temp;

 

        // Increment count of steps

        step++;

 

        if (from == d || to == d)

            break;

 

        // If first jug becomes empty, fill it

        if (from == 0)

        {

            from = fromCap;

            step++;

        }

 

        // If second jug becomes full, empty it

        if (to == toCap)

        {

            to = 0;

            step++;

        }

    }

    return step;

}

 

// Returns count of minimum steps needed to

// measure d litre

int minSteps(int m, int n, int d)

{

    // To make sure that m is smaller than n

    if (m > n)

        swap(m, n);

 

    // For d > n we cant measure the water

    // using the jugs

    if (d > n)

        return -1;

 

    // If gcd of n and m does not divide d

    // then solution is not possible

    if ((d % gcd(n,m)) != 0)

        return -1;

 

    // Return minimum two cases:

    // a) Water of n litre jug is poured into

    //    m litre jug

    // b) Vice versa of "a"

    return min(pour(n,m,d),   // n to m

               pour(m,n,d));  // m to n

}

http://www.geeksforgeeks.org/measure-1-litre-from-two-vessels-infinite-water-supply/

There are two vessels of capacities ‘a’ and ‘b’ respectively. We have infinite water supply. Give an efficient algorithm to make exactly 1 litre of water in one of the vessels. You can throw all the water from any vessel any point of time. Assume that ‘a’ and ‘b’ are Coprimes.

Following are the steps:
Let V1 be the vessel of capacity ‘a’ and V2 be the vessel of capacity ‘b’ and ‘a’ is smaller than ‘b’.
1) Do following while the amount of water in V1 is not 1.
….a) If V1 is empty, then completely fill V1
….b) Transfer water from V1 to V2. If V2 becomes full, then keep the remaining water in V1 and empty V2
2) V1 will have 1 litre after termination of loop in step 1. Return.

/* Sample run of the Algo for V1 with capacity 3 and V2 with capacity 7 1. Fill V1:                               V1 = 3, V2 = 0 2. Transfer from V1 to V2, and fill V1:   V1 = 3, V2 = 3 2. Transfer from V1 to V2, and fill V1:   V1 = 3, V2 = 6 3. Transfer from V1 to V2, and empty V2:  V1 = 2, V2 = 0 4. Transfer from V1 to V2, and fill V1:   V1 = 3, V2 = 2 5. Transfer from V1 to V2, and fill V1:   V1 = 3, V2 = 5 6. Transfer from V1 to V2, and empty V2:  V1 = 1, V2 = 0 7. Stop as V1 now contains 1 litre. Note that V2 was made empty in steps 3 and 6 because it became full */

To prove that the algorithm works, we need to proof that after certain number of iterations in the while loop, we will get 1 litre in V1.
Let ‘a’ be the capacity of vessel V1 and ‘b’ be the capacity of V2. Since we repeatedly transfer water from V1 to V2 until V2 becomes full, we will have ‘a – b (mod a)’ water in V1 when V2 becomes full first time . Once V2 becomes full, it is emptied. We will have ‘a – 2b (mod a)’ water in V1 when V2 is full second time. We repeat the above steps, and get ‘a – nb (mod a)’ water in V1 after the vessel V2 is filled and emptied ‘n’ times. We need to prove that the value of ‘a – nb (mod a)’ will be 1 for a finite integer ‘n’. To prove this, let us consider the following property of coprime numbers.
For any two coprime integers ‘a’ and ‘b’, the integer ‘b’ has a multiplicative inverse modulo ‘a’. In other words, there exists an integer ‘y’ such that ‘b*y ≡ 1(mod)a’ (See 3rd point here). After ‘(a – 1)*y’ iterations, we will have ‘a – [(a-1)*y*b (mod a)]’ water in V1, the value of this expression is ‘a – [(a – 1) * 1] mod a’ which is 1. So the algorithm converges and we get 1 litre in V1.

void Vessel:: makeOneLitre(Vessel &V2)

{

    // solution exists iff a and b are co-prime

    if (gcd(capacity, V2.capacity) != 1)

        return;

 

    while (current != 1)

    {

        // fill A (smaller vessel)

        if (current == 0)

            current = capacity;

 

        cout << "Vessel 1: " << current << "   Vessel 2: "

             << V2.current << endl;

 

        // Transfer water from V1 to V2 and reduce current of V1 by

        //  the amount equal to transferred water

        current = current - V2.transfer(current);

    }

 

    // Finally, there will be 1 litre in vessel 1

    cout << "Vessel 1: " << current << "   Vessel 2: "

         << V2.current << endl;

}

 

// Fills vessel with given amount and returns the amount of water

// transferred to it. If the vessel becomes full, then the vessel

// is made empty

int Vessel::transfer(int amount)

{

    // If the vessel can accommodate the given amount

    if (current + amount < capacity)

    {

        current += amount;

        return amount;

    }

 

    // If the vessel cannot accommodate the given amount, then

    // store the amount of water transferred

    int transferred = capacity - current;

 

    // Since the vessel becomes full, make the vessel

    // empty so that it can be filled again

    current = 0;

 

    return transferred;

}

https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

In modular arithmetic, the modular multiplicative inverse of an integer a modulo m is an integer x such that

The multiplicative inverse of a modulo m exists if and only if a and m are coprime (i.e., if gcd(a, m) = 1).^[1] If the modular multiplicative inverse of a modulo m exists, the operation of division by amodulo m can be defined as multiplying by the inverse of a, which is in essence the same concept as division in the field of reals.

Suppose we wish to find modular multiplicative inverse x of 3 modulo 11.

This is the same as finding x such that

Working in  we find one value of x that satisfies this congruence is 4 because

https://en.wikipedia.org/wiki/Coprime_integers

A number of conditions are individually equivalent to a and b being coprime:

• No prime number divides both a and b.
• There exist integers x and y such that ax + by = 1 (see Bézout's identity).
• The integer b has a multiplicative inverse modulo a: there exists an integer y such that by ≡ 1 (mod a). In other words, b is a unit in the ring Z/aZ of integers modulo a.
• Every pair of congruence relations for an unknown integer x, of the form x ≡ k (mod a) and x ≡ l (mod b), has a solution, as stated by the Chinese remainder theorem; in fact the solutions are described by a single congruence relation modulo ab.
• The least common multiple of a and b is equal to their product ab, i.e. LCM(a, b) = ab.