The two jars problem is a puzzle, in which the goal is to measure some amount of water using two (several) jars of different capacity and an unlimited source of water.

Task

You have two jars, the first one has a 3 liters capacity, the second one 5 liters. You also have an unlimited source of water. Measure exactly 4 liters of water.

Solution

Firstly, we must construct a graph representing the given problem. Nodes on the horizontal axis will represent volume of water in the larger jar, analogously nodes on the vertical axis will represent volume of water in the smaller jar. Horizontal edges will denote pouring water into the larger jar, vertical into the smaller one. Finally the diagonal edges will stand for pouring water from one jar into the other.

The graph will not contain any inner node, because we are able to precisely measure the water, only if we completely fill or empty at least one of the jars.

Now we can use bread first search to traverse the graph starting at node 0/0. For every node, the procedure will store its predecessor. When the algorithm reaches the 0/4 node, it will terminate the searching phase and will reconstruct the backward path.

Variants of the puzzle

If the operations performed are not equivalent – pouring water from one jar into the other might be considered as more difficult than just emptying one jar – than we have to assign costs to the edges and find the shortest path. To do so, we can use Dijkstra, Bellman-Ford or Floyd-Warshall algorithm.

The puzzle can also be generalized to any number of jars. The solution to this problem is simillar to the original one, we only have to construct the graph in more dimensions (equal to the number of jars).