Using Graphs to Solve the Jug Problem

In the movie "Die Hard with a Vengeance" (starring Bruce Willis and Samuel Jackson), the heros are faced with the prospect of a bomb exploding unless they can determine how to measure exactly 4 gallons of water using two jugs that hold exactly 5 gallons and 3 gallons respectively. Fortunately, this problem is very simple and easily solved in the 30 seconds or so given in the movie, but what will happen in "Die Hard with a Terrible Vengeance", when the jugs may be much bigger and the problem much harder? Obviously the police need an automated solution to the "jug" problem.

Unlike the scene in the movie, in which any solution was sufficient, we want our automated system to produce the best solution, ie. the one that requires the least heavy lifting of water jugs. Furthermore, we'd like to know the best solution for any given initial configuration of water in the two jugs. (In the movie both jugs were empty initially.)

The general problem to be solved is this: given an (essentially) infinite supply of water and two jugs holding exactly B and S gallons (where B > S), show how to get exactly P gallons (P <= B) in one of the jugs using the following six operations:

1. emptyB - pour out the contents of the larger jug
2. emptyS - pour out the contents of the smaller jug
3. fillB - fill the larger jug from the water supply
4. fillS - fill the smaller jug from the water supply
5. pourStoB - pour the contents of the smaller jug into the larger jug, until the larger jug is full, or the smaller jug is empty
6. pourBtoS - pour the contents of the larger jug into the smaller jug, until the smaller jug is full, or the larger jug is empty

We can model this problem using a graph. Each node in the graph is a pair (b,s) where

• b represents the number of gallons in the jug that holds at most B gallons, 0 <= b <= B

• s represents the number of gallons in the jug that holds at most S gallons, 0 <= s <= S

There is a directed arc between two nodes (x,y) and (u,v) if, given x gallons in the jug that holds at most B gallons, and y gallons in the jug that holds at most S gallons, we can perform any one of the six operations listed above (i.e., empty either jug, fill either jug, pour from one jug to another) and end up with u gallons in the big jug and v gallons in the small jug.

Each operation has an associated weight, which is proportional to the effort required to lift the water used in that operation. So, in the graph, each arc has a weight corresponding to the number of gallons lifted. The weights are defined as follows:

1. emptyB - number of gallons in the large jug before being emptied
2. emptyS - number of gallons in the small jug before being emptied
3. fillB - B, the number of gallons in the large jug when filled
4. fillS - S, the number of gallons in the small jug when filled
5. pourStoB - number of gallons in the small jug before pouring
6. pourBtoS - number of gallons in the large jug before pouring

In this graph representation, any node of the form (P,k) or (j,P) represents a solution to the problem of P gallons, since one of the jugs holds exactly P gallons.

So, given two jugs that hold B and S gallons, and an initial configuration (b,s), where the large jug has b gallons and the small jug has s gallons, you are to find the sequence of operations requiring the least effort (as determined by the weights of the operations) that produces P gallons in one of the jugs.

That is, you are to write a program with five inputs B, S, b, s, and P, which builds the graph of B x S nodes, and finds the shortest path between (b,s) and (j,k), for some j and k, where j=P or k=P.

Extra Fun for Extra Credit:

1. Suppose the initial state is always (0,0), and furthermore, assume we want the solution requiring the fewest number of operations. (That is, suppose we aren't concerned with the weights of the operations.) How might you solve this simpler version of the problem?

2. Can you describe a scenario in which the quickest solution (in terms of the number of operations) is not the easiest solution (in terms of the weight of water lifted)?

3. Given two jugs of size B and S, and assuming that both jugs are initially empty, for what values of P is the problem solvable? In other words, can you write a simple mathematical expression that describes all values of P that can be measured with jugs of size B and S (ignoring weights and number of operations)?

This assignment is due at the start of class on Tuesday, Feb 16.