Question

Pouring water. We have three containers whose sizes are 10 pints, 7 pints, and 4 pints, respectively. The 7-pint and 4-pint containers start out full of water, but the 10-pint container is initially empty. We are allowed one type of operation: pouring the contents of one container into another, stopping only when the source container is empty or the destination container is full. We want to know if there is a sequence of pourings that leaves exactly 2 pints in the 7- or 4-pint container.

(a) Model this as a graph problem: give a precise definition of the graph involved and state the specific question about this graph that needs to be answered.

---

(b) What algorithm should be applied to solve the problem?

Answer 1

3.8 (a) Let G = (V, E) be our (directed) graph. We will model the set of nodes as triples of numbers (a₀, a₁, a₂) where the following relationships hold: Let S₀ = 10, S₁ = 7, S₂ = 4 be the sizes of the corresponding containers. a_i will correspond at the actual contents of the i^th container. It must hold 0 ≤ a_i ≤ S_i for i = 0,1,2 and at any given node a₀ + a₁ + a₂ = 11 (the total amount of water we started from). An edge between two nodes (a₀, a₁, a₂) and (b₀, b₁, b₂) exists if both the following are satisfied :

– the two nodes differ in exactly two coordinates (and the third one is the same in both).

– if i, j are the coordinates they differ in, then either a_i = 0 or a_j = 0 or a_i = S_i or a_j = S_j.

The question that needs to be answered is wether there exists a path between the nodes (0, 7, 4) and (∗, 2, ∗) or (∗, ∗, 2) where ∗ stands for any (allowed) value of the corresponding coordinate.

(b) Given the above description, it is easy to see that a DFS algorithm on that graph should be applied, starting from node (0, 7, 4) with an extra line of code that halts and answers ‘YES’ if one of the desired nodes is reached and ‘NO’ if all the connected component of the starting node is exhausted an no desired vertex is reached.

(c) It is easy to see that after a few steps of the algorithm (depth 6 on the dfs tree) the node (2,7,2) is reached, so we answer ‘YES’.