The Die Hard Jugs
You have an unmarked 3-gallon jug, an unmarked 5-gallon jug, and an unlimited water supply. A step is one of: filling a jug from the source, emptying a jug onto the ground, or pouring one jug into the other until the source is empty or the target is full. What is the minimum number of steps needed to end up with exactly 4 gallons in the 5-gallon jug?
Related problems & prerequisites
Worth solving first
- Wolf, Goat, and Cabbage 5.0/10
Source: Classic water-jug measuring puzzle, versions of which appear in Bachet (1612); popularised by the film 'Die Hard with a Vengeance' (1995). Statement written for AxiomIQ.