Jugs of Water Puzzle: Minimum Number of Operations

Question

PUZZLE. Given two water jugs with capacities $a, b \in \mathbb{N}$, the goal is to measure exactly $c$ units of water only performing the following operations:

• fill one of the jugs to it's capacity limit,
• empty one of the jugs,
• fill water from one jug to the other until the first jug is empty or the second jug is full.

This puzzle is well-known and the special case $a = 5, b = 3, c = 4$ was originally featured in the movie Die Hard 3: With a Vengeance. It can be easily solved by brute-force in a few steps.

We call a triplet $(a, b, c)$ an instance. A sequence of operations as described above is called a solution, if after performing all these operations in order one of the jugs contains exactly $c$ units water. If there is no solution requiring strictly fewer operations, a solution is called optimal.

Naturally, there are two questions in this puzzles context:

• Existence: Given an instance $(a, b, c)$, is it possible to measure exactly $c$ units of water using a sequence of the operations described above? [solved below]
• Optimality: Find an optimal solution. How?

Both problems can be solved algorithmically by BFS. There are at $a + 1$ possible amounts the first jug can contain and $b + 1$ amounts for the second jug. Hence, we have $(a + 1)(b + 1) \in \mathcal{O}(ab)$ possible states. When considering large capacities and instances with only quite long solutions, space and time complexity issues arise. Thus, I search for a more efficient approach.

It is clear that the amount of water in each jug is always an integer linear combination $s \cdot a + t \cdot b$ of the capacities $a$ and $b$. It can also be shown that every such integer linear combination can be reached (up to the exception of exceeding capacity limits, let's assume $c \le \max(a, b)$ and $a \le b$ wlog). By Bezout's Lemma, if every linear combination is reachable, we are able to measure $c$ units of water iff $gcd(a, b) \mid c$. To do so, we use the following algorithm:

1. fill the first jug
2. transfer from first jug to second jug
3. if one of the jugs contains exactly $c$ units water: terminate, solution found, else continue with step 4.
4. if the second jug is full: empty it and transfer from second to first jug
5. go to step 1

We execute this algorithm twice: In the first run, 'first jug' means the jug with capacity $a$. In the second run, 'first jug' means the jug with capacity $b$. After both runs, we take the solution requiring the minimum number of operations.

EXAMPLE. Let's work through the instance $(5, 3, 4)$ from the movie. The algorithm yields:

• 1st run: $(0, 0) \rightarrow_1 (5, 0) \rightarrow_2 (2, 3) \rightarrow_4 (2, 0) \rightarrow_4 (0, 2) \rightarrow_1 (5, 2) \rightarrow_2 (4, 3)$
• 2nd run: $(0, 0) \rightarrow_1 (0, 3) \rightarrow_2 (3, 0) \rightarrow_1 (3, 3) \rightarrow_2 (5, 1) \rightarrow_4 (0, 1) \rightarrow_4 (1, 0) \rightarrow_1 (1, 3) \rightarrow_2 (4, 0)$

Note that each pair $(p, q)$ means that the jug with capacity $a = 5$ contains $p$ units of water and jug with capacity $b = 3$ contains $q$ units. An arrow $\rightarrow_k$ denotes a transition (step $k$) as given by the algorithm.

QUESTION. Is this algorithm always optimal and why? (Proof)

Algorithmic approaches (I know, it may overlap with computer science) faster than BFS are also highly appreciated. May we use the Extended Euclidean algorithm in some way?

Answer 1

Yes, the algorithm is always optimal. The reason is that once you've decided which jug to fill first, there's nothing you can do that makes sense at any point other than what the algorithm says.

Suppose we have just poured from A to B. Then, because we stopped pouring, it must be the case that either A is empty or B is full. (Or both are true, in which case we have achieved nothing we couldn't do just by filling up B from the beginning).

• If A is empty, then pouring back from B to A immediately will just put us in the state we just came from. Either emptying or filling B will erase all of our hard work, so the only sane thing to do is to fill A from the tap, and then continue pouring from A to B.

• If B is full, then pouring back from B to A immediately would still be pointless (at least from the point of view of getting a shortest solution) because we could have done that instead of pouring from A to B in the first place. Either emptying or filling A would lose our work so far, so the only thing to do is to empty out B, and then continue pouring from A to B.

Thus, in an optimal sequence every pour goes in the same direction: either always from A to B or from B to A. You can compute how long it will take to reach $c$ in each case by using the extended Euclidean algorithm (as Joffan describes) rather than actually doing the simulation one pour at a time, though.

Answer 2

Essentially this is an exercise in modular arithmetic.

Each cycle of jug activity either adds or subtracts a certain amount from the larger jug, depending on which way around the cycle you are heading (which jug is being refilled and which discarded).

In order to find the number of operations, barring some details, you need to find the multiplicative inverse of $b \bmod a$ (I'm assuming that $a$ is the largest of the three numbers). The extended Euclidean algorithm will give you this, and also the feasibility of the triplet.

Suppose we have $(a,b,c) = (57,41, 20)$. Then the extended Euclidean algorithm gives:

\begin{array}{c|c} n & s & t & q \\ \hline 57 & 1 & 0 & \\ 41 & 0 & 1 & 1 \\ 16 & 1 & -1 & 2 \\ 9 & -2 & 3 & 1 \\ 7 & 3 & -4 & 1 \\ 2 & -5 & 7 & 3 \\ 1 & 18 & -25 & 2 \\ \end{array}

where each line gives an identity $n=57s+41t$, ending with Bezout's identity $18\cdot 57-25\cdot 41=1$

Edit insert: this is where we can check feasibility. If the Extended euclidean algorithm here ends with a GCD of $1$, there is no issue, but if $a$ and $b$ have a common factor then the problem is only solvable if $c$ is also divisible by that factor.

This means that $-25\cdot 41\equiv 1 \bmod 57$, so we have $-25$ as the mulitplicative inverse of $41\bmod 57$ and $41k\equiv 20\bmod 57$ can be solved with $k\equiv -25\cdot 20\equiv -50\cdot 10\equiv 7\cdot 10\equiv 70\equiv 13\bmod 57$.

So $-13\equiv 44\bmod 57$ is larger; therefore we want to go the additive way, refilling the small jug and pouring into the big jug, and that refill should happen $13$ times (if we start with both jugs empty): $\newcommand{pour}{\underset{\text{pour}}{\to}}$ $\newcommand{refill}{\underset{\text{refill}}{\to}}$ $\newcommand{empty}{\underset{\text{empty}}{\to}}$

$\begin{align}(0,0)&\refill(0,41)\pour(41,0)\refill(41,41)\pour(57,25)\empty(0,25)\\ &\pour(25,0)\refill(25,41)\pour(57,9)\empty(0,9)\pour(9,0)\\ &\refill(9,41)\pour(50,0)\refill(50,41)\pour(57,34)\empty(0,34)\\ &\pour(34,0)\refill(34,41)\pour(57,18)\empty(0,18)\pour(18,0)\\ &\refill(18,41)\pour(57,2)\empty(0,2)\pour(2,0)\refill(2,41)\\ &\pour(43,0)\refill(43,41)\pour(57,27)\empty(0,27)\pour(27,0)\\ &\refill(27,41)\pour(57,11)\empty(0,11)\pour(11,0)\refill(11,41)\\ &\pour(52,0)\refill(52,41)\pour(57,36)\empty(0,36)\pour(36,0)\\ &\refill(36,41)\pour(57,20)\\ \end{align}$

For every refill, of course we also get an initial pour, and then we may also get extra empty + pour operations if we go past a multiple of 57 poured. so $\lfloor(13\times 41)/57\rfloor = 9$ so we should have $13\times 2 + 9\times 2 = 44$ operations (which would end with correct amount in the big jug). Here we stopped short of the last two operations because we had the correct amount in the small jug already (which can be predicted since $20<41$), giving $42$ operations.