Solving Water Jug Problem using BFS

Solving Water Jug Problem using BFS
Solving Water Jug Problem using BFS

Introduction

Water Jug Problem is also known as Water Pouring Puzzles, measuring puzzles and decanting problems. These belong to a class of puzzles, in which there are a finite and specific number of water jugs having predefined integral capacities, in terms of gallons or litres. 

The prime challenge in the water jug problem is that these water jugs do not have any calibrations for measuring the intermediate water levels. In order to solve these puzzles, you are given a required measurement that you have to achieve by transferring waters from one jug to another, you can iterate multiple times until the final goal is reached, but in order to get the best results, the final solution should have a minimum cost and a minimum number of transfers.

Image Source: Pinterest

Problem Statement:

You are given two jugs, one of m litre and another of n litre capacity. Both the jugs are initially empty. The jugs do not have any intermediate markings and labelling for measuring smaller quantities. You can be asked to measure d litres of water, such that d is less than n.

Solution:

First, fill the n litre jug and empty all its contents in the “m” litre jug. As soon as the n litre jug becomes vacant, refill it. As soon as the “m” litre jug becomes full, empty it. Repeat the first three steps until either the n litre jug or the m litre jug, has exactly d litres of water in it

Numerous source codes have been devised for solving Water Jug problems using recursion, searching and sorting algorithms. The solution written using Breadth-First Search is considered to be one of the most optimum solutions. Let’s first understand, “What is Breadth-First Search (BFS)?”.

Breadth-first search is also known as “Level order traversal”.  It is a graph traversal algorithm, in which the graph traversal begins from the root node and explores the entire range of adjacent nodes. Then the nearest node is picked up and all the unexplored/unvisited nodes are explored/visited. The same steps are followed until the goal node is reached.

Breadth-first search is usually compared with the depth-first search (DFS) algorithm. For solving the Water Jug Puzzle, we prefer the Breadth-first search over the Depth-first search as it is not necessary that the depth-first search will find the shortest path. BFS will not lead to an infinite loop and finds the shortest possible path between the root node and the goal via other accessible nodes.

In Graph theory, the Breadth-first search is used to solve a wide range of problems. For example Cheney’s algorithm, Peer to Peer Networks, Copying garbage collection, Crawlers in Search Engines, Finding Minimum Spanning Tree, GPS tracking system, Finding the shortest path between two given nodes u and v, by measuring the path length by the number of edges and so on.

Worst case time complexity of BFS : O(|E|) = O(b^d)
Space complexity of BFS : O(|V|) = O(b^d)

blog banner 1

Image Source: FreelancingGig.com

What is the State Space?

The set of all possible configurations available for a given problem and its environment variables is known as its state space. The state contains Static information related to the system at any point. Each distinct configuration of the problem is known as its state. While iterating through the solutions one state can be achieved more than once.

The state-space for the water jug problem is usually represented as a set of ordered pairs of integers (X, Y), where X= 1,2,3,…..m and Y=1,2,3,……n. Where X is the number of gallons/litres of water in Jug A and Y is the number of gallons/litres of water in Jug B. The highest possible value of X is m which is the actual capacity of the gallon. Similarly, for Y, the highest possible value is n, which is its maximum capacity.

Implementation of the BFS Algorithm:

The below-mentioned four steps are followed to solve the water jug problem:

  • Define a state space that contains all possible configurations of the water jugs and even some of the unreachable ones.
  • Specify one or multiple states within that space that describe all the possible situations from which we can initiate the problem-solving process. These states are referred to as the initial states.
  • Specify one or more states which are regarded as the acceptable solutions to the problem. These states are known as goal states.
  • Specify a set of rules also known as predictions that describe the actions (operators) allowed and a well-defined control strategy for aligning the order of application of these predictions.

We make some assumptions for solving the Water Jug Problem:

  • You can fill any Jug from the pump.
  • You are allowed to pour water from a jug into the ground/bucket.
  • You are allowed to pour water from one jug to another.
  • You can not use any other measuring device or parameters.

Image Source: letitsnowglobe

Source Code for Water Jug Problem in CPP:

The solution given below is a C++ code for solving the Water Jug problem using Breadth-First Search and Queue. All the intermediary operations are written using if-else-if conditions. The output is given in the form of state configuration representations.

#include <bits/stdc++.h>
using namespace std;
class nodes{
	public: 
		pair<int,int> p;
		int first;
		int second;
		string s;
};
string makestring(int a,int b){
	std::stringstream out1;
	std::stringstream out2;
	string t1,t2,str;
    out1 << a;
    t1 = out1.str();
    out2 << b;
    t2 = out2.str();
    str = "("+t1+","+t2+")";
    return str;
}
int main()
{
	int counter = 0;
    ios::sync_with_stdio(false);
    //pair<int,int> cap,ini,final;
    nodes cap,ini,final;
    ini.p.first=0,ini.p.second=0;
    ini.s = makestring(ini.p.first,ini.p.second);
    //Input initial values
    cout<<"Enter the capacity of 2 jugs\n";
    cin>>cap.p.first>>cap.p.second;
    //input final values
    cout<<"Enter the required jug config\n";
    cin>>final.p.first>>final.p.second;
    //Using BFS to find the answer
    queue<nodes> q;
    q.push(ini);
    nodes jug;
    while(!q.empty()){
    	//Base case
    	jug = q.front();
    	if(jug.p.first == final.p.first){// && jug.p.second == final.p.second){
    		cout<<jug.s<<endl;
    		// counter++;
    		// if(counter==5)
	  		return 0;
    	}
    	nodes temp = jug;
    	//Fill 1st Jug
    	if(jug.p.first<cap.p.first){
			temp.p = make_pair(cap.p.first,jug.p.second);
			temp.s = jug.s + makestring(temp.p.first,temp.p.second);
			q.push(temp);
    	}
    	//Fill 2nd Jug
    	if(jug.p.second<cap.p.second){
			temp.p = make_pair(jug.p.first,cap.p.second);
			temp.s = jug.s + makestring(temp.p.first,temp.p.second);
			q.push(temp);
    	}
    	//Empty 1st Jug
    	if(jug.p.first>0){
			temp.p = make_pair(0,jug.p.second);
			temp.s = jug.s + makestring(temp.p.first,temp.p.second);
			q.push(temp);
    	}
    	//Empty 2nd Jug
    	if(jug.p.second>0){
			temp.p = make_pair(jug.p.first,0);
			temp.s = jug.s + makestring(temp.p.first,temp.p.second);
			q.push(temp);
    	}
    	//Pour from 1st jug to 2nd until its full
    	if(jug.p.first>0 && (jug.p.first+jug.p.second)>=cap.p.second){
    		temp.p = make_pair((jug.p.first-(cap.p.second-jug.p.second)),cap.p.second);
    		temp.s = jug.s + makestring(temp.p.first,temp.p.second);
    		q.push(temp);
    	}
    	//Pour from 2nd jug to 1st until its full
    	if(jug.p.second>0 && (jug.p.first+jug.p.second)>=cap.p.first){
    		temp.p = make_pair(cap.p.first,(jug.p.second-(cap.p.first-jug.p.first)));
    		temp.s = jug.s + makestring(temp.p.first,temp.p.second);
    		q.push(temp);
    	}
    	//Pour all water from 1st to 2nd
    	if(jug.p.first>0 && (jug.p.first+jug.p.second)<=cap.p.second){
    		temp.p = make_pair(0,jug.p.first+jug.p.second);
    		temp.s = jug.s + makestring(temp.p.first,temp.p.second);
    		q.push(temp);
    	}
    	//Pour from 2nd jug to 1st until its full
    	if(jug.p.second>0 && (jug.p.first+jug.p.second)<=cap.p.first){
    		temp.p = make_pair(jug.p.first+jug.p.second,0);
    		temp.s = jug.s + makestring(temp.p.first,temp.p.second);
    		q.push(temp);
    	}
    	q.pop();
    }
	return 0;
}

Example:
Input: 4 3 2 3
Output: (0,0) (4,0) (1,3) (1,0) (0,1) (4,1) (2,3)

Code Courtesy: Anirudh Bagri

Issues in the Water Jug Problem :

Although we have multiple feasible solutions for the water jug problem, yet there are several issues faced by the programmers and knowledge engineering experts. Such issues include :

  • Throwing the water in the ground should not be allowed as this leads to waste of water.
  • Before filling any jug, we have to check if it is filled or not. This leads to extra space complexity as a variable has to be created for tracking this condition.
  • Many times, intermediate states are redundant and therefore, leads to repetitive operations, leading to an additional computational time.
  • The state representation can be confusing for beginners, especially if there are more than ten jugs available.
  • In the output, only the configuration states are displayed, it will be very difficult to display the operations carried out on each state. In the case of larger inputs, this becomes un-inferable.

Frequently Asked Questions

Why is DFS not used for solving a water jug problem?

DFS is also known as Depth-First Search sometimes turns out to be an incomplete algorithm and may end up abruptly, giving a Non-Optimal Solution. The solution generated by the depth-first search may be incomplete as this algorithm goes on to the deepest possible point in the first path. In case, that first path leads to infinity, the algorithm will turn into an infinite loop and will never give any correct solution.

If many consecutive solutions give the same answer, usually that is considered to be the optimal solution but actually, it isn’t. If the target Goal State is not present in that path, then the Goal State will never be reached as the prior loop is an infinite one.

Are there more problems similar to The Water Jug problem?

There are several other knowledge engineering-driven daily life problems that can be solved by writing artificial intelligence-based algorithms. Most of these are solved by using the Breadth-First Search (BFS) or Depth First Search (DFS).

Nowadays, to reduce the time complexity algorithm developers have devised several combinations of BFS and DFS along with other binary tree-based programming strategies. Some of the commonly studied Artificial intelligence-based problems include:

1. Missionaries and Carnivals Problem
2. Chess Problem
3. 8- Queen Problem
4. 8- Puzzle Problem
5. Monkey Banana Problem
6. Tower of Hanoi Problem
7. Cryptarithmetic Problem

What is the time complexity of the Water Jug problem?

In the water jug problem, we carry multiple operations on the previous state of the system and try to reach the goal state. Most of the algorithms that are written down to solve the water jug problem include the following four steps:
Assuming that you are given two unlabelled jugs m and n, and the desired quantity of water is d litres.

Step One: Fill the m litre jug and empty its contents into the n litre jug.
Step Two: If at any instant the m litre jug becomes empty fill it with water.
Step Three: If at any instant the n litre jug becomes full empty it.
Step Four: Repeat steps one, two, and three till any of the jugs among the n litre jug and the m litre jug contains exactly d litres of water.

The time complexity of the solutions is usually O (m*n).

Do we have a Heuristic Function for solving the Water Jug Problem?

We usually add a heuristic function while solving problems to estimate how close we are to our goal. The closer the goal, the lower is the value of the heuristic function, it is often known as the estimated cost. The best-estimate function of the problem is admitted as its heuristic function. In the water jug problem, there is a constraint that only certain amounts of water can be added to a gallon of water.

The heuristic function proposed for a water jug problem, h(x,y) = (x * a) + (y * b), and has the lowest value at (0,0). This function is definitely feasible and consistent, as in practice it is the amount that is required to get to the goal from that node in one step, assuming that one step is possible. As soon as, you reach the goal node, this value becomes zero.

Conclusion

The BFS approach for solving the water jug problem has been one of the most feasible solutions. Although, various programmers have solved the Water Jug problem in O (m*n) using recursion and other tree exploitation strategies. This can be written in any of the programming languages including development-based languages such as JavaScript, Swift, etc.

Algorithms are updated very swiftly, still, Artificial Intelligence experts are working to find a better solution for solving the Water Jug problem. Analytically, a better solution would be a hybrid algorithm, devised by combining the properties of breadth-first search, depth-first search, recursive function calls, priority approach.

To solve more problems on data structure and algorithm please visit our problem section.

By Vanshika Singolia