Top Puzzle 8: The Two Jugs Problem | Puzzles for Interview - Interview Preparation PDF Download

Introduction

The Two Water Jug Puzzle is a problem where you are given two jugs of different volumes and you need to measure a specific amount of water using them. The jugs don't have markings to allow measuring smaller quantities, so you need to use your skills to solve the problem. In this article, we will discuss an arithmetic approach to solving this problem.

Modeling the Problem

The problem can be modeled by means of the Diophantine equation of the form mx + ny = d which is solvable if and only if gcd(m, n) divides d. The solution x, y for which equation is satisfied can be given using the Extended Euclid algorithm for GCD.

Example

Let's consider an example where we have a jug J1 of 5 liters (n = 5) and another jug J2 of 3 liters (m = 3) and we have to measure 1 liter 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. 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.

Solutions

To find the minimum number 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 liter jug into n liter jug):
1. Fill the m-liter jug and empty it into the n-liter jug.
2. Whenever the m-liter jug becomes empty fill it.
3. Whenever the n-liter jug becomes full empty it.
4. Repeat steps 1,2,3 until either the n-liter jug or the m-liter jug contains d liters 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 number of operations.

Solution 2 (Always pour from n liter jug into m liter jug):
1. Fill the n-liter jug and empty it into the m-liter jug.
2. Whenever the n-liter jug becomes empty fill it.
3. Whenever the m-liter jug becomes full empty it.
4. Repeat steps 1, 2 and 3 until either the n-liter jug or the m-liter jug contains d liters of water.
Let us say solution 2 achieves the task in C2 number of operations. Now our final solution will be a minimum of C1 and C2.

Illustration

Suppose there are a 3-liter jug and a 5-liter jug to measure 4 liters of water so m = 3, n = 5, and d = 4. The associated Diophantine equation will be 3m + 5n = 4. We use pair (x, y) to represent amounts of water inside the 3-liter jug and 5-liter 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 number 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 number of operations you need to perform are 6.

Conclusion

Therefore, we would use solution 2 to measure 4 liters of water in 6 operations or moves. There are several ways of solving this problem including BFS and DP, but an arithmetic approach is a simple and effective way to solve the problem.