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 6 randomly select integers and a
target value, use parentheses and the four common arithmetic
operators (+, -, x, and ÷) to
build an expression whose value is as close as possible to the
target. If the target can be matched exactly in more
than one way, then fewer values used is better.
Example:
| Values |
Target |
| 8 |
3 |
2 |
10 |
5 |
4 |
538 |
| |
|
|
|
|
|
|
| Solution ( 1of 5):
10+(8×(3×(2+(4×5)))) = 538 |
|
Background & Techniques
This program is loosely based on a popular British television show,
Countdown. You can find a number of references on the web for more
information about the program itself. Input values are
semi-randomly selected by players on the TV program and the computer
selects a target value in the range of 101 to 999. Our version
relaxes some of the constraints of the TV show; any integer input and
target values may be selected, up to input 9 values may
be specified and some operators may be excluded.
These extensions allow the program to solve the following problem proposed
by a
viewer several months ago in response to our
Expressions 2002 program:
Thank you for your solution to the Year 2002
Arithmetic Puzzle.
Please enumerate all solutions (if any) to A General Year 2002 Arithmetic Puzzle
(of unknown origin):
a) Integers 1 through 9 are to be used exactly
once.
b) Parentheses are permitted.
c) Integers 1 through 9 are not necessarily in increasing sequence.
d) Integers used in the expression are not allowed to be a concatenation of
digits.
e) Only operators + and * are permitted between adjacent integers.
f) Develop an expression that yields the value 2002.
I added a "Use all values" option to force only
solutions using all input values to be displayed. I haven't done the
calculations, however a complete search with 9 operands and 2 operations
would take a long time. But the first few dozen solutions for 2002
(or 2003) are found in a few seconds.
By the way, the number of expressions tested is very large. The
number of different ways to parenthesize expressions of N variables
using binary operations has a name: Catalan numbers. There are
42 ways to write expressions with 6 variables and 5 operations.
There are 1430 ways to parenthesize expressions with 9 variables.
For each of these expression "templates", the N variables may be plugged in
in N! (N factorial) ways, and the M operations may be
substituted in M(N-1) ways. For example, with 3
variables there are 2 templates; 6, (3!), arrangements of input
values, and 16 , (42), arrangements of operators.
For the 6-value "Countdown" problem, there are over 30,000,000
potential expressions to check! The program displays run time and a
count of expressions checked at the end of each search.
Two buttons, "Generate1" and "Generate2" generate
random problems. Generate1 creates a problem with random
values and target for any selected number of variables. Generate2
creates a problem which follows the TV show rules as I understand them:
"Select 6 cards from a set of 24 cards consisting of two each with values
1-10, and the remaining four cards containing values 25,50,75,100:".
Non-programmers are welcome to read on, but may
want to skip to the bottom of this page to
download executable version of the program.
Notes for programmers:
There were several interesting problems to solve in this
project. The general strategy is to generate all possible parenthesized
expression templates of the required length as well as all arrangements of
operations and values and then apply them in a nested loop to evaluate
each expression and compare its value to the target value.
 | Generating all possible expression templates.
I started by generating all possible parenthesized expression
prototypes or templates based on the current number of
variables. This led to an interesting side trip
into Catalan numbers which is worth a separate Math Topics posting one
of these days.
A template record contains string E, a string version of the expression and a
Postfix, an array of integers which represent the postfix position of
the operators and values in the expression. Postfix notation,
also known as "reverse Polish" notation is the easiest way
to evaluate mathematical expressions because the operands physically precede
the operations, "a+b" becomes "ab+" , etc.
Neat stuff - if you haven't studied on it, you may want
to.
|
| Generating all possible arrangements of operations and input values. Our old faithful "Combos" unit is used to generate an
array of permutations of input values. For the 6 value
case there are 6 choices for the first number in the expression, 5
choices for the second, etc. or 6! (6x5x4x3x2x1) =720
arrangements.
Unlike the values, operations may be repeated several times in each
expression. In this case we need to generate sets of operations,
each set containing 1 less member than the number of values. Referring
to the 6 value case, 5 operations are required to connect the
values. Assuming than all four operations are selected, this leads to
4x4x4x4x4 (=1024) arrangements of
operations.
|
| Evaluating the expressions. Actual operators and values are kept separate from the expressions
and only plugged in a evaluation time. The templates are defined
in a TTemplate record which contains a string version of the
expression and a "Postfix" array defining instructions for
evaluating the expression. In this array, positive numbers are used
for value position indices and negative numbers for operations.
Thus the expression "v op (v op v)" in my postfix array would be:
"1,2,3,-2,-1". At evaluation
time, this says "push values 1,2, and 3 onto a stack , apply the
2nd operator to the two most recent values on the stack and replace
them with the result. Then apply the 1st operator to the two most
recent items on the stack and replace them with the result.
Since we are done, the remaining value on the stack is the final
result. Note that traditional stack descriptions
speak of a "stack" as a push down", "pop
up" data structure (like a stack of dishes) where items are
always added to and removed from the top of the stack. I
find it convenient to add and delete items from the tail end on an
array of items with the same effect.
|
| Optimization
A large part of the effort was spent optimizing the
search. The time for six value problems was reduced from
several minutes to 3.5 seconds on my 2.4ghz Pentium
system. Eliminating redundant operations is one
technique. In the six variable case this reduces the 30,000,000
potential expressions to less 15,000.000. For the commutative operations ('+' and 'x'), we can skip any
expression where the first operand is greater than the second, on the
assumption the we have already evaluated the version where he first
operand is smaller. Also before evaluating, we can
check that any divide operations between two input values divide
evenly. Both of these checks are made efficient by
adding an Optimize array to each template. Entries here
point to the first operand of a basic term in the Postfix
array. I.e. to the "a" in an "a b op"
structure. This lets us locate the terms to check without
rescanning Postfix.
Unfortunately, because postfix
evaluation is quite efficient, the time to determine that we do not
need to evaluate an expression takes nearly as long as the time to
evaluate it, so gains from this source were less than might be
expected; eliminating
50% of expression evaluations reduced run times by about
25%.
Largest gains came from:
 | The addition of postfix evaluation (the original version
built fully parenthesized expression strings with embedded operators
and values and evaluated the string. |
| Converting strings from dynamic
(huge) strings to fixed length strings where ever possible. Millions
of allocate/deallocate operations on dynamic strings add significantly to
run times. |
| Limiting the calls to application.processmessages within
evaluation loop. Eliminating a call for every evaluation and
calling only when operations change increased the processing rate
from 2.9 million to 4.4 million expressions
per second on the 2.4 ghz
machine! |
|
| Filtering duplicate solutions.
This is tougher than I would have thought. It is not
even clear what constitutes a duplicate. Is 4-(3-2) different
than 4+(2-3)? Probably not, but finding such identities is not
trivial. A fully expanded form of the expressions
with all parentheses removed and sorted to the extent possible by
operation and value should create a standard form that could be
retained in a list and used to check new solutions for
uniqueness. Unfortunately, I never got the "simplify &
standardize" procedure written. Fortunately, I don't
think it matters much, except for missing out on the satisfaction of
having done it.
The filtering performed tries to associate an operator with each
value position in the expression and only report a single solution for
each such association that is unique. Duplicate values in the
input are poorly recognized by this technique.
|
| Generating standard countdown games.
This was accomplished using a standard "card
shuffle" technique, a simple method for randomly selecting
M of N objects. A Cards array is initialized with the 24
card values (two each with values 1 through 10, and four card
containing values 25,50,75, and 100). Then we loop selecting card numbers from 1 to 24,
then 1 to 23, 1 to 22, 1 to 21, 1 to 20, and 1 to 19. Each time
we move the selected card value to the display area and move the last
card we could have selected to the card position that we did select,
effectively removing the selected card from the deck and reducing the
deck size by 1. |
All in all, an interesting and challenging project. Thanks
to the viewer who suggested it. I enjoyed it!
Addendum March 6,2005: While updating CountDown to include
a new version of the Combo unit (the object which creates
combinations and permutations for solution searches), I discovered a few
bugs involving large results which caused various overflow
conditions. Those were fixed today and a revised version
uploaded. As a test and "just for fun", I created
the first 10 expressions that evaluate to the current year (2005) using
all of the digits from 1 to 9.
Addendum March 28, 2005: An alert viewer found that
the input integers to Countdown problems were limited internally to
the range of -128 to +127, although cleverly, larger values were accepted
and displayed in the result as though everything was OK. It wasn't,
but it is now. Input values can now be in the range -999 to
+999 and target values in the range -9999 to +9999, for both to the user
and the program.
Running/Exploring the Program
Suggestions for Further Explorations
Is there a tricky algorithm for reducing the number of expressions to
be evaluated? I keep thinking that are are many duplicates generated
by the "brute force" procedure, and there should be a way to
take advantage of symmetry to reduce the number by at least half - but
every shortcut I tried eliminated some potentially unique
expression. Those darn non-commutative "-" and
"÷" operations keep spoiling things!
Recognizing duplicate solutions is a problem that
I haven't really solved. One problem area is the
presence of duplicate input values. Another is recognizing
that expressions which may appear quite different are probably the
same. (For example: a-b*(c-d) should probably be considered identical
to a+b*(d-c). My thought is to reduce every solution to a
standardized form that could be compared as a string to other
expressions. This would involve removing parentheses and somehow
sorting terms by value and
operation.
| Original Date: March 04,
2003 |
Modified:
May 11, 2018
|
|
|
