# Water pouring

## How to solve the water pouring puzzle programmatically.¶

Given two jugs of capcity of 3 and 5 liters, acquire exactly 4 liters in a jug. Assume an unlimited water supply, and that jugs can only be filled or emptied, i.e., no estimations.

First to model the data: a mapping of jug sizes to their current quantity. There are 3 primitive operations:

- filling a jug to capacity
- emptying a jug entirely
- pouring from a source jug to a destination jug, until either the source is emptied or the destination is full

```
class Jugs(dict):
def fill(self, size):
self[size] = size
def empty(self, size):
self[size] = 0
def pour(self, src, dest):
total = self[src] + self[dest]
self[src] = max(total - dest, 0)
self[dest] = min(total, dest)
```

That's sufficient to solve the puzzle through sheer brute force: scanning every possible combination breadth-first. Note the below implementations don't terminate unless a solution is found.

```
import itertools
from functools import partial
sizes = 3, 5
operations = list(itertools.chain(
(partial(Jugs.fill, size=size) for size in sizes),
(partial(Jugs.empty, size=size) for size in sizes),
(partial(Jugs.pour, src=src, dest=dest)
for src, dest in itertools.permutations(sizes, 2)),
))
def search(target):
for n in itertools.count(1):
for ops in itertools.product(operations, repeat=n):
jugs = Jugs.fromkeys(sizes, 0)
states = [op(jugs) or tuple(jugs.values()) for op in ops]
if any(target in state for state in states):
return states
%time search(4)
```

Now to relentlessly simplify the code. The first observation is that an empty source is useless, as is a full destination. So the `fill`

and `empty`

primitives are actually unneeded, and can be integrated into the `pour`

method.

```
def pour(jugs, src, dest):
if not jugs[src]:
jugs[src] = src
if jugs[dest] >= dest:
jugs[dest] = 0
total = jugs[src] + jugs[dest]
jugs[src] = max(total - dest, 0)
jugs[dest] = min(total, dest)
operations = [partial(pour, src=src, dest=dest)
for src, dest in itertools.permutations(sizes, 2)]
%time search(4)
```

That reduced the search space considerably, but moreover has revealed another simplification: it's pointless to "undo" a pour. Whether the source was emptied or the destination was filled, whatever reversing the previous pour direction would accomplish could have been done in the first place.

If there were more than 2 jugs, then there could be complex workflows. But with only 2, the first choice in pour directions determines the rest. There are only 2 *potential* solutions to the puzzle.

```
def search(target, src, dest):
jugs = dict.fromkeys((src, dest), 0)
while True:
pour(jugs, src, dest)
yield tuple(jugs.values())
if target in jugs.values():
return
list(search(4, 5, 3))
```

```
list(search(4, 3, 5))
```

And both of them are valid solutions. The solution to the puzzle is quite simply: keep pouring. It doesn't even matter which to start with.

But it can be further simplified. Now it's clear that the `jug`

data structure is only providing modular arithmetic.

```
def search(target, src, dest):
for n in itertools.count(1):
quot, rem = divmod(n * src - target, dest)
if not rem:
return n, -quot
search(4, 5, 3)
```

```
search(4, 3, 5)
```

```
assert (5 * 2) - (3 * 2) == (3 * 3) - (5 * 1) == 4
```

The puzzle is looking for integer solutions to $$ \ 3x + 5y = 4 $$ Which is known as a linear Diophantine equation, and must have a solution because $4$ is a multiple of $gcd(3, 5)$.