The hiring process of various companies has evolved over the years. They have extended their part to making the candidates solve tough puzzles using their code implementation. But why? Well, for starters the analytical skills can be tested, and secondly, the coding skills are used to get the most optimal way to solve the riddle.
In today's tech blog, we are going to understand and solve a well-known problem called the Water Jug Problem. We will understand the problem, check an example, and methods to solve it, with C++ and Java codes.
What is the Water Jug Problem?
Here is the problem statement for Water Jug Problem:
You are given 2 jugs with the capacity 'm' and 'n' respectively. Initially, they are given empty. There is an unlimited supply of water. You can either fill the whole jug or a quantity that is less than the given capacity of jugs. Now, you are also given a third positive integer 'd'. Using the 2 given jugs, you need to come up with a solution to have 'd' amount of water in them and return the number of steps you took to reach that capacity.
Understanding the Problem
Before beginning the coding part, it is very important for you to understand what the question is asking you to do. Many students just copy the code from web servers and later, when the interviewer asks any question from it, they are stuck and even embarrassed. So, to save yourself from such questions, kindly go through this section carefully.
So, you are given 2 jugs with their capacities. It has also been clearly stated in the question that with the unlimited water supply, you can either fill the whole jug up to its capacity or somewhat less than that. Keep that in mind.
Secondly, we need to find a way to somehow have a 'd' amount of water left in the jugs. Basically, we need to transfer, fill and, empty the jugs to get the required capacity of water in the jugs.
The next most important question is which data structure should you choose for this question. You cannot use arrays as it will be a heavy task for both the compiler(in terms of time and auxiliary space complexity) and you(in terms of long codes).
You should choose a structure with which you can manage the content of both jugs simultaneously on the front. The possible and safest option is to use Sets or Pairs.
How to Approach the Solution
Now that we have chosen what to work with, let's understand how you can actually make it work. Well, for starters you can have (a, b) which represents the amount of water currently in jug 1 and jug 2 respectively. Initially, both the components will be (0, 0) since the jugs are empty in the beginning. The final state of the jugs will be either (0, d) or (d, 0) as both add up to give a total of the required quantity.
The following operations can be performed on the jugs:
- Empty a jug (a, b) -> (0, b)
- Fill a jug (0, b) -> (a, b)
- Transfer water from one jug to another.
Example
Input: 3, 5, 4
Output: 6
Explanation: The following steps are taken:
- Fill the 5-liter jug completely.
- Transfer 3 liters from a 5-liter jug to a 3-liter jug.
- Empty the 3-liter capacity jug.
- Transfer the remaining 2 liters from a 5-liter jug to a 3-liter jug.
- Now, fill the 5-liter jug fully.
- Pour 1 liter from a 5-liter jug into a 3-liter jug.
- There! We have 4 liters in the first jug, now empty the 2nd jug.
For more clarity, check the below illustration.
03 Methods to Solve the Water Jug Problem
Now, you know what the problem is and what is the approach behind the solution. Next, discuss some methods with which you can code this problem. Following are the three methods, you can use:
Method 01) Always pour from 1st jug to 2nd jug
- Fill the m liter jug and empty it into the n liter jug.
- When the m liter jug becomes empty refill it.
- When the n-liter jug becomes full, empty it.
- Repeat the above steps till any one of the jugs contains the required amount of water in them.
Method 02) Always pour from 2nd jug to 1st jug
- Fill the n-liter jug and empty it into the m-liter jug.
- When the n liter jug becomes empty refill it.
- When the m liter jug becomes full, empty it.
- Repeat the above steps till any of the jugs contain the required amount of water in them.
Method 03) Using BFS(Breadth First Search)
In this method, we use a queue and a map to find the solution. In the beginning, we initialize it with zero as both the jugs are empty. We then keep applying the above operations that are permitted to us and find the possible scenarios to find the targeted amount of water in the jugs.
Also, we keep maintaining an empty matrix to keep a track of the positions or states that we have encountered. In this way, the space complexity reduces manifolds and the efficiency of the program continuously improves.
Code Implementation with C++
Here is the C++ code to solve the Water Jug Problem:
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> p; void printPath(map<p, p> mp, p u) { if (u.first == 0 && u.second == 0) { cout << 0 << " " << 0 << endl; return; } printPath(mp, mp[u]); cout << u.first << " " << u.second << endl; } void BFSSolution(int x, int y, int target) { map<p, int> m; bool isSolvable = false; map<p, p> mp; queue<p> q; q.push(make_pair(0, 0)); while (!q.empty()) { auto u = q.front(); q.pop(); if (m[u] == 1) continue; if ((u.first > x || u.second > y || u.first < 0 || u.second < 0)) continue; m[{ u.first, u.second }] = 1; if (u.first == target || u.second == target) { isSolvable = true; printPath(mp, u); if (u.first == target) { if (u.second != 0) cout << u.first << " " << 0 << endl; } else { if (u.first != 0) cout << 0 << " " << u.second << endl; } return; } //Filling the 2nd jug completely if (m[{ u.first, y }] != 1) { q.push({ u.first, y }); mp[{ u.first, y }] = u; } //Filling the 1st jug completely if (m[{ x, u.second }] != 1) { q.push({ x, u.second }); mp[{ x, u.second }] = u; } //Transferring contents of 1st Jug to 2nd Jug int d = y - u.second; if (u.first >= d) { int c = u.first - d; if (m[{ c, y }] != 1) { q.push({ c, y }); mp[{ c, y }] = u; } } else { int c = u.first + u.second; if (m[{ 0, c }] != 1) { q.push({ 0, c }); mp[{ 0, c }] = u; } } //Transferring content of 2nd jug to 1st jug d = x - u.first; if (u.second >= d) { int c = u.second - d; if (m[{ x, c }] != 1) { q.push({ x, c }); mp[{ x, c }] = u; } } else { int c = u.first + u.second; if (m[{ c, 0 }] != 1) { q.push({ c, 0 }); mp[{ c, 0 }] = u; } } //Emptying 2nd Jug if (m[{ u.first, 0 }] != 1) { q.push({ u.first, 0 }); mp[{ u.first, 0 }] = u; } //Emptying 1st jug if (m[{ 0, u.second }] != 1) { q.push({ 0, u.second }); mp[{ 0, u.second }] = u; } } if (!isSolvable) cout << "Solution not possible"; } int main() { int Jug1 = 4, Jug2 = 3, target = 2; cout << "Path from initial state " "to solution state ::\n"; BFSSolution(Jug1, Jug2, target); return 0; }
Code Implementation with Java
Here is the Java code to solve this problem:
import java.util.*; class Pair { int a, b; List path; Pair(int a, int b) { this.a = a; this.b = b; path = new ArrayList<>(); } Pair(int a, int b, List _path) { this.a = a; this.b = b; path = new ArrayList<>(); path.addAll(_path); path.add(new Pair(this.a, this.b)); } } public class Solution { public static void main(String[] args) throws java.lang.Exception { int x = 4; int y = 3; int target = 2; getPath(x, y, target); } private static void getPath(int x, int y, int target) { boolean[][] visited = new boolean[x + 1][y + 1]; Queue queue = new LinkedList<>(); //Since both jugs are empty, hence initializing with 0 Pair initialState = new Pair(0, 0); initialState.path.add(new Pair(0, 0)); queue.offer(initialState); while (!queue.isEmpty()) { Pair curr = queue.poll();
if (curr.a > x || curr.b > y || visited[curr.a][curr.b]) continue; //Marking current jugs as visited
visited[curr.a][curr.b] = true; if (curr.a == target || curr.b == target) { if (curr.a== target) { curr.path.add(new Pair(curr.a, 0)); } else { curr.path.add(new Pair(0, curr.b)); } int n = curr.path.size(); System.out.println( "Path of states of jugs followed is :"); for (int i = 0; i < n; i++) System.out.println( curr.path.get(i).a + " , " + curr.path.get(i).b); return; } queue.offer(new Pair(x, 0, curr.path)); queue.offer(new Pair(0, y, curr.path)); queue.offer(new Pair(x, curr.b, curr.path)); queue.offer(new Pair(curr.a, y, curr.path)); queue.offer(new Pair(0, curr.b, curr.path)); queue.offer(new Pair(curr.a, 0, curr.path)); int emptyJug = y - curr.b; int amountTransferred = Math.min(curr.a, emptyJug); int b = curr.b + amountTransferred; int a = curr.a - amountTransferred; queue.offer(new Pair(a, b, curr.path)); // Tranferring water from jug2 to jug1 emptyJug = x - curr.a; amountTransferred = Math.min(curr.b, emptyJug); b = curr.b - amountTransferred; a = curr.a + amountTransferred; queue.offer(new Pair(a, b, curr.path)); } System.out.println("Solution not possible! "); } }
Code Implementation with Python
Here is the Python code to solve the Water Jug Problem:
from collections import deque def Solution(a, b, target): m = {} isSolvable = False path = [] q = deque() #Initializing with jugs being empty q.append((0, 0)) while (len(q) > 0): # Current state u = q.popleft() if ((u[0], u[1]) in m): continue if ((u[0] > a or u[1] > b or u[0] < 0 or u[1] < 0)): continue path.append([u[0], u[1]]) m[(u[0], u[1])] = 1 if (u[0] == target or u[1] == target): isSolvable = True if (u[0] == target): if (u[1] != 0): path.append([u[0], 0]) else: if (u[0] != 0): path.append([0, u[1]]) sz = len(path) for i in range(sz): print("(", path[i][0], ",", path[i][1], ")") break
q.append([u[0], b]) # Fill Jug2 q.append([a, u[1]]) # Fill Jug1 for ap in range(max(a, b) + 1): c = u[0] + ap d = u[1] - ap if (c == a or (d == 0 and d >= 0)): q.append([c, d]) c = u[0] - ap d = u[1] + ap if ((c == 0 and c >= 0) or d == b): q.append([c, d]) q.append([a, 0]) q.append([0, b]) if (not isSolvable): print("Solution not possible") if __name__ == '__main__': Jug1, Jug2, target = 4, 3, 2 print("Path from initial state " "to solution state ::") Solution(Jug1, Jug2, target)
Output:
Path of states by jugs followed is : 0 , 0 0 , 3 3 , 0 3 , 3 4 , 2 0 , 2
Complexity Analysis
Time Complexity for the solution will be O(n*m) and the Space Complexity for it will be O(n*m).
Conclusion
After reading the above tech blog, it is certain that you must have understood the Water Jug problem and the approaches with which it can be solved. It is funny how a riddle can be asked in an interview, but as mentioned in the introduction of this blog, hiring trends are continuously evolving. So, you need to keep up with the world.
FavTutor's tech blogs are one of the best ways you can understand and approach the problem by actually learning the intuition behind the problem.
