Search
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).
|
| |
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:
 | 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
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:
May 15, 2018
|
|
