[Solved]: Algorithm - Wine Bottle Filling

Problem Detail: 

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?

Asked By : Teodorico Levoff

Answered By : Rick Decker

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<K_2$, respectively, and denote by $(a_1, a_2)$ the current amounts in the bottles. You have six basic operations you can perform, for $i=1, 2$:

• $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 $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_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+b\equiv K_1+b\pmod{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_1\pmod{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 \equiv\langle\,0, 3, 1, 4, 2\,\rangle\pmod{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 $0\le n < m < K_2$ such that $mK_1\equiv nK_1\pmod{K_2}$. Then we would have $(m-n)K_1\equiv0\pmod{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 $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$.
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".

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40890