puzzle contents
Contents
raw puzzle
raw / puzzle misc

Solution to the Water Jug Problem

Robert Eisele

Sometimes you need exactly a specific amount of sugar, sand, water - whatever - but the only measuring tools you have are two containers of different known sizes. Since you have no scale, markings, or way to measure partial fills, the only operations that make sense are the ones that create known amounts: fill a container completely, empty it completely, or pour from one into the other until one is empty or the other is full. That setup is known as the Water Jug Problem (also the Two Jugs / Measuring Problem) and it’s widely remembered from Die Hard with a Vengeance.

Problem statement

You have two containers (“jugs”) with fixed capacities:

At any moment, the system state is the pair \((x,y)\) where:

You are allowed the following operations (each counts as one operation):

  1. Fill a jug to capacity \[ (x,y)\to(A,y),\quad (x,y)\to(x,B) \]

  2. Empty a jug \[ (x,y)\to(0,y),\quad (x,y)\to(x,0) \]

  3. Pour from one jug into the other until either the source becomes empty or the target becomes full

    Pour A → B: \[ \Delta = \min(x, B-y),\quad (x,y)\to(x-\Delta,y+\Delta) \] Pour B → A: \[ \Delta = \min(y,A-x),\quad (x,y)\to(x+\Delta,y-\Delta) \]

Goal

Given a target \(T \in \mathbb{N}\), find a sequence of allowed operations that reaches a state where one jug contains exactly \(T\): \[ x=T \quad\text{or}\quad y=T \] Additionally, we want the sequence with the minimum number of operations.

Feasibility

The only moments where an amount becomes known are the hard boundaries: 0, A, B, and whatever you get by filling one jug until the other is empty or full. That means every “interesting” number the system can ever talk about is produced by repeatedly taking differences and sums of the capacities and previously produced amounts. So it’s natural to look at the integer combinations of the two capacities:

\[ G := \{\, mA+nB \mid m,n\in\mathbb Z \,\}. \]

Think of \(G\) as the set of all “net effects” you can build from the only two absolute reference quantities in the problem: a full \(A\)-jug and a full \(B\)-jug. If the process has a modular restriction at all, it must show up here.

Now look at the positive numbers inside \(G\). There is a smallest one (well-ordering of \(\mathbb N\)):

\[ d := \min(G \cap \mathbb N). \]

By definition of \(G\), \(d\) can be written as \[ d = uA+vB \] for some integers \(u,v\).

The crucial point is what this smallest positive element does to everything else in \(G\). Take any \(g\in G\) and divide by \(d\): \[ g = qd + r,\qquad 0 \le r < d. \] Because \(g\in G\) and \(qd\in G\) (closure under addition), the remainder \[ r = g-qd \] is also in \(G\). But \(r\) is a nonnegative integer smaller than \(d\). Since \(d\) was chosen as the smallest positive integer in \(G\), the only possibility is \(r=0\). Therefore, \[ d \mid g\quad\text{for every }g\in G. \] So \(d\) is a “step size”: every integer combination \(mA+nB\) lands on the lattice \(d\mathbb Z\).

In particular, \(A\in G\) and \(B\in G\), hence \(d\mid A\) and \(d\mid B\). So \(d\) is a common divisor of \(A\) and \(B\). And if \(c\) is any common divisor of \(A\) and \(B\), then \(c\) divides every \(mA+nB\), hence divides \(d\). That makes \(d\) the greatest common divisor:

\[ d = \gcd(A,B). \]

Now connect this back to the jug moves. Start at \((0,0)\), so both contents are multiples of \(d\). Filling sets a jug to \(A\) or \(B\), again multiples of \(d\). Emptying gives \(0\). Pouring transfers \[ \Delta=\min(x,\;B-y)\quad\text{or}\quad \Delta=\min(y,\;A-x), \] and if \(x\) and \(y\) are multiples of \(d\), then \(B-y\) and \(A-x\) are also multiples of \(d\), so \(\Delta\) is a multiple of \(d\) as well. Subtracting \(\Delta\) from one jug and adding it to the other cannot leave the lattice of multiples of \(d\).

So the process never escapes \(d\mathbb Z\): every amount you can end up with in either jug must be a multiple of \(d=\gcd(A,B)\). Consequently, reaching a target \(T\) in a jug forces the divisibility condition:

\[ \gcd(A,B)\mid T. \]

Finally, if the goal is to have exactly \(T\) in a single jug, then \(T\) must fit into at least one of the jugs, which is equivalent to \[ T \le \max(A,B). \]

Minimum-operations algorithm from first principles

State-space graph

The system has finitely many states: \[ (x,y)\ \text{with}\ x\in{0,\dots,A},\ y\in{0,\dots,B} \] so \((A+1)(B+1)\) states.

Each allowed operation takes one state to another state. Think of this as a directed graph:

The problem becomes:

Find the shortest path from \((0,0)\) to any goal state \((T,y)\) or \((x,T)\).

BFS gives the minimum number of operations

Because every edge has equal cost (1), this is a shortest path problem in an unweighted graph. Breadth-First Search (BFS) explores states in increasing distance from the start:

Therefore, the first time BFS encounters a goal state, it must be at the smallest possible distance - i.e. the solution has the minimum number of operations.

Complexity

JavaScript implementation

The implementation below:

function gcd(a, b) {
  a = Math.abs(a); b = Math.abs(b);
  while (b !== 0) [a, b] = [b, a % b];
  return a;
}

function stateKey(x, y) {
  return `${x},${y}`;
}

function neighbors(x, y, A, B) {
  const res = [];

  // Fill
  if (x !== A) res.push({ x: A, y, op: "fill A" });
  if (y !== B) res.push({ x, y: B, op: "fill B" });

  // Empty
  if (x !== 0) res.push({ x: 0, y, op: "empty A" });
  if (y !== 0) res.push({ x, y: 0, op: "empty B" });

  // Pour A -> B
  if (x !== 0 && y !== B) {
    const d = Math.min(x, B - y);
    res.push({ x: x - d, y: y + d, op: "pour A -> B" });
  }

  // Pour B -> A
  if (y !== 0 && x !== A) {
    const d = Math.min(y, A - x);
    res.push({ x: x + d, y: y - d, op: "pour B -> A" });
  }

  return res;
}

/**
 * Finds a MINIMUM-operation sequence to measure exactly T in either jug.
 *
 * Returns:
 *   null if impossible
 *   else {
 *     goal: { x, y },
 *     steps: Array<{ op, from:{x,y}, to:{x,y} }>
 *   }
 */
function minOpsMeasure(A, B, T) {

  if (A <= 0 || B <= 0 || T < 0) {
    throw new Error("Require A>0, B>0, T>=0.");
  }

  if (T === 0) return { goal: { x: 0, y: 0 }, steps: [] };

  // Feasibility
  if (T > Math.max(A, B)) return null;
  if (T % gcd(A, B) !== 0) return null;

  // BFS
  const start = { x: 0, y: 0 };
  const startK = stateKey(0, 0);

  const queue = [start];
  let qi = 0;

  const visited = new Set([startK]);

  // parent map: key -> { prevKey, op, from, to }
  const parent = new Map();

  while (qi < queue.length) {
    const { x, y } = queue[qi++];

    // Goal check
    if (x === T || y === T) {
      const goalK = stateKey(x, y);
      const steps = [];
      let k = goalK;

      // Reconstruct path backwards
      while (k !== startK) {
        const rec = parent.get(k);
        steps.push({ op: rec.op, from: rec.from, to: rec.to });
        k = rec.prevKey;
      }
      steps.reverse();

      return { goal: { x, y }, steps };
    }

    // Expand neighbors
    for (const nb of neighbors(x, y, A, B)) {
      const k = stateKey(nb.x, nb.y);
      if (visited.has(k)) continue;

      visited.add(k);
      parent.set(k, {
        prevKey: stateKey(x, y),
        op: nb.op,
        from: { x, y },
        to: { x: nb.x, y: nb.y }
      });

      queue.push({ x: nb.x, y: nb.y });
    }
  }
}

As an example with the original Die Hard numbers then looks like

const result = minOpsMeasure(3, 5, 4);
if (!result) {
  console.log("Impossible");
} else {
  console.log("Goal state:", result.goal);
  console.log("Minimum steps:", result.steps.length);
  for (const s of result.steps) {
    console.log(`${s.op}: (${s.from.x},${s.from.y}) -> (${s.to.x},${s.to.y})`);
  }
}
All Puzzles