2022 Term 3 · Forenoon

21 questions from 22T3_fn.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-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.

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

1.1SEARCHSolution ↗

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

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

1.2SEARCHSolution ↗

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

NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: aFb,bFc,cEa

1 / 11