Water Jugs Puzzle
September 23, 2016
We first note that some combinations of jug capacities and targets do not offer a solution. Specifically, if the greatest common divisor of the capacities of the two jugs does not evenly divide the target, there is no solution. For instance, if the two jugs have capacities of twelve gallons and three gallons, the only attainable targets are multiples of three: zero gallons, three gallons, six gallons, nine gallons, or twelve gallons.
Once we know that a solution is possible, we adopt the strategy of always pouring in one direction, from the “from” jug to the “to” jug. If the “to” jug is full, empty it. If the “from” jug is empty, fill it. Otherwise, pour as much as you can from the “from” jug to the “to” jug. Stop when one or the other of the jugs has the desired amount of water. You’ll have to try both possible arrangements of “from” jug and “to” jug to determine which requires the smallest number of steps. Here’s a function that handles the pouring and displays the steps that it is performing, returning the number of steps required:
(define (water-jugs-verbose fcap tcap target)
(let loop ((fjug 0) (tjug 0) (steps 0))
(display "step: ") (display steps)
(display "; fjug: ") (display fjug)
(display "; tjug: ") (display tjug)
(cond ((= fjug target)
(display "; done; target in fjug") (newline)
steps)
((= tjug target)
(display "; done; target in tjug") (newline)
steps)
((= tjug tcap) ; "to" jug full; empty it
(display "; tjug full; empty it") (newline)
(loop fjug 0 (+ steps 1)))
((zero? fjug)
(display "; fjug empty; fill it") (newline)
(loop fcap tjug (+ steps 1)))
(else
(display "; pour fjug into tjug") (newline)
(let ((x (min (- tcap tjug) fjug)))
(loop (- fjug x) (+ tjug x) (+ steps 1)))))))
And here are two examples so you can see how it works:
> (water-jugs-verbose 5 3 4) step: 0; fjug: 0; tjug: 0; fjug empty; fill it step: 1; fjug: 5; tjug: 0; pour fjug into tjug step: 2; fjug: 2; tjug: 3; tjug full; empty it step: 3; fjug: 2; tjug: 0; pour fjug into tjug step: 4; fjug: 0; tjug: 2; fjug empty; fill it step: 5; fjug: 5; tjug: 2; pour fjug into tjug step: 6; fjug: 4; tjug: 3; done; target in fjug 6 > (water-jugs-verbose 3 5 4) step: 0; fjug: 0; tjug: 0; fjug empty; fill it step: 1; fjug: 3; tjug: 0; pour fjug into tjug step: 2; fjug: 0; tjug: 3; fjug empty; fill it step: 3; fjug: 3; tjug: 3; pour fjug into tjug step: 4; fjug: 1; tjug: 5; tjug full; empty it step: 5; fjug: 1; tjug: 0; pour fjug into tjug step: 6; fjug: 0; tjug: 1; fjug empty; fill it step: 7; fjug: 3; tjug: 1; pour fjug into tjug step: 8; fjug: 0; tjug: 4; done; target in tjug 8
The variables here are fcap and tcap for the capacities of the “from” and “to” jugs, fjug and tjug for the current contents of the “from” and “to” jugs, and target for the desired amount of water. Here’s a non-verbose version of the same function, so you can see how simple it really is:
(define (water-jugs fcap tcap target)
(let loop ((fjug 0) (tjug 0) (steps 0))
(cond ((or (= fjug target) (= tjug target)) steps)
((= tjug tcap) (loop fjug 0 (+ steps 1)))
((zero? fjug) (loop fcap tjug (+ steps 1)))
(else (let ((x (min (- tcap tjug) fjug)))
(loop (- fjug x) (+ tjug x) (+ steps 1)))))))
Then it is easy to solve the puzzle: Check if it is possible, and if it is, try both possibilities and return the smallest:
(define (jugs x y target)
(if (positive? (modulo target (gcd x y))) #f
(min (water-jugs x y target) (water-jugs y x target))))
> (jugs 3 5 4) 6
You can run the program at http://ideone.com/dy2IzB.
The problem was first described by Claude Gaspard Bachet in 1612 in his book Problèms plaisant, though it is probably older.
There are several ways to solve the puzzle. You can build the graph of possible actions at each state, then use breadth-first search to find the shortest path to the target. There is a dynamic programming solution, but it’s tricky. A math solution uses the extended Euclidean algorithm to solve a diophantine equation. Our solution is simple and elegant, though if the jugs are large some of the other methods might be faster.
The puzzle has several variants. One common variant replaces the infinite sink and drain with a single jug the size of the sum of the two smaller jugs, initially filled with water. Other variants involve several jugs, or different colors of water that may not be combined (though at different times the same jug may hold different colors of water).
Programming Praxis 
On ideone I posted a BFS solution in Python3.
Common Lisp, non-verbose, breadth-first search:
(defparameter *jug-1-capacity* 3) (defparameter *jug-2-capacity* 5) (defun successors (state) (let* ((x (first state)) (y (second state)) (dx (- *jug-1-capacity* x)) (dy (- *jug-2-capacity* y))) (remove state (remove-duplicates (list (list 0 y) (list x 0) (list *jug-1-capacity* y) (list x *jug-2-capacity*) (if (<= y dx) (list (+ x y) 0) (list *jug-1-capacity* (- y dx))) (if (<= x dy) (list 0 (+ x y)) (list (- x dy) *jug-2-capacity*))) :test #'equal) :test #'equal))) (defun solutionp (state goal) (or (= (first state) goal) (= (second state) goal))) (defun make-path (from predecessors &optional (so-far ())) (if (null from) so-far (make-path (cdr (assoc from predecessors :test #'equal)) predecessors (cons from so-far)))) (defun solve (goal) (labels ((iter (todo done predecessors) (unless (endp todo) (let ((state (first todo))) (if (solutionp state goal) (make-path state predecessors) (let ((new-todos (set-difference (set-difference (successors state) todo :test #'equal) done :test #'equal))) (iter (append (rest todo) new-todos) (cons state done) (pairlis new-todos (make-list (length new-todos) :initial-element state) predecessors)))))))) (iter '((0 0)) () '(((0 0))))))The steps to obtain four gallons of water are: