Water Jug Problem in Python

Water Jug Problem in Python

The Problem:

You have 2 water jugs of varying capacity A and B. You can fill a jug, empty a jug, or transfer the contents to the other.  When you transfer from A -> B all the content of A will be poured into B up to the capacity of B leaving A with the remainder.  For example, If A  contains 3 litres of water and B can hold only 2 litres then A will have 1 litre left after the transfer.

The goal is to transfer, fill and empty the jugs until you arrive at a target volume in a single jug.

The Algorithm

Give Jug 1, j1 has a volume of 3 litres and Jug 2, j2 has a volume of 5 litres. The target volume t1 is 1 litre.

The problem is valid if t1 < j1 or t1 < j2 and if t1 is divisible by the greatest common denominator of j1 and j2.

We'll calculate GCD using the euclidian method.  We subtract the smaller capacity from the larger recurrsively until they are equal. That final value is our GCD. For example using the values state above would produce the follow:

[3, 5] -> [3, 2] -> [1, 2] -> [1, 1]

Our GCD is 1.

def getGCD(a, b):
    larger = max(a, b)
    smaller = min(a, b)
    if larger != smaller:
        smaller = getGCD(larger - smaller, smaller)
    return smaller

Next we verify that the problem is has a solution. To do this we check if the target value is a multiple of the GCD.

In our example the target value of 1 is obviously okay.  Here's an example that doesn't work.

j1 = 16
j2 = 18

gcd = getGCD(16, 18) # 2

target = 9 # not divisible by 2

Now, assuming we've got valid starting values for our jugs and target we can move on to the solution.  

I break this down into 3 basic moves.

  1. if the smaller jug is empty, fill it.
  2. if the larger jug is full, empty it.
  3. Otherwise transfer the contents of the smaller jug to the larger.

We repeat these steps until the volume of one of the jugs is equal to our target.  Assuming we've validated our initial values it will work.

In the code example below I additionally count steps and show the number of  fill and dump actions taken.  I represent them as an array with 2 values, the number of times the small jug was filled and the number of times the large jug was emptied.  The filling increments the value by 1, emptying decrements the value by 1.

Using our example values of 3 and 5 litres we would arrive at an action count of [2, -1].  That means we filled the 3 litre jug twice and emptied the 5 litre once.  Fun fact,  this can be a math equation.

2(3 liters) + -1(5 litres) = 1 litre

At the end of the code you can use this to verify your answer.

Try it out

You can try it out and modify it here