Expressions 2002

[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

Insert +(addition) or × (multiplication) operators as required into the string of digits 123456789 to form an expression that evaluates to 2002.

Integers 1 Through 9 must appear in increasing order. Integers used in the expression  may be a concatenation of digits. Assume, as usual, that multiplications are performed before additions.

For example, if the desired value were 100,  then one  solution would be 1×2×3×4+5+6+7×8+9=100.

Background & Techniques

This program was prompted by a user request.    It is similar to the Expressions100 program which requires insertion of + and - signs into the string 123456789 to form an expression which evaluates to 100.     

The approach used there also works here with a few interesting modifications  Here, as in Expressions100,  I treat  the 8 spaces between the digits as "buckets" into which we'll insert either  '+', '×' , or nothing.  So we have 3 choices for each of 8 positions. That's only 38 -1 (6581) possible solutions; hard for humans, trivial for computers.

If we let 0 represent concatenation of digits, 1 represent '+' , and 2 represent '×' then the base 3 numbers from 00000000 to 22222222, cover all possibilities.   Function Power calculates  38 and  procedure  ConvertBase  converts numbers in that range  to base three for us.   Each these numbers represents an expression so, for example,  base 3 number  01201201 represents the expression 12+3x45+6x78+9.  

The new wrinkle this time is the precedence difference between + and x; multiplications must be performed before additions.   So here's a chance to view the world's simplest expression evaluator inn action. 

Stacks

A stack is a list of items typically accessed on a Last -in, First-out  (LIFO) basis.    Items are added to one end of the stack and removed from the same end.   Usually this is pictured as "push down" list which adds and removes from the top of the list with Push and Pop operations. But heck, I see no reason that the bottom won't work just as well. 

In this implementation, we just add and remove items from the end of an array - fast and simple, about 15 lines of code define the array, the count and the Push and Pop routines..

 

A full expression operator using stacks deserves its own topic page, but for expressions restricted to + and × it's not too bad.     We'll process each operation string (e.g.  01201201) from left to right.   We concatenate digits as the concatenation operations (0's)  are encountered.    When we encounter a 1 (+) or 2 (×) operation, if the preceding operation was + we just push  the number that is between the two operations, NextNum, onto the stack (see sidebar).   If the preceding operation was ×, we'll pop the top entry off of the stack, multiply it by NextNum and push the result back onto the stack.    When all 8 operations have been processed, stack items are the terms that must be summed  to get the value of the expression.    There are about 30 lines of Delphi code in this evaluate loop.     I think the code could be cleaner, but it  works so the maxim "If it ain't broke, don't fix it" seems to apply.  

 

 Running/Exploring the Program 

bulletBrowse source code extract
bulletDownload Source
bulletDownload executable  (Not much need for this unless you just really want to see the two solutions - or want to check solutions for some other year.)

Suggestions for Further Explorations

Bruce also sent this email with what looks like a  much harder version of the problem:

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.
 
Original: October 28, 2002

Modified: May 11, 2018

 

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