Expressions from Integers

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

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.

Mensa 365 Puzzlers  Calendar 2017

Mensa 365 Puzzlers Calendar 2018

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

Contact

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

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.          

Non-programmers are welcome to read on, but may want to jump to bottom of this page to download the executable program now.

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:

bulletUGetParens.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. 
bulletUComboV2.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.

bulletFinally 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.   
bulletOne 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 

bulletDownload  executable
bullet 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 )
bulletDownload 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

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