Water Jugs Puzzle
September 23, 2016
There are various puzzles in which water is poured from one jug to another to reach a desired amount of water. In the version we consider today, we have two jugs, an unlimited amount of water to fill them, and a drain into which we can pour an unlimited amount of water. The two jugs have known capacities, but it is not possible to accurately measure portions of a jug.
As an example, we wish to obtain four gallons of water, using jugs of capacities three and five gallons. Starting with two empty jugs, it is possible to obtain four gallons of water using the following six steps:
- Fill the five-gallon jug.
- Pour three gallons from the five-gallon jug to the three-gallon jug, leaving two gallons in the five-gallon jug.
- Empty the three-gallon jug.
- Pour two gallons from the five-gallon jug to the three-gallon jug, leaving the five-gallon jug empty and two gallons in the three-gallon jug.
- Fill the five-gallon jug.
- Pour one gallon from the five-gallon jug into the three-gallon jug, filling it, leaving the desired four gallons in the five-gallon jug.
Bruce Willis figured that out once; so too do thousands of school children every year.
Your task is to write a program that solves this kind of water-jug problem using the minimum number of steps (filling a jug, emptying a jug, or pouring one jug into the other). When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
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: