Q1 — Search: Water Jug BFS

Three move types on the 5-3-2 jug set: BFS level-counting finds 212 to 131 in three pours and 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.

A state, encoded as a digit string ABC, denotes volume of water in jugs a, b and c, respectively. For example, state 122 denotes that jugs a, b and c contain 1L, 2L and 2L of water, respectively.

The allowable moves (actions) are

xETy: pick up jug $x$ and empty it into jug $y$ and jug $y$ is also topped up,
xEy: pick up jug $x$ and empty it into jug $y$ and jug $y$ is still not topped up,
xTy: pick up jug $x$ and top up jug $y$ and jug $x$ is still not emptied out.

For example: $122 \xrightarrow{cEa} 320 \xrightarrow{bETa} 500 \xrightarrow{aTb} 230$ .

MoveGen takes a state ABC and returns a set of neighbours that are one move away from ABC. For example, $\text{MoveGen}(122) = \{ 032, 302, 320, 131 \}$ .

#	Question	Official answer
1.1	Let 212 be the start state and 131 be the goal state, find the shortest path from start to goal. Enter the path starting with 212 as a comma separated list o...	`212,410,401,131`
1.2	Let 212 be the start state and 131 be the goal state, find the sequence of moves that produce the shortest path from start to goal. Enter the sequence of mov...	`cEa,bEc,aTb`

The Topic in 60 Seconds

Move	Meaning	Amount poured
$xEy$	empty $x$ into $y$ , $y$ NOT topped up	all of $x$ , and $y$ had room left
$xETy$	empty $x$ into $y$ , $y$ tops out	$\text{cap}(y) - \text{vol}(y)$
$xTy$	top up $y$ from $x$ , $x$ keeps some	$\text{cap}(y) - \text{vol}(y)$

The three collapse to: pour $\min(\text{vol}(x),\ \text{cap}(y)-\text{vol}(y))$ ; the label records which side ran out. BFS explores level by level, so the first arrival at the goal is provably shortest.

Deep-dive: browse the Concepts section for Breadth First Search.

Step 0 — Verify the worked example

$122$ : a=1, b=2, c=2.

$cEa$ : c's whole 2L into a (room 4) → a=3, c=0 → 320 ✓
$bETa$ : top a (room 2) exactly from b's 2L → a=5, b=0 → 500 ✓
$aTb$ : top b (needs 1) from a → b=3, a=4... careful: example says 230 — reading it as top-from-full-a: a=5−3=2 → 230 ✓ (that step started from 500).

1.1 — BFS from 212 → `212,410,401,131`

Start 212 (a=2, b=1, c=2):

Level	Expanded	New states (producing transfer)
0	—	212
1	212	aE/ET/T-b → 032 · bE/T-a → 302 · cE/T-a → 410 · cE/T-b → 203
2	032	230 (c→a), 302 seen
2	302	502 (c→a), 212, 032 seen
2	410	230, 500 (b→a), 401 (bEc / bETc / bTc: b's 1L → c)
2	203	033 (a→b), 500 (c→a), 230 (c→b)
3	…	from 401 (a=4,b=0,c=1): top b from a → b=3, a=1 → 131 GOAL

No goal at levels 1–2 ⇒ depth 3 is optimal. Path: 212 → 410 → 401 → 131.

1.2 — Move sequence → `cEa,bEc,aTb`

Move	From	Arithmetic	Result
`cEa`	212	c's 2L empties into a (room 3, not topped)	a=4, c=0 → 410
`bEc`	410	b's 1L empties into empty c (not topped)	b=0, c=1 → 401
`aTb`	401	top b (needs 3) from a's 4L; a keeps 1	b=3, a=1 → 131 ✓

Note why the last label is aTb and not aEb: a ends with 1L — not emptied — exactly the T-move signature.

Interactive BFS trace

1 / 5

OPEN = { 212 } (a=2, b=1, c=2)

expandingin OPENsolution pathseen

Tricks & Tips

Answers: 1.1 212,410,401,131 · 1.2 cEa,bEc,aTb