Water buckets and infinite tap water

[Link to code, you can try it in the end of the post]

Suppose you have an infinite source of water and two buckets of capacities $5$L and $3$L. Through juggling around the water in the buckets, can you find a way to have one of the buckets hold exactly $1$L of water?

A possible way of doing it would be:

1. Fill the bucket of $3$L and then pour its water into the $5$L one;
2. Fill the bucket of $3$L. At this point you have $3$L in each bucket;
3. Pour the bucket of $3$L into the $5$L one. Since the bigger one already had $3$L in it, only $2$ will fit, meaning there will be a remaining litre in the $3$L bucket.

I find this problem a very interesting one, and it is not hard to generalize it: given $N$ buckets of capacities $c_1, c_2, \cdots, c_N$, as well as a target value $T$ and an infinite source of water, is there a sequence of moves that puts exactly $T$ litres in one of the buckets?

There are some cases for which one can immediately say that there is no such sequence. On one hand, if $T > c_i\ \forall i\leq N$, it is obvious we cannot do so; on the other hand, if such a sequence exists, then $d = \gcd{(c_1,\cdots, c_N)} | T$, i.e., if $T$ is not a multiple of the greatest common divisor $d$ of all the capacities, then the answer is no.

I don't find it obvious that $T$ being a multiple of $d$ is sufficient to prove the existence of a solving sequence, even though we can find integer coefficients $a_i$ such that $a_1c_1 + \cdots + a_Nc_N = T$ (which would hint on the sequence to be used) it feels like we could not be able to juggle the water in the buckets to hold the intermediate steps needed to get to the final solution.

Even so, it was with astounding ease that I created a script to solve this problem, presenting the sequence of moves when there is a solving sequence and indicating that there is no such sequence when there is no solution. By "astounding ease" I mean that I was expecting it to be fairly difficult, but turned out not to be that complicated. I challenge you to try it for yourself.

Say we have $N$ ordered buckets. We can represent how much each bucket is filled by a tuple $(w_1, \cdots, w_N)$. We can now think of all the tuples of length $N$ that could represent a plausible state; that is, we can think of $V = \{(w_1,\cdots, w_N) \in \mathbb{N}_0^N | w_i\leq c_i  \}$ as the set of vertices of a directed graph $G$, and then have an edge from $a = (a_1, \cdots, a_N)$ to $b = (b_1, \cdots, b_N)$ if we can get from the state $a$ to the state $b$ by either completely filling one of the buckets with the water source, by pouring one bucket $i$ into bucket $j$, or by emptying one of the buckets.

If we think of our original problem in these terms, our original question becomes:

Is there a path in $G$ from $(0, \cdots, 0)$ to a vertex having at least one coordinate with value $T$?

Answering this question is rather easy and can be done by resorting to the well-known breadth-first search (BFS) algorithm. A good thing about this particular application of the algorithm is that we can build the graph just as we need it, potentially reducing memory usage and increasing the speed of the algorithm a bit. The code is here on GitHub and can be tried online in repl.it. Alternatively you can try it in the widget below, but I believe it will be fairly slower than running the script directly in repl.it or on your machine. In the end of the script you have two variables, $T$ and $buckets$ that can be changed to change the problem configuration. $T$ is the target value and $buckets$ is a list of capacities.


 [Pt] Existe uma charada bastante comum com jarros de água com capacidades diferentes: se eu tiver um jarro com $5$L, outro jarro com $3$L e uma torneira (que deita água), será que consigo medir exatamente $1$L de água? A resposta é sim:

1. Encho o jarro de $3$L e despejo no de $5$L;
2. Volto a encher o jarro de $3$L. Agora cada jarro tem $3$L;
3. Despejo o jarro pequeno no jarro grande. O jarro grande já tinha $3$L lá, portanto só cabem mais $2$L, e portanto sobra $1$L no jarro pequeno, que era o que queríamos.  

Generalizar este problema, para o caso em que temos $N$ jarros com capacidades $(c_1, \cdots, c_N)$ e em que queremos medir $T$ litros, é bastante fácil!

É óbvio que se a quantidade que queremos medir for maior que a capacidade de qualquer jarro, então não há solução. Por outro lado, temos que só pode haver solução se $T$ for múltiplo do máximo divisor comum das capacidades $c_1, \cdots, c_N$.

Escrever um script que resolva o problema na sua forma geral revelou-se bastante mais simples do que eu estava à espera, bastou ver o problema de outra maneira: em cada momento, a quantidade de água nos jarros pode ser vista como um tuplo $(w_1, \cdots, w_N)$. Se pensarmos dessa maneira, podemos construir um grafo dirigido $G$ com vértices $V = \{(w_1,\cdots, w_N) \in \mathbb{N}_0^N | w_i\leq c_i  \}$ e há uma aresta do vértice $a = (a_1, \cdots, a_N)$ para o vértice $b = (b_1, \cdots, b_N)$ se eu consigo ir do estado $a$ para o $b$ esvaziando ou enchendo completamente um dos jarros, ou despejando a água de um jarro $i$ para um jarro $j$.

Vendo o problema desta forma, a pergunta original torna-se

Será que existe um caminho no grafo $G$ que comece em $(0, \cdots, 0)$ e termine num vértice em que alguma coordenada tem o valor $T$?

 Para responder a esta questão criei o script que pode ser encontrado aqui no GitHub. Alternativamente, podem experimentar correr o script no widget que se encontra no início da secção em português, embora eu recomende que o façam diretamente no link para o repl.it. Para resolver o problema, implementei o algoritmo de procura em largura (BFS) e vou construindo apenas as partes do grafo de que vou precisando. No fim do script há duas variáveis, $T$ e $buckets$ que contêm respetivamente o valor alvo e as capacidades dos baldes. Estas variáveis podem ser alteradas para resolver problemas com outras configurações.

Let me know what you think!

-RGS