Three- and Five-liter Jug Plan
Problem statement
You have a3-liter jug and a5-liter jug, both initially empty, plus unlimited water and a drain. Construct a sequence of jug volumes that leaves exactly target liters in the5-liter jug. The reported interview asks for4 liters; this practice also includes the other integer targets from0 through5.
Return rows [amountIn3LiterJug,amountIn5LiterJug], including the initial state and the state after every action. To select one reproducible plan, repeat this policy until the5-liter amount equals target:
- If the5-liter jug is empty, fill it completely.
- Otherwise, if the3-liter jug is full, empty it completely.
- Otherwise, pour from the5-liter jug into the3-liter jug until the former is empty or the latter is full.
Stop as soon as the target is reached, including at the initial state. Use only these whole-jug fill, empty and maximal-pour actions. No minimum-step objective is imposed; the fixed policy determines the required plan.
Function
jugPlan(target: int) → int[][]Examples
Example 1
target = 4return = [[0,0],[0,5],[3,2],[0,2],[2,0],[2,5],[3,4]]Fill the5-liter jug, pour into the3-liter jug, empty the3-liter jug, pour the remaining2 liters into it, refill the5-liter jug, then pour1 liter. The5-liter jug now contains4 liters.
Example 2
target = 5return = [[0,0],[0,5]]One fill of the5-liter jug reaches the target.
Example 3
target = 0return = [[0,0]]The initial empty state already has0 liters in the5-liter jug, so no action is needed.
Constraints
0 <= target <= 5.