Water Jug Puzzle - Tools and Tactics
I am sure that we have heard or played water jug puzzles before. There are several ways this problem is described. Generally, we would have 3 different sized water containers of some known/declared volumes (like 8 litre, 5 litre, and 3 litre). But none is calibrated, so we cannot measure 1 or 2 litre volumes. A common problem to solve is “given some amount of water in 1 jug or 2 jugs, divide that amount of water into 2 equal volumes by just pouring water from one jug to another - without spilling”.
Many variants of this problems can be found on the Internet (Search for “water jug puzzle”]. Most ask to divide the 8 liters/gallons into 2x4 liters/gallons, given 8, 5, 3 liters/gallons jugs. One a bit more difficult is “3 water jugs (19L, 13L and 7L), 19L is empty, others are full; target/wanted 2 jugs of water 10L each.” [see https://www.gotoknow.org/posts/545162 ].
Water pouring puzzle https://en.wikipedia.org/wiki/Water_pouring_puzzle has more about the puzzle.
Let us look at not the puzzle but the insights for solving such puzzle. We can draw up pictures to help us visualize. This is an implicit process of identifying ‘entities’ (or system variables). It is much the same as making sure we know what subjects and objects are when we speak a sentence.
We can focus on pouring as an operation or a function like let f(i, j ,w) to mean pouring amount w of water from jug i to jug j. Here we say what the ‘verb’ is and how this verb is performed.
But we need to track amount of water in each jug, so we know what is the next possible pouring. This is ‘monitor and review’. This is the result of our operations. A measurement of all things performed so far. It is called ‘state’ (or measurement of state) of the system .
The ‘state’ (of the system) tells us where we are. And in a ‘simple way’ we solve the puzzle with
Repeat: if we reached the goal state then we are done
else what are the next possible operations
choose one of these and perform it
We can now see how we solve a puzzle using ‘system’ concept and programming language as tools and tactics. Most of us already do this and are experienced in using this approach. But many do not realize that the key factors are the 'state' (or monitor and review) and the process (repeat until goal state).
To show how this done. (referring to https://www.gotoknow.org/posts/545162 ).
We write the state as a 3-tuple (a, b, c ) to say there is a amount in 19L jug, b amount in 13L jug and c amount in 7L jug. Now we express the puzzle in state terms:
Given/Initial state: (0, 13, 7) – 19L jug is empty, 13l and 7L jugs are full
Goal state: (10, 10, 0 ) -- there is only one possible goal state in this puzzle
And our process:
Repeat: until current state == (10, 10, 0 )
find a list of possible pouring [f(i, j, w)] ;
choose one f(i, j, w);
We should also see that we have now broken the puzzle into a set of entities, one simple action and one loop of actions with one control decision (when to finish). Within the loop we have an action to evaluate the current state and make a list of next possible moves, and another decision (called 'option') to choose an action from a list (of next possible). [The 'rule for possible' moves depends on the game/puzzle. The criterion for choosing the next move also depends on the game/puzzle.]
This is a powerful problem solving approach because it simplifies and structuralizes the problem. It divides control and responsibilities into hierarchical levels. And it allows operations at all levels to be specified and performed by various parties (machines, workers, managers,..).
Automation, manufacturing, administration, construction, … in the modern day are based on this system concept. Skills in system design and development are highly valued and sought after. So it pays to reflect on the this example.