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 <[email protected]> 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 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.
