Ninja and Vessels

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
9 upvotes
Asked in company
Codenation

Problem statement

Ninja has been given two vessels, one is of ‘M’ liters and the other is of ‘N’ liters. Initially, both of the vessels are empty. These vessels do not have any marking that allows measuring smaller quantities. Ninja has to use these vessels to measure ‘W’ liters of water.

Can you help Ninja to measure ‘W’ liters of water in a minimum number of steps?

Note:

1) State (‘X’, ‘Y’) represents that the first vessel has  ‘X’ liters of water and the second vessel has ‘Y’ liters of water.

2) If it is impossible to measure ‘W’ amount of water using the given two vessels then return -1.

You can use the following operations to measure ‘W’ liters of water:

1) You can empty a vessel i.e. move from (‘X’, ‘Y’) to (0, ‘Y’) or (‘X’, 0).

2) Fill a vessel (‘X’, ‘Y’) to its maximum capacity i.e. (‘M’, ‘Y’) or ( ‘X’, ‘N’).

3) Pouring water from one vessel to another until one of the vessels is either empty or full i.emove from (‘X’, ‘Y’) to (min(‘X’ + ‘Y’, ‘M’ ), max(0, ‘X’ + ‘Y’ - ‘M’) or (max(0, ‘X’ + ‘Y’ - ‘N’), min(‘X’ + ‘Y’ , ‘N’).
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains an integer ‘T’ which denotes the number of test cases. 

The first and the only line of each test case contains three space-separated integers ‘M’, ‘N’, and ‘W’ where ‘M’ represents the capacity of water the first vessel can store, ‘N’  represents the capacity of water the first vessel can store and ‘W’ represents the amount of water you have to measure.
Output Format : 
For each test case, return the minimum number of steps required to measure the ‘W’ amount of water.

Print the output of each test case in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= ‘T’ <= 100
1 <= ‘M’, ‘N’ <= 5000
1 <= ‘W’ <= max(‘M’, ‘N’)

Time Limit: 1 sec
Sample Input 1:
2
5 3 2
4 4 4
Sample Output 1:
2
1

Explanation for Sample Output 1:

In test case 1, First, we fill water in vessel one i.e (5, 0).

Then transfer water from vessel one to vessel two i.e. (2, 3). So, we have ‘W’ = 2 liters of water in the first vessel in the minimum number of steps.

In test case 2, we can fill water in either of the vessels because both the vessels are of the same size. So, we will fill water in vessel one i.e. (4,0) which gives us the desired liters of water i.e ‘W’ = 4 in the minimum number of steps.
Sample Input 2:
2
5 10 3
3 4 2
Sample Output 2:
-1
 4

Explanation for Sample Output 2:

In test case 1, we can not measure 3 liters of water by using vessels of capacities 5 liters and 10 liters, respectively.

In test case 2, first, we fill water in the first vessel i.e (3, 0).

In the next step, transfer all water from the first vessel to the second vessel i.e (0, 3).

In the third step, fill water in the first vessel i.e (3, 3). 

Finally, transfer 1-liter water from the first vessel to the second vessel i.e (2, 4). This gives us the desired liters of water i.e ‘W’ = 2 in the first vessel in the minimum number of steps.
Hint

Think of breadth-first search.

Approaches (1)
Breadth first search

As we know we can perform one of the three operations at a time, so we can use the breadth-first search algorithm to find the minimum number of steps required to measure ‘W’ liters of water.

 

The steps are as follows:

 

  1. We declare a queue ‘VESSEL_STATES’ in which we store the current state of the two vessels.
  2. We declare a map ‘VISITIED_STATES’ in which we store if the current state is visited or not.
  3. First, we add (0,0) state into the ‘VESSEL_STATES’ because we know initially both the vessels are empty.
  4. We run a loop while the ‘VESSEL_STATES’ is not empty:
    • Remove the front element of the ‘VESSEL_STATES’ and store it in a variable ‘CURR_STATE’.
    • If ‘CURR_STATE’ is present in ‘VISITIED_STATES’
      • Continue.
    • Else add this state in ‘VISITIED_STATES’.
    • If ‘CURR_STATE’ is the required state i.e ‘CURR_STATE.X’ == ‘W’ or ‘CURR_STATE.Y’ == ‘W’
      • Return ‘CURR_STATE.STEPS’.
    • Perform all of the given operations on the ‘CURR_STATE’  and add it in ‘VESSEL_STATES’:
      • We can empty a vessel:
        • ‘VESSEL_STATES.add(0, ‘CURR_STATE.Y’, ‘CURR_STATE.STEPS’ + 1).
        • ‘VESSEL_STATES.add(‘CURR_STATE.X’, 0, ‘CURR_STATE.STEPS’ + 1).
      • We can fill a vessel to its maximum capacity:
        • ‘VESSEL_STATES.add(‘M’, ‘CURR_STATE.Y’, ‘CURR_STATE.STEPS’ + 1).
        • ‘VESSEL_STATES.add(‘CURR_STATE.X’, ‘N’, ‘CURR_STATE.STEPS’ + 1).
      • We can pour water from one vessel to another until one of the vessels is either empty or full:
        • ‘VESSEL_STATES.add(min(‘CURR_STATE.X’ + ‘CURR_STATE.Y’,’M’), max(0, ‘CURR_STATE.X’ + ‘CURR_STATE.Y’ - ‘M’), ‘CURR_STATE.STEPS’ + 1).
        • ‘VESSEL_STATES.add(max(0, ‘CURR_STATE.X’ + ‘CURR_STATE.Y’ - ’N’), min(‘CURR_STATE.X’ + ‘CURR_STATE.Y’ , ‘N’), ‘CURR_STATE.STEPS’ + 1).
  5. If ‘VESSEL_STATES’ gets empty i.e we could not measure the ‘W’ liters with the help of these two vessels then return -1.
Time Complexity

O(M + N),  Where ‘M’ represents the capacity of water the first vessel can store, ‘N’  represents the capacity of water the first vessel can store.

 

Since at every state we can perform three operations. So we perform all of these operations and store them into ‘VESSEL_STATES’. There are at most (2 * M + 2 * N) states so, the overall time complexity is O(M + N).

 

For example, if ‘M’ = 1 and ‘N’ = 5 then we have the following possible states [(0, 0) (1, 0) (0, 1) (1, 1) (0, 2) (1, 2) (0, 3) (1, 3) (0, 4) (1, 4) (0, 5) (1, 5)]. 

Space Complexity

O(M + N), Where ‘M’ represents the capacity of water the first vessel can store, ‘N’  represents the capacity of water the first vessel can store.

 

Since at every state we can perform three operations. We perform all of these operations and store them into ‘VESSEL_STATES’ and if the ‘CURR_STATE’ is unique then we store it in ‘VISITIED_STATES’. In the worst-case scenario, we have (2 * M + 2 * N) new states. So, the overall space complexity is O(M + N).

Code Solution
(100% EXP penalty)
Ninja and Vessels
Full screen
Console