@Don: Could you please explain ur tree approach with an example?
Thanks Doom On Tuesday, 3 April 2012 02:52:17 UTC+5:30, Don wrote: > > I did that by building a tree in which each node stores the > configuration, including number of steps to that point, amount of > water in each bucket, and a pointer to the parent, sibling, and > leftmost child. Start out with one node with stepCount set to zero and > all the buckets empty. You want the solution with the least number of > steps, so use a breadth-first search. For each node, create a list of > children based on the following: > > 1. For each bucket which is not full, fill it > 2. For each bucket which is not empty, empty it > 3. For each pair of buckets A and B where A is not empty and B is not > full, pour A into B > > When you find a bucket with the desired amount of water, you can trace > back through the parent pointers to get the series of moves required > to get there. > > If you just need the minimum number of steps, the problem is much > easier. Just use a 99x99x99 table D[99][99][99]. If the bucket > capacities are a,b,c, start with all table values set to a large value > except > > D[a][0][0] = D[0][b][0] = D[0][0][c] = 1 > > Then iteratively start with all states with depth d and set all states > which can be reached from that state by a single step to d+1 if their > current depth is greater than d+1. You'll end up with a table of all > states reachable with the set of buckets, and the minimum number of > steps to reach each state. > > Don > > > On Apr 1, 12:57 pm, bharat b <bagana.bharatku...@gmail.com> 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/-/WfsTfRIQ0dIJ. 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.
