A common puzzle asked during interviews is how to measure 4 liters of
water with just two uneven shaped buckets, one of 3 liter another of 5
liter, in minimum number of steps. To extend and generalize this, write a
program to evaluate the minimum number of steps to measure “X” liters of
water, with “Y” buckets each having a separate denomination. The
assumptions and sample input/output as given below:
*Assumptions:*
* *
1. Each bucket used for measuring water should be unique in
denomination and the number of buckets will be <= 3
2. The target amount to be reached has to finally reside in a
single bucket (at the end of the measuring activity).
3. The bucket capacities and target amount will be <= 99
4. If there are multiple ways to measure the same amount, only
one way, having the minimum number of steps, has to be shown in
the output.
If there are multiple minimum steps solutions present, displaying one
solution should be enough.
5. The console input as well as the output should be in single
line and in the format shown below.
6. You can assume (not mandatory) minimum 2 steps will be
required. You can ignore the cases where solution can be
achieved in single
step.
7. You can assume that maximum 10 steps will be required to reach
the target amount. If any solution requires more than 10 steps
to reach the
target amount, you can stop the calculation and ignore that test case.
*Input Format:*
The input will be of the following comma separated format – No. of
buckets, capacity of bucket 1, capacity of bucket 2, …, Target amount
desired. The following examples will provide more clarity
*Sl. No.*
*Input string*
*Explanation*
1
2,3,5,4
Implies that there are 2 buckets of capacity 3 and 5 lts each and the
target amount desired is 4 lts.
2
3,4,6,9,7
Implies that there are 3 buckets of capacity 4, 6 and 9 lts each and the
target amount desired is 7 lts.
.
*Output Format:*
Each step should be a 11 bytes field left aligned & right padded with
spaces along with the right boundary as “|”. Together “|” character the
length should be 12 characters. The following examples will provide more
clarity
*Sl. No.*
*Input string*
*Expected Output String*
1
2,3,5,4
Fill 2 |Move 2 to 1|Empty 1 |Move 2 to 1|Fill 2 |Move 2 to 1|
2
3,4,6,9,7
Fill 1 |Move 1 to 2|Fill 3 |Move 3 to 2|
* *
*Let’s explain 1**st** output sample in more detail*: As explained
earlier, effectively the input 2,3,5,4 means there are 2 buckets of
capacity 3 liter and 5 liter and using these two buckets we have to measure
4 liter (which is the target).
The answer is: Fill 2 |Move 2 to 1|Empty 1 |Move 2 to 1|Fill
2 |Move 2 to 1|
Let’s explain the answer also for test case 1:
*Step #*
*Step Description*
*Status of 3 liter bucket (Bucket 1)*
*Status of 5 liter bucket (Bucket 2)*
*Explanation*
Step 1
Fill 2
0
5 liter
We are filling the 2nd bucket
Step 2
Move 2 to 1
3 liter
2 liter
Moving the liquid from bucket 2 to bucket 1. As Bucket 1 can take 2
liter. So, after moving Bucket 1 will contain 2 liter and
remaining 3 liter
will be in bucket 2.
Step 3
Empty 1
0
2 liter
We have emptied the 1st bucket (Bucket 1).
Step 4
Move 2 to 1
2 liter
0
Moved all the liquid which was in bucket 2 to bucket 1 (i.e. 2 liter)
Step 5
Fill 2
2 liter
5 liter
Filled the 2nd bucket (5 liter)
Step 6
Move 2 to 1
3 liter
4 liter
If we try to move the liquid from bucket 2 to 1, then if we fill bucket
1, 1 liter liquid will be reduced from bucket 2, as a result
Bucket 2 will
contain (5-1)=4 liter . We achieved the target.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
