Q1 — Search: Water Jug BFS
Same three move-types, fresh endpoints: three pours carry 320 to 401 and BFS level-counting proves nothing shorter exists.
The Question
Consider a water-jug puzzle with three jugs a, b and c of capacities 5L, 3L and 2L, respectively. States encode volumes ABC; moves are xETy (pour until y tops out), xEy (empty x into y, y not topped), xTy (top up y, x retains water).
| # | Question | Official answer |
|---|---|---|
| 1.1 | Let 320 be the start state and 401 be the goal state, find the shortest path from start to goal. | 320,122,131,401 |
| 1.2 | Find the sequence of moves that produce the shortest path. | aTc,cTb,bEa |
Deep-dive: browse the Concepts section for Breadth First Search.
Step-by-step verification
| Move | From | Arithmetic | Result |
|---|---|---|---|
aTc | 320 (a=3,b=2,c=0) | top c (needs 2) from a; a keeps 1 | a=1, c=2 → 122 |
cTb | 122 (a=1,b=2,c=2) | top b (needs 1) from c; c keeps 1 | b=3, c=1 → 131 |
bEa | 131 (a=1,b=3,c=1) | b's whole 3L into a (room 4, not topped) | a=4, b=0 → 401 ✓ goal |
Shortest-path proof by BFS levels
| Level | States |
|---|---|
| 0 | 320 |
| 1 | 230 (a→b), 122 (a→c), 520 (b→a, c→a), 331 (c→b) |
| 2 | … 131 appears while expanding 122 … |
| 3 | … 401 appears while expanding 131 — FIRST arrival ⇒ shortest |
No goal at depths 0–2 ⇒ the 3-move solution is provably minimal.
Label logic worth quoting: the middle move is cTb (not cEb) because c ends holding 1L — not emptied; the last is bEa (not bETa) because a had room to spare — not topped.
Interactive trace
1 / 5
OPEN = { 320 } (a=3, b=2, c=0)
expandingsolution pathseen
Tricks & Tips
Answers: 1.1 320,122,131,401 · 1.2 aTc,cTb,bEa