Water Jug problem using BFS

The problem, simply

You have two jugs with no marks on them. One holds A cups, the other holds B cups. You may do three kinds of moves: fill a jug to the top from the tap, empty a jug onto the ground, or pour one jug into the other until the first is empty or the second is full.

Give back the fewest moves that leave exactly C cups in either jug, or -1 if it can never happen.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every sequence of moves, depth first, like a kid trying random buttons and backing up.

1. From the current pair, try all six moves.
2. Do not revisit a pair already on the current path, or you could loop forever.
3. When a jug holds C, keep the number of moves if it is the best so far.
4. Stop a path once it can no longer beat the best.

class JugsDFS {
    static int best;

    public static int minSteps(int capA, int capB, int target) {
        best = Integer.MAX_VALUE;
        go(0, 0, capA, capB, target, 0, new boolean[capA + 1][capB + 1]);
        return best == Integer.MAX_VALUE ? -1 : best;
    }

    static void go(int a, int b, int capA, int capB, int target, int steps, boolean[][] onPath) {
        if (a == target || b == target) { best = Math.min(best, steps); return; }
        if (steps + 1 >= best || onPath[a][b]) return;
        onPath[a][b] = true;
        int pourAB = Math.min(a, capB - b), pourBA = Math.min(b, capA - a);
        int[][] moves = {
            {capA, b}, {a, capB},                      // fill a jug
            {0, b}, {a, 0},                            // empty a jug
            {a - pourAB, b + pourAB},                  // pour A into B
            {a + pourBA, b - pourBA}                   // pour B into A
        };
        for (int[] m : moves) go(m[0], m[1], capA, capB, target, steps + 1, onPath);
        onPath[a][b] = false;                          // free this pair for other paths
    }
}

How long it takes: the path marks are removed when backing up, so the same pair is explored again and again along different paths. With up to (A + 1) * (B + 1) pairs and 6 moves each, the worst case is exponential, roughly O(6^(A * B)). Extra room: the marks and the recursion, O(A * B).

Way 2: the clever way

Use the ripples. Every move costs 1, so breadth first search over the pairs finds the fewest moves. Each pair is visited once, ever.

1. If C is 0, answer 0. If C is bigger than both jugs, answer -1.
2. Put (0, 0) in a waiting line (a queue) with 0 moves.
3. Take a pair from the front. Make all six moves. For each new pair you have not seen: write down its move count (one more), and if it holds C in either jug, that count is the answer. Otherwise add it to the line.
4. If the line empties, answer -1.

class JugsBFS {
    public static int minSteps(int capA, int capB, int target) {
        if (target == 0) return 0;
        if (target > Math.max(capA, capB)) return -1;  // no jug is big enough
        int[][] steps = new int[capA + 1][capB + 1];
        for (int[] row : steps) Arrays.fill(row, -1);
        steps[0][0] = 0;
        Queue<int[]> line = new ArrayDeque<>();
        line.add(new int[]{0, 0});
        while (!line.isEmpty()) {
            int[] s = line.poll();
            int a = s[0], b = s[1];
            int pourAB = Math.min(a, capB - b), pourBA = Math.min(b, capA - a);
            int[][] moves = {
                {capA, b}, {a, capB},                  // fill a jug
                {0, b}, {a, 0},                        // empty a jug
                {a - pourAB, b + pourAB},              // pour A into B until A is empty or B is full
                {a + pourBA, b - pourBA}               // pour B into A
            };
            for (int[] m : moves) {
                if (steps[m[0]][m[1]] != -1) continue; // seen this pair already
                steps[m[0]][m[1]] = steps[a][b] + 1;
                if (m[0] == target || m[1] == target) return steps[m[0]][m[1]];
                line.add(m);
            }
        }
        return -1;                                     // the ripples never reached C
    }
}

How long it takes: there are at most (A + 1) * (B + 1) pairs, each handled once with 6 moves, O(A * B). Extra room: the step table and the line, O(A * B).

Watch out for

• Mark a pair as seen when it joins the line, not when it leaves, so it never enters twice.
• Some versions only count C in a particular jug, or allow C as the total of both jugs. Read the question and change the target test.
• A string key like "3,0" in a hash set works but is slow. A 2D array indexed by the two amounts is faster.
• Huge jugs (say a billion cups) make the table too big. Use the math shortcut below.

What interviewers ask next

• When is it possible at all? Exactly when C <= max(A, B) and C is a multiple of gcd(A, B). This comes from Bezout's identity: every reachable amount is a mix of whole jugs.
• Fewest moves for huge jugs? Only two strategies can be best: always fill A and pour into B, or always fill B and pour into A. Simulate both (each takes at most about A + B moves) and take the smaller count.
• Three jugs, with a fixed amount of water and no tap (the classic 8, 5, 3 puzzle)? The same search over triples of amounts works.
• Print the moves, not just the count. Store which pair and which move first reached each pair, then walk back.

Remember this

Grown-up words: the pairs of amounts are states, the moves are edges, the map is the state graph, the ripples are BFS levels, the waiting line is a queue, and the "multiple of gcd" rule is Bezout's identity.