2022 Term 3 · Afternoon

21 questions from 22T3_an.yaml. Answer everything, then hit "Check answers".

Worked solutions, step by step ↗Stuck on a question? Open its full solution — traces, visuals, shortcuts.

21 questions

Question stem · Q1

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 $A B C$ , 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 $A B C$ and returns a set of states that can be produced in one move. For example, $MoveGen (500)$ returns ${140, 401}$ .

Tip: click any diagram to expand it full-screen.

1.1SEARCHSolution ↗

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 of states.

NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: 500,411,747

1.2SEARCHSolution ↗

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 moves as a comma separated list.

NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: aFc,cFb,aEc

1 / 11