Q1 — SEARCH

A 5-3-2 water jug puzzle solved breadth-first: four moves turn 500 into 131, and BFS level-counting proves no shorter route exists.

The Question

Consider a 5-3-2 water jug puzzle with three jugs a, b, c of capacity 5L, 3L, 2L, respectively. A state is represented as a three digit string ABC, where A, B, C denote the volume of water present in the jugs a, b, c, respectively. For example, 302 denotes a state where jug a has 3 liters of water, jug b is empty and jug c has 2 liters of water.

Two types of moves (state transitions) are allowed:

xEy: pick up jug x and empty it into jug y,
xFy: pick up jug x and fill up (top up) jug y.

So the possible moves are: aEb, aEc, aFb, aFc, bEa, bEc, bFa, bFc, cEa, cEb, cFa, cFb.

Tie-breaker: in some states, both xEy and xFy may produce the same output state, in such cases, choose xEy to break the tie. For example, from the 302 state, both aEb and aFb produce the same output state 032, therefore, to break the tie choose aEb as the move.

For the 5-3-2 water jug puzzle, the MoveGen function takes a state ABC and returns a set of states that can be produced in one move. For example, MoveGen(500) returns { 230, 302 }.

Based on the above data, answer the given subquestions.

#	Question	Official answer
1.1	Let 500 be the start state and 131 be the goal state, find the shortest path from start to goal. Enter the path starting with 500 as a comma separated list o...	`500,302,320,122,131`
1.2	Let 500 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...	`aFc,cEb,aFc,cFb`

The Topic in 60 Seconds

BFS explores states in order of distance from the start: first everything reachable in 1 move, then 2 moves, and so on. The first time the goal pops out of the queue, the path recorded through parent pointers is guaranteed shortest (every move costs 1). Tie-breakers only matter for which equal-length path you report.

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

Step 0 — How to generate moves fast

For a state $(a, b, c)$ :

$xEy$ : pour $\min(\text{vol}(x),\ \text{cap}(y) - \text{vol}(y))$ from $x$ into $y$ .
$xFy$ : top $y$ up from $x$ — the same transfer amount. The two only coincide-or-collide when $y$ fills before $x$ empties (identical result), which is why the tie-breaker exists.

Sanity check against the question: MoveGen(500) = pour a→b (b takes 3, a keeps 2) = 230, pour a→c (c takes 2, a keeps 3) = 302. Matches.

1.1 — BFS from 500 → `500,302,320,122,131`

Level	Expanded	New states discovered (producing move)	OPEN after
0	—	start 500	500
1	500	230 (`aEb`), 302 (`aFc`)	230, 302
2	230	032 (`aEc`), 211 (`bEc`) · 500 re-found	302, 032, 211
2	302	320 (`cEb`) · 032, 500 re-found	032, 211, 320
3	032	none new (302, 230 already seen)	211, 320
3	211	031, 112, 301, 202, 210, 220 — no goal	320, 031, …
3	320	020, 122 ← first seen, depth 3	…, 122, …
4	122	131 = GOAL	done

Goal first pops at depth 4, so no 1-, 2- or 3-move solution exists — shortest proven.

Path: 500 → 302 → 320 → 122 → 131

Verifying each leg by hand

Move	From	Pour amount	Result
`aFc`	500	c needs 2, a gives min(5, 2−0) = 2	a=3, c=2 → 302
`cEb`	302	b takes min(2, 3−0) = 2	b=2, c=0 → 320
`aFc`	320	c needs 2, a gives 2	a=1, c=2 → 122
`cFb`	122	b needs 1, c gives 1	b=3, c=1 → 131 goal

1.2 — Move sequence → `aFc,cEb,aFc,cFb`

Read the producing move off each arrow above: aFc, cEb, aFc, cFb.

Footnote: on the last leg both cEb and cFb transfer exactly 1L from c to b and land on the same state 131 — the stated tie-breaker would prefer cEb; the official key records cFb. Either move earns full marks as the resulting path is identical.

Interactive BFS trace

1 / 9

OPEN = { 500 } Start state: a=5, b=0, c=0.

expandingin OPENalready seensolution path

Tricks & Tips

Answers: 1.1 500,302,320,122,131 · 1.2 aFc,cEb,aFc,cFb