Algorithm - Wine Bottle Filling

You have two friends, call them A and B. They each are given two wine bottles: one bottle holds k_1 litres and the other k_2 litres. Both A and B can perform these operations:

• completely fill a wine bottle with wine
• completely empty a wine bottle
• pour the wine of one bottle into the other bottle, making sure to stop only when either the bottle being filled is full or if when the bottle being emptied is completely empty. Assume the litres of wine are all positive ints.

Q: Determine if there exist a seq of operations that leaves exactly k_3 litres of wine in the bigger wine bottle. Try representing this as a graph problem.

My idea: define the vertices to be a pair of integers in a graph. I got this as a recent interview question. But couldn't solve the entire problem in time. Then they said you could have apparently applied some algo to this problem too, and that it had a complexity that was fast enough. Any ideas?

Here's an efficient method that doesn't involve constructing a graph of the states and searching for a path to each target value. Let the capacities of the bottles be integers $K_1

• $e_i$: empty bottle $i$.

• $p_i$: pour as much of bottle $i$ as will fit into bottle $3-i$.

We'll show this


Theorem. If $\gcd(K_1, K_2) = 1$ (i.e., $K_1$ and $K_2$ have no factors in common), then you can start in state $(0,0)$ and end in state $(0, t)$ for any target integer $0\le t\le K_2$.

Consider these two sequences of basic moves, starting in state $(0, b)$:

• Sequence $S$: if $b>K_2-K_1$, perform $f_1, p_1, e_2, p_1$.

• Sequence $T$: if $b\le K_2-K_1$, perform $f_1, p_1$.

The result of $S$ will be
$$
(0, b)\stackrel{f_1}{\rightarrow}(K_1,b)\stackrel{p_1}{\rightarrow}(K_1-(K_2-b),K_2)\stackrel{e_2}{\rightarrow}(K_1-K_2+b,0)\stackrel{p_1}{\rightarrow}(0,K_1-K_2+b)
$$
and the result of $T$ will be
$$
(0, b)\stackrel{f_1}{\rightarrow}(K_1,b)\stackrel{p_1}{\rightarrow}(0, K_1+b)
$$
It's not difficult to establish that if $b>K_2-K_1$, the $S$ sequence will satisfy that the first component of each state will be less than or equal to $K_1$ and the second will be less than or equal to $K_2$ at each step and we can show similarly that the basic moves in the $T$ sequence are likewise always legal at each step.

For example, with $K_1=3, K_2=5$ we will have the following sequence of states:
$$
(0,0)\stackrel{T}{\rightarrow}(0,3)\stackrel{S}{\rightarrow}(0,1)\stackrel{T}{\rightarrow}(0,4)\stackrel{S}{\rightarrow}(0,2)
$$
so the sequence $T,S,T,S$ will generate the target values $0, 3, 1, 4, 2$, and of course we can always generate $K_2$ by a single $f_2$ move. Notice that we have generated all the target values $0\le t\le K_2=5$, as the theorem above indicated we should.

To show that this behavior happens for all integer capacities $K_11$ then you can make all and only those target amounts $ng$ where $0\le n\le K_2/g$, since we can reduce this case to one with capacities $K_1'=K_1/g,K_2'=K_2/g$ and observe that $\gcd(K_1',K_2')=1$.

• Instead of the $S$-$T$ sequences, these can also be used:

$$\begin{align}
Q: &\text{if }b

• The $S$-$T$ sequences might not produce a given target in the fewest number of moves. It may be the case that the $Q$-$R$ sequences will get to a given target value faster and vice-versa. It's possible, using the extended Euclidean algorithm, to determine which sequence choice will reach a particular target value quicker.

• To generate all the possible target values by this method will take $O(K_2)$ time.

• If you only want an answer to the interviewer's question, "is there a sequence of operations that leaves an amount $k_3$ in the larger bottle?" here's an algorithm that runs in time $O(\log K_2)$: if $k_3 > K_2$ answer "no", otherwise compute $g=\gcd(K_1, K_2)$ (which you can do in time $O(\log K_2)$) and if $g$ divides $k_3$, answer "yes", else answer "no".

StackExchange Computer Science Q#40890, answer score: 5