[Home] [Puzzles & Projects] [Delphi Techniques] [Math Topics] [Library] [Utilities]
Insert +(addition) or × (multiplication) operators as required into the string of digits 123456789 to form
an expression that evaluates to 2002.
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.
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.
|Browse source code extract|
|Download 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.)|
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
Please enumerate all solutions (if any) to A General Year 2002 Arithmetic Puzzle (of unknown origin):
|Original: October 28, 2002||
Modified: November 07, 2008
Copyright © 2000-2013, Gary Darby
All rights reserved.