Last Updated: 22 Feb, 2021

Ninja and Vessels

Moderate

Asked in company

Solve now

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’).

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

Solve now

Approaches

01 Approach

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:

We declare a queue ‘VESSEL_STATES’ in which we store the current state of the two vessels.
We declare a map ‘VISITIED_STATES’ in which we store if the current state is visited or not.
First, we add (0,0) state into the ‘VESSEL_STATES’ because we know initially both the vessels are empty.
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).
If ‘VESSEL_STATES’ gets empty i.e we could not measure the ‘W’ liters with the help of these two vessels then return -1.

Solve now