### 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.

Mensa® Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

(Hint: If you can wait, current year calendars are usually on sale in January.)

### Contact

 Search DelphiForFun.org only

### Problem Description

Given a set of integers and a target value, this program constructs all possible expressions using the given integers, the operators '+', '-', '*', and '/' together with parentheses to find  those which evaluate to the target value.

### Background & Techniques

This puzzle from our page-a-day "Brain Game" calendar prompted  today's puzzle.   I was sure that the key to solving it was to find the add, subtract, multiply, and divide operations which would covert the corner numbers to the one in the center.    Finding the expression is a matter of trial and error, at least for me.  And, since there are 6 ways to arrange the 3 terms and 16 ways to choose the two operators separating them, and two ways to parenthesize the expression, it may might takes as many as 191 "trial and errors" before finding the right one.    I find it much more enjoyable to teach my computer how to search and let it check all 192 expressions in a few microseconds.

If I'm lucky, there will be many more of these in the coming months and I can brag about all time I saved.  If you don't program and get tired of pencil and paper searching, you can use the program to find the answer to this or similar puzzles quickly.

Programmers can read on to see how our Library units provide the tools to parenthesize the expressions, permute the given values (without repeats),  permute the 4 operations (with repeats allowed),  and evaluate the expression strings we build.

### Programmer's Notes:

So the strategy for solving this problem is generate all possible expressions using the provided integers, the selected operators (up to 4 of these), and parentheses to control the order of evaluating the intermediate values.  Almost all of the tools we need are included in the DFF library although a couple of minor changes were made which we'll discuss below.  The tools are:

 UGetParens.pas: Contains procedure GetParens which takes an array of variable names and a token character to indicate operators between the variables and returns a list of expression "templates"  with parentheses inserted in all meaningful locations (no parentheses around single variables or the entire expression).  List Exp1List is built in our case.  UGetParens is used in a number of DFF programs and has been in my local library folder but was omitted from DFFLibV14 zip file.  It was added today (April 14, 2013), but is also included in the download for this program for this initial release. UComboV2.pas:  A longtime, frequently used container for the TComboSet class to generate  combinations and permutations of many types.  One of the smart things we did in this unit was to create an instance, Combos,  of the class when the unit is initialized.   In this, as in most cases,  the single pre-allocated  class is all that ise  needed.  A call to Combos.Setup tell it that we want to permute N of the N source integer values read, and a "While Combos.GetNext" returns the six ways to arrange the three values read for our problem ([1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]).  For each set returned, we run through the templates (Exp1List) returned by GetParens, and add insert the input value in the current index order into the templates and save them in a string list  Exp2List. So on the first time through the loop, the GetParens template "(a?a)?a" becomes "(3?12)?21"

When the loop ends and Exp2List is complete, a second call is made to Combos.setup is made to initialize a Combos.Getnext loop to select one less than the number of variables at a time from the 4 operations (assuming that they have all been selected) "with repeats" (so permutations can return multiple occurrences of a sign).    For each operation set returned, we run through all of the Exp1List entries, plugging in the current permutation of operations.  The firs time through the loop, the first Exp1List entry "(3?12)?21" becomes "(3+12)+21".   Resulting expressions are are saved in TrialsList string list.

 Finally we are ready to find out if we have any winners.  Unit Parser10 contains a TPasrser class which can evaluate complex expressions including powers, roots, trig function, logarithms, etc.  so should have no trouble with our simple expressions.  In fact, there is, or was, a slight problem with "Divide by zero" exceptions produced when we test expressions like  12/(3/21) using integer division where fractional results are ignored.  In theory, I should be able to intercept and ignore these errors but after a couple of hours working on it without success, I added a new operation "DIVZ" to the operations that TParser knows how to handle.  DIVZ checks for a zero denominator and returns 0 rather than produce the exception.  Not exactly correct, but works around the problem for now. One final note, I also made a slight change to procedure SetMemoMargins in library unit DFFUtils.  It now calls procedure ReformatMemo after the margins have been changed since this will typically be required anyway.

So, all in all, another problem solved.  Now I'm hoping for many more of the same type in the coming months to further exercise this "brain extender" program!

Addendum July 29, 2014:

Version 2  adds an extended version of the original puzzle.  This one has multiple completed input figures and a single target figure with one value missing.   The strategy for this one is to find  an single expression template which will evaluate to the number position containing the  "?".  The same value positions and operations applied in the same order for each figure must equal the value in the "?" position for that figure.  The successful template when applied to the incomplete figure will provide the required value.

Another puzzle programming exercise from my favorite source: the   Mensa Puzzle-A-Day Calendar.

### Running/Exploring the Program

 Download  executable Download source  (Note:  Library file DFFVLIB13 or later is required to recompile this program.  The three library changes  (UGetParens added, Parser10, and DFFUtils changed) for this program have been included in this download and in DFFLibV14 ) Download current library file (DFFLibV15) .

### Suggestions for Further Explorations

 Procedure GetParens could be expanded using the techniques of this program to insert the operators as well as variable values in the parenthesized strings and return completed  expressions.

 Original:  April 14, 2013 Modified:  July 29, 2017