[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
Here's a program that solves those problems like "given a cup that will hold 4 fluid ounces and one that will hold 11 fluid ounces, describe how to measure 6 fluid ounces" . Of course, in the computer version we might as well let the user choose the cup volumes and list the moves to obtain all feasible amounts.
Background & Techniques
This is another graph searching problem. Given cups with capacities C1 and C2, the corners of the graph are all possible integer pairs ranging from (0,0) to (C1,C2). Limiting the maximum cup capacity to 20 will restrict the search space to 400 or less such pairs, a reasonable number for exhaustive search.
I created a TCup (ha!) object to associate with each integer pair. It contains a Visited flag identifying that this node has been checked, and a TStringList object (named Path) to hold the moves that led to this node.
A doubly dimensioned State array holds the TCup objects. An example of multiple dimensioned dynamic arrays. Nodes are checked in sequence and for each one that has a path to it, the adjacent unvisited states (reachable in one more move) are created. I identified about half a dozen possible moves (empty cup A, fill Cup A, Pour A into B and the converse steps starting with cup B). Each time we find a move, we mark it as visited and fill in its path as the current path with the current move appended. This all happens in the MakeMove routine;
Successive passes are made through state array until we make a pass without changing anything.
When that's done, we fill in a Possibles array with the shortest paths found that produced each of the potential target values from 1 to C1+C2.
A TListBox displays solutions found and selecting one of those displays the detail of moves required to obtain it in a second TListBox .
I got slightly adventurous and tried the OnOwnerDraw exit to display representations of the cups and their liquid levels with the move list descriptions. See what you think.
I wrote a more complicated version with a breadth first search, but surprisingly the results were the identical to the results from this version. It's not immediately obvious why this is so - perhaps every non-optimum solution contains loops - but I'll accept it. The simpler the better. Let's call it a conjecture for now. If anyone finds a solution shorter than one the program provides, please let me know.
Addendum - After writing the above, I found a few cases where breadth-first did indeed produce shorter paths - for example measuring 2 with cup capacities of 1 and 3. As a result, I reinstalled the breadth-first option here. The only change required is to be sure that paths are built from shortest to longest. As an alternative to sorting by path length, a FindShortest function simply searches the State array and returns the shortest path not previously returned. A new Boolean Checked flag was added to TCup to enable this test.
A second conjecture (unproven at least by me), is that if the two cup volumes are relatively prime (have no common divisor), all possible volumes from 1 to C1+C2 can be obtained.
Running/Exploring the Program
Suggestions for Further Explorations
The program could be modified to allow user play.....with a hint button, best score info., random cup size and target generation, etc. Levels of play (easy, medium, hard) could be introduced based on number of moves required to solve, which the program already knows.
More than two cups might be an interesting variation.
Copyright © 2000-2017, Gary Darby All rights reserved.