Water Jug / Die Hard

Problem. Two jugs of capacities $a$ and $b$ litres, unlimited water, no markings. Allowed moves: fill a jug, empty a jug, pour one into the other until the source is empty or the target is full. Can you measure exactly $c$ litres?

The answer

Possible iff $\gcd (a,b)\mid c$ and $c\le \max (a,b)$.

Every reachable amount is an integer combination $xa+yb$, hence a multiple of $g=\gcd (a,b)$ (Bézout). Conversely, repeatedly filling $a$ and pouring into $b$ (emptying $b$ when full) realises every multiple of $g$ up to $\max (a,b)$.

The famous Die Hard instance: $a=3$, $b=5$, $c=4$. Since $\gcd (3,5)=1\mid 4$, it is solvable.

The constructive strategy

Two symmetric strategies; take the shorter:

Pour $a\to b$: fill $a$; pour into $b$; whenever $b$ is full, empty it; repeat until some jug holds $c$.
Pour $b\to a$: the mirror image.

int pourSteps(int from, int to, int target) {   // simulate, counting moves
    int x = from, y = 0, steps = 1;             // fill 'from'
    while (x != target && y != target) {
        int t = min(x, to - y);
        x -= t; y += t; steps++;                // pour
        if (x == target || y == target) break;
        if (x == 0) { x = from; steps++; }      // refill
        if (y == to) { y = 0;   steps++; }      // empty
    }
    return steps;
}
int minSteps(int a, int b, int c) {
    if (c > max(a,b) || c % __gcd(a,b)) return -1;
    return min(pourSteps(a, b, c), pourSteps(b, a, c));
}

$O(a+b)$ — each state $(x,y)$ recurs after at most $a+b$ pours.

BFS on the state space

For three or more jugs, or unusual move sets, model it as a graph and search:

// state = (x, y); moves: fill x, fill y, empty x, empty y, pour x->y, pour y->x
queue<pair<int,int>> q;
map<pair<int,int>, int> dist;

$O(ab)$ states, 6 moves each. This is the general answer and extends to any number of jugs — see implicit graphs.

The lesson: implicit-graph BFS

The water jug problem is the archetype of a large family:

Problem	State	Moves
Water jugs	$(x,y)$ litres	fill, empty, pour
15-puzzle	board configuration	slide a tile
Wolf, goat, cabbage	who is on which bank	cross with $\le 1$ item
Missionaries and cannibals	counts on each bank	cross with 1-2 people
Rubik’s cube	cube state	face turn
Word ladder	a word	change one letter
Coin/token puzzles	positions	legal move
Lock combinations	current code	rotate a dial

Whenever a puzzle asks for the minimum number of operations, it is a BFS on an implicit graph — and the only real work is defining the state and the neighbour function.

For very large state spaces, bidirectional BFS halves the exponent.

Variants

Variant	Note
Minimum number of pours	BFS, or compare the two strategies
Three or more jugs	BFS; the gcd condition generalises to $\gcd$ of all capacities
Jugs with markings	more moves; still BFS
Infinite supply vs a fixed total	changes the reachable set
Measure $c$ in a specific jug	restrict the goal test
Minimise the water used	Dijkstra with pour amounts as weights

Why the gcd appears

The reachable amounts are exactly $\{xa+yb:x,y\in \mathbb{Z}\}\cap [0,\max (a,b)]$, and Bézout’s identity says that set is the multiples of $\gcd (a,b)$. It is the same fact that governs linear Diophantine equations and the Frobenius coin problem — a single number-theoretic statement answering three superficially unrelated puzzles.

See also: BFS · Linear Diophantine Equations · Euclidean Algorithm