The Two Water Jug Puzzle

Problem :

You have given two empty jugs A and B in which the volume of liquid that can be poured is not marked. But Jug A can hold a maximum amount of 03 Liters and Jar B can hold a maximum amount of 04 Liters. There’s an unlimited amount of water resources and also a place to discharge water. There’s a requirement to obtain 02 Liters of water from one of the jugs somehow. How would you achieve this requirement?

Figure 1.1

Hint: There can be several approaches. You need to pick the best solution.

The steps you can perform to achieve this requirement are as follows.

• Empty a Jug.
• Fill a Jug.
• Pour water from one jug to the other until one of the jugs is either empty or full.

Approach 01 — Using Breadth-First Search (BFS)

Now you might have a question, what’s BFS? Let’s look at the definition.

Breadth-first search is a graph traversal algorithm. It starts traversing the graph from the root node and explores all the neighboring nodes. Then, it selects the nearest node and explores all the unexplored nodes. The algorithm continues the same process for each of the nearest nodes until it finds the goal.

Here, we’ll be defining the states in terms of (A, B).

A — Amount of water in Jug A

B — Amount of water in Jug B

Therefore our initial state would be (0, 0) since both the jugs are empty and the final states of the process could be either (0, 2) or (2, 0) which means any jug would contain 02 Liters of water at the end.

The steps that we’ll be performing in this approach are as follows.

1. Empty a Jug: The state transition could be (A, B) -> (0, B). Let’s assume that we empty the Jug A.
2. Fill a Jug: The state transition could be (0, 0) -> (A, 0). Let’s assume that we Fill Jug A.
3. Pour water from one jug to the other until one of the jugs is either empty or full: The state transition could be (A, B) -> (A-d, B+d).

Following is the implementation of the above approach using python language.

Approach 02— Using Memoization and Recursion

In this approach, we’ll be following six steps such as:

• Empty the jug A completely.
• Empty the jug B completely.
• Fill the jug A.
• Fill the jug B.
• Fill the water from jug B into jug A until jug A is full or jug B has no water left.
• Fill the water from jug A into jug B until the jug B is full or jug A has no water left.

Here, visit each of the six steps, using Recursion, one by one until one of them is true. As the same recursive calls can be repeated, each value is stored using memoization so that the recursive function does not run again and return the stored value.

Following is the implementation of the above approach using python language.

Do you have any other suggestions? Please comment below.