There is a certain class of puzzle wherin one is provided with an ordered list of numbers, and is asked what arithmetic operators (+ − × ÷) fit between adjacent pairs of them such that, when the whole is evaluated as an expression, the result is some other given number. Example:
4 ? 10 ? 5 ? 7 ? 3 = 2
That is, how can you replace the question marks with operators such that the resulting equation is true? One possible answer (I suppose there may be more than one):
4 + 10 ÷ 5 − 7 + 3 = 2
I have a few questions about these:
[ol]
[li]What is this type of puzzle called?[/li][li]Is there some algorithmic way of solving them, other than brute search through every possible combination of operators?[/li][li]If one must brute search, is there some heuristic one can apply which tends to find the correct answer(s) faster?[/li][/ol]
Something is missing here. This seems to depend entirely on what rules are set for order of evaluation, and none are mentioned here. In most computer languages, this would evaluate as follows:
(4 + 10) ÷ ((5 − 7) + 3) = 2 which equals 14, not 2.
I think you got the precedences round the wrong way. Most programming languages and scientific calculators would do the division first, and evaluate it as ((4 + (10 ÷ 5)) − 7) + 3, which does equal 2. Really basic calculators might evaluate it as (((4 + 10) ÷ 5) − 7) + 3, which equals -1.2.
Most computer languages don’t use ÷ as an operator. Almost all computer languages use / for division, and, following the standard practice in mathematics, assign it a higher precedence than addition and subtraction. The only notable exception I can think of is APL, which does indeed use ÷ as the division operator, but assigns it the same order of precedence as every other operator and evaluates (IIRC) right to left, which means the expression would evaluate to
(4 + (10 ÷ (5 − (7 + 3)))) = 2
I would be very curious indeed to learn of any programming language which gave division lower precedence than addition and subtraction.
Actually, APL would do something even more fun than what you said.
[background for non-APL folks]
APL has about 40 native operators and no precedence could ever be sensibly defined across all of them. So they did away with the concept of precedence all together.
[/background for non-APL folks]
Every line in a program is an expression evaluated strictly from right to left. If the leftmost items are a variable and the assignment operator (a left-pointing arrow like ←), then the result is stored in the variable. If not, the result is output to the console screen.
So the line
A←4 + 10 ÷ 5 − 7 + 3
would be evaluated as compute (4 + (10 ÷ (5 − (7 + 3)))) and store the result in variable A. That result would be 2.
The line
4 + 10 ÷ 5 − 7 + 3 = 2
would be evaluated as compute (4 + (10 ÷ (5 − (7 + (3=2))))) and output the result to the screen. 3=2 evaluates to false which is zero, then the rest of the calculation gives a result of -1.
The line
2 = 4 + 10 ÷ 5 − 7 + 3
would be evaluated as compute (2 = (4 + (10 ÷ (5 − (7 + 3))))) and output the result to the screen. The (4 + …) part evaluates to 2, and so the final leftmost evaluation is (2=(2)) which evaluates to true which is 1.
No idea about a heuristic, just a little computation about the brute force:
if you have n numbers, then you must assign (n-1) operations. You have to place the parentheses which is equivalent to choosing an order for the operations: this gives you (n-1)!
And you have to choose, for which operation, wether it is a +, a -, etc… this gives you 4^(n-1) choices.
So, in the end, the complexity of the brute force is:
4^(n-1) * (n-1)!
… or about 2.6 billons possibilities for 9 numbers.
Here is the correct calculation for the maximum number of distinct different expressions possible for n numbers. It’s the product of the following two numbers:
4[sup]n-1[/sup]. Four operators in n-1 different places.
The nth Catalan number (2nd application). See the article for the expresion.
My stab at solving it: Dynamic programming. Let N[i,j] be the set of all numbers that can be generated from the ith thru jth integer in the sequence. Initialize with N[i,i] containing the ith number. Generate N[i,k] from (each element in N[i,j]) op (each element in N[j+1,k]) for all ops and j from i to k-1. Look in N[1,n] for the answer. Superficially just a few loops, but the blow up of the size of the sets makes it exponential time in the worst case. The hope would be that the number of elements stays kinda low due to duplicates. And whatever you do, check that you’re not dividing by zero!
It is trivially NP-Complete using just + and - due to the obvious reduction via Subset sum.