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 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)

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)

(2, -2)

search(4, 3, 5)

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