AI: The water jug puzzle

Formulate a puzzle as a search problem and solve it with breadth-first search.

What to build

A program that measures an exact amount of water with two jugs and no markings, in the fewest steps.

Requirements

  • Jugs A and B start empty. Actions, tried in this order: fill A, fill B, empty A, empty B, pour A into B, pour B into A (pour until the source is empty or the target is full). The goal is reached when either jug holds exactly T litres.
  • Use breadth-first search, trying the actions in the order above and stopping at the first goal state reached. Print N steps, then each action as ACTION -> (a, b); or print impossible.

Input

One line: the capacities of A and B, and T.

Output

The steps, or impossible.

Constraints

Capacities ≤ 100; 0 ≤ T ≤ 100.

Example

Input:

3 5 4

Output:

6 steps
fill B -> (0, 5)
pour B into A -> (3, 2)
empty A -> (0, 2)
pour B into A -> (2, 0)
fill B -> (2, 5)
pour B into A -> (3, 4)

Why it works

Every reachable pair of amounts is a state, and breadth-first search reaches them in order of steps, so the first goal reached uses the fewest steps.

Examples

Example 1 · Input
3 5 4
Expected output
6 steps
fill B -> (0, 5)
pour B into A -> (3, 2)
empty A -> (0, 2)
pour B into A -> (2, 0)
fill B -> (2, 5)
pour B into A -> (3, 4)
Example 2 · Input
2 4 3
Expected output
impossible

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

A state is the pair (water in A, water in B); breadth-first search over these states finds the fewest steps.

Hint 2

When pouring, move min(water in the source, room left in the target).

Solution

Show one correct solution (try it yourself first)
from collections import deque

A, B, T = map(int, input().split())


def moves(a, b):
    pour_ab = min(a, B - b)
    pour_ba = min(b, A - a)
    return [
        ("fill A", (A, b)),
        ("fill B", (a, B)),
        ("empty A", (0, b)),
        ("empty B", (a, 0)),
        ("pour A into B", (a - pour_ab, b + pour_ab)),
        ("pour B into A", (a + pour_ba, b - pour_ba)),
    ]


start = (0, 0)
parent = {start: None}
queue = deque([start])
found = start if T == 0 else None
while queue and found is None:
    state = queue.popleft()
    for action, nxt in moves(*state):
        if nxt not in parent:
            parent[nxt] = (state, action)
            if T in nxt:
                found = nxt
                break
            queue.append(nxt)
if found is None:
    print("impossible")
else:
    steps = []
    while parent[found]:
        before, action = parent[found]
        steps.append(f"{action} -> ({found[0]}, {found[1]})")
        found = before
    print(f"{len(steps)} steps")
    for line in reversed(steps):
        print(line)

Lesson: Problem solving by search →