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)
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
empty primitives are actually unneeded, and can be integrated into the
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)
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): 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))
[(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): 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