Q1 — SEARCH

Blind BFS over the 5-4-1 water jug state space finds 221 in exactly 4 moves via 140 and 131.

The Question

Consider a 5-4-1 water jug puzzle with three jugs $a$ , $b$ , $c$ of capacity 5L, 4L, 1L, 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, 140 denotes a state where jug $a$ has 1 liter of water, jug $b$ has 4 liters of water and jug $c$ is empty.

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 140 state, both aEc and aFc produce the same output state 041, therefore, to break the tie choose aEc as the move.

For the 5-4-1 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, $\text{MoveGen}(500)$ returns $\{140, 401\}$ .

#	Question	Official answer
1.1	Let 500 be the start state and 221 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,140,131,230,221`
1.2	Let 500 be the start state and 221 be the goal state, find the sequence of moves that produce the shortest path from start to goal. Enter the sequence of mov...	`aFb,bFc,cEa,bFc`

The Topic in 60 Seconds

Every move costs 1, so the state space is an unweighted graph and breadth-first search (FIFO queue) returns a shortest path: the first time the goal is dequeued, its depth is minimal.

Operator semantics used by this puzzle:

Operator	Valid when	Effect
`xEy` (empty x into y)	ALL of x fits into y: $A_x \le cap_y - A_y$	$y$ gains $A_x$ , $x$ becomes 0
`xFy` (fill y up from x)	$A_x > 0$ and $y$ not full	transfer $cap_y - A_y$ , $y$ becomes full

If both operators yield the same state, the tie-breaker says report xEy.

Deep-dive: browse the Concepts section for uninformed search.

Working — BFS level by level

Depth	New states	Derivation
0	500	start
1	140, 401	`aFb`: b 0→4, a keeps 5−4=1 · `aFc`: c 0→1, a keeps 5−1=4 (`aEb` invalid: 5 L cannot fully empty into the 4 L jug)
2	041, 131, 410	from 140: `aEc` 1≤1 → 041, `bFc` c takes 1, b 4−1=3 → 131 · from 401: `cEb` 1≤4 → b=1, c=0 → 410
3	230, 311	from 131: `cEa` 1≤5−1=4 → a=2, c=0 → 230 · from 410: `aFc` c takes 1, a 4−1=3 → 311
4	221 = GOAL	from 230: `bFc` c takes 1, b 3−1=2

The goal first appears at depth 4, so the 5-state path is provably shortest.

OPEN-list trace

Step	Dequeue	Generated	OPEN after (FIFO)
1	500	140, 401	140, 401
2	140	041, 131 (500 already seen)	401, 041, 131
3	401	410 (041 duplicate, 500 seen)	041, 131, 410
4	041	nothing new (neighbours full or seen)	131, 410
5	131	230	410, 230
6	410	311	230, 311
7	230	221 — GOAL, stop	done

1.1 & 1.2 — Path and move sequence

#	Move	Transition	Arithmetic / rule
1	`aFb`	500 → 140	fill b: transfer 4, a keeps 5−4 = 1 (`aEb` invalid — 5 L cannot empty into a 4 L jug)
2	`bFc`	140 → 131	c takes 1, b keeps 4−1 = 3 (`bEc` invalid — 4 > 1)
3	`cEa`	131 → 230	1 ≤ 5−1 = 4 fits entirely → a=2, c=0 (`cFa` yields the same state — tie-breaker picks `cEa`)
4	`bFc`	230 → 221	c takes 1, b 3−1 = 2 → GOAL

Path: 500,140,131,230,221 · Moves: aFb,bFc,cEa,bFc

Interactive BFS trace

Each step shows the dequeued state, the exact pour arithmetic, and the FIFO queue contents.

1 / 8

OPEN = [500] Goal: 221

expanding (dequeued)in OPEN (queue)expandedgoal / shortest path

Tricks & Tips

Answers: 1.1 500,140,131,230,221 · 1.2 aFb,bFc,cEa,bFc