http://www.cut-the-knot.org/wgraph.shtml
Every distribution of wine in the three jugs A, B, and C, can be described by the quantities b and c of wine in the jugs B and C, respectively. Thus every possible distribution of wine is described by a pair(b, c). Initially b=c=0 so that one starts with the distribution (0, 0). The target distribution is obviously(4, 0). puz <http://www.cut-the-knot.org/do_you_know/graphs2.shtml#puz(G)>(WaterPuzzle) in this case consists of all integer pairs (b,c) connected by edges wherever it's possible to move from one node to another by pouring wine between the jugs. Thus, from (0, 0) we can move to (5, 0) and (0, 3). From (5, 0) it's possible to move back to (0, 0) but also to (2, 3) by pouring from B to C and to (5, 3) by pouring from A to C. Continuing in this manner we'll discover that the nodes of the graph corresponding to the feasible configurations of wine are located on the perimeter of the 6x4 rectangle in the first quadrant. (Why?) On the diagram I only showed some of the edges. In particular, there is a walk <http://www.cut-the-knot.org/do_you_know/graphs.shtml#walk> from the starting node (0, 0) to the target node (4, 0),viz. (0,0)(A->B)(5,0)(B->C)(2,3)(C->A)(2,0)(B->C)(0,2)(A->B)(5,2)(B->C)(4,3) (C->A)(4,0) On Sunday, 1 April 2012 23:27:17 UTC+5:30, bharat wrote: > > > 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/fOl0tV5QsooJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
