AI · Theory
Water jug: jugs of size A and B, get exactly D litres. States are (x, y) litres. Actions: fill, empty, pour. Search (BFS) finds a shortest sequence. Classic AI planning toy — not a plumbing exam.
3 and 5 litre jugs, goal 4. Trace a few states on paper before code. That trace is the viva.
Water Jug Problem — output — a list of (x,y) states ending with 4 litres in one jug. BFS on states.
State representation + one action trace.
# 3 and 5 litre jugs → 4
from collections import deque
def jugs(a=3, b=5, goal=4):
q = deque([(0, 0, [])])
seen = {(0, 0)}
while q:
x, y, path = q.popleft()
if x == goal or y == goal or x + y == goal:
return path + [(x, y)]
nxt = [
(a, y), (x, b), (0, y), (x, 0),
(x - min(x, b - y), y + min(x, b - y)),
(x + min(y, a - x), y - min(y, a - x)),
]
for s in nxt:
if s not in seen:
seen.add(s)
q.append((s[0], s[1], path + [(x, y)]))
return None
print(jugs())
Water Jug Problem — output: a list of (x,y) states ending with 4 litres in one jug. BFS on states.