Container Puzzle Algorithm: Measure 1-10 litres, given 3, 7, and 10 litre containers, with the largest being full of water.

0 / 873 Container Puzzle Solution:

Given three containers 3, 7, and 10 litres respectively with the largest being full of water, determine a method of measuring anything between 1 to 10 litres using these containers alone. If any quantity isn’t measurable deduce accordingly. Give solution as well as algorithm for the container puzzle.

This blog will also give an algorithm for solving this puzzle:

1)  Store initial state of containers with their capacity in an array, for e.g. [0,0,10] in this case.

2) From State S (0,0,10), determine all possible configurations achievable by transferring liquids between containers, checking each time, the liquid that the containers can hold further.

3) Store each state obtained after each transfer in a list for revisiting and discarding invalid states.

4) If any of the states obtained as a result of Step 2), are already in the global list or contain same 3 numbers (quantities), discard them.

5) Add valid state at each level to an N-Ary tree.

6) Some states could be exceptions and may not obey Rule #4. In that case, count the number of attempts in reaching next state. If that exceeds 4 (4 is the highest number of states that can be obtained by liquid transfers between 3 containers given the capacities in this case. We can have generic number of attempts before reevaluating which can be NP2  where N= number of containers), reevaluate/backtrack the states obtained at 4 and pick one of the states that gives a different next State Sn

7) Continue iterating and adding new states until the liquid quantity to be measured is reached. Terminate and add this state to the tree which will be the highest leaf of the tree.

Note:- A state S which will represent node of a tree can have a maximum of 4 children in this case as the number of containers is 3, say for e.g. S1,S2,S3,S4.  Consider and add only valid states out of these as children of that state S. An N-Ary tree is the best data structure suited for solving puzzles like this.

See the DEMO below which will print out the tree from initial to final state depending on the quantity entered for measurement.

From the output of this tree, it’s very easy to trace the route till the destination state and print it out. Read more about tree route tracing algorithm :- DEPTH OF AN N-ARY TREE AND FINDING ROUTE TO A NODE IN AN N-ARY TREE

Below is the complete code that runs the show behind the DEMO:-

Hope you enjoyed reading this. Subscribe to Golibrary for more interesting reads like this!!