Countdown Plus!

[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

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+(45)))) = 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.  

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

 

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

 

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

 

bulletOptimization

 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:
bulletThe addition of postfix evaluation (the original version built  fully parenthesized expression strings with embedded operators and values and evaluated the string.  
bulletConverting 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.   
bulletLimiting 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!      

 

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

 

bulletGenerating 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 

bulletDownload source
bulletDownload  executable

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: February 18, 2016

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