Measure Target Water with Jugs | Dataford Interview Questions

Your question is Measure Target Water with Jugs. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

At Acme Utilities, you are given two water jugs with capacities jug1 and jug2, and a target amount target. Starting from both jugs empty, return a shortest sequence of valid operations that results in exactly target gallons in either jug.

Valid operations are:

Fill a jug completely.
Empty a jug completely.
Pour water from one jug into the other until the source is empty or the destination is full.

Formal Specification

Implement a function that takes three integers: jug1, jug2, and target. Return a list of states, where each state is [a, b] representing the current amount of water in jug 1 and jug 2. The returned list must start with [0, 0] and end at a state where a == target or b == target. If no solution exists, return an empty list.

Constraints

1 <= jug1, jug2 <= 100
0 <= target <= max(jug1, jug2)
A state is represented as two integers [a, b]
Return any one shortest valid sequence if multiple solutions exist

Function Signature

def measure_water(jug1, jug2, target):