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 asACTION -> (a, b); or printimpossible.
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)