A Measuring Cups Problem

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

 

Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

 

Problem Description

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.   

 

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2016, Gary Darby    All rights reserved.