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

# 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

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
= 3, 5
sizes = list(itertools.chain(
operations =size) for size in sizes),
(partial(Jugs.fill, size=size) for size in sizes),
(partial(Jugs.empty, size=src, dest=dest)
(partial(Jugs.pour, srcfor 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.fromkeys(sizes, 0)
jugs = [op(jugs) or tuple(jugs.values()) for op in ops]
states if any(target in state for state in states):
return states
%time search(4)
```

```
CPU times: user 138 ms, sys: 2.28 ms, total: 140 ms
Wall time: 144 ms
```

`[(0, 5), (3, 2), (0, 2), (2, 0), (2, 5), (3, 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]:
= src
jugs[src] if jugs[dest] >= dest:
= 0
jugs[dest] = jugs[src] + jugs[dest]
total = max(total - dest, 0)
jugs[src] = min(total, dest)
jugs[dest]
= [partial(pour, src=src, dest=dest)
operations for src, dest in itertools.permutations(sizes, 2)]
%time search(4)
```

```
CPU times: user 87 µs, sys: 0 ns, total: 87 µs
Wall time: 88.7 µs
```

`[(3, 2), (2, 0), (3, 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):
= dict.fromkeys((src, dest), 0)
jugs while True:
pour(jugs, src, dest)yield tuple(jugs.values())
if target in jugs.values():
return
list(search(4, 5, 3))
```

`[(2, 3), (0, 2), (4, 3)]`

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

`[(0, 3), (1, 5), (0, 1), (0, 4)]`

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):
= divmod(n * src - target, dest)
quot, rem if not rem:
return n, -quot
4, 5, 3) search(
```

`(2, -2)`

`4, 3, 5) search(`

`(3, -1)`

`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)\).