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:

  1. Fill the five-gallon jug.
  2. Pour three gallons from the five-gallon jug to the three-gallon jug, leaving two gallons in the five-gallon jug.
  3. Empty the three-gallon jug.
  4. 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.
  5. Fill the five-gallon jug.
  6. 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.

Pages: 1 2

2 Responses to “Water Jugs Puzzle”

  1. Paul said

    On ideone I posted a BFS solution in Python3.

  2. Johan said

    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:

    CL-USER> (solve 4)
    ((0 0) (0 5) (3 2) (0 2) (2 0) (2 5) (3 4))
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: