[Solved]: Algorithm – Wine Bottle Filling

• $f_i$: fill bottle $i$.
• $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 $0le tle 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 $ble 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 $0le tle K_2=5$, as the theorem above indicated we should. To show that this behavior happens for all integer capacities $K_1<K_2$ where $gcd(K_1, K_2) = 1$, consider the second component values at each stage modulo $K_2$: an $S$ sequence takes $(0,b)rightarrow(0, K_1-K_2+b)$ and $K_1-K_2+bequiv K_1+bpmod{K_2}$. Similarly, a $T$ sequence takes $(0, b)rightarrow(0, K_1+b)$, so any sequence of $S$-$T$ moves starting at $(0,0)$ will produce the target values $nK_1pmod{K_2}$, for $n=0, 1, 2, dotsc,K_2-1$. For our example, with $K_1=3,K_2=5$, we’ll have the sequence of target values $$ langle,0, 3, 6, 9, 12,rangle equivlangle,0, 3, 1, 4, 2,ranglepmod{5} $$ All that remains to establish our theorem is to show that the $K_2$ elements of the target sequence are distinct. Suppose that they weren’t, namely that there exist $n, m$ with $0le n < m < K_2$ such that $mK_1equiv nK_1pmod{K_2}$. Then we would have $(m-n)K_1equiv0pmod{K_2}$ which would mean that $K_2$ would have to divide $(m-n)K_1$. However, $K_1$ has no factors in common with $K_2$ since $gcd(K_1, K_2)=1$, so $K_2$ would have to divide $m-n$. However, $m-n<K_2$ and so the only possibility would be that $m-n=0$, i.e., $m=n$, contrary to our assumption. Thus, all the $K_2$ values in our target sequence are distinct, establishing our theorem. Notes

1. For completeness, we note that if $gcd(K_1,K_2)=g>1$ then you can make all and only those target amounts $ng$ where $0le nle 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$.
2. Instead of the $S$-$T$ sequences, these can also be used: $$begin{align} Q: &text{if }b < K_1, text{ perform }p_2,f_2,p_2,e_1\ R: &text{if }b ge K_1, text{ perform }p_2,e_1 end{align}$$
3. 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.
4. To generate all the possible target values by this method will take $O(K_2)$ time.
5. 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”.