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:
- fill the first jug
- transfer from first jug to second jug
- if one of the jugs contains exactly $c$ units water: terminate, solution found, else continue with step 4.
- if the second jug is full: empty it and transfer from second to first jug
- 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?
Best Answer
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.