Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Given something like this:

1 5 3 4 = 18

I need to determine (using an algorithm) if there is a combination of operators and brackets that bring me to 18. Only "+" and "*" and "(" and ")" are allowed.

Example:

1 + 5 + ( 3 * 4 ) = 18

Beside brute force, is there any particular algorithm that is able to compute all the possible combo in reasonable time? RPN may help in order to encode the possible solutions, but the same are a lot (4^n ?).

share|improve this question
    
This is a question for math.stackexchange.com. But instinctively that looks NP-complete where n is the number of variables. –  user23157 May 16 '11 at 7:38
2  
@B Tyler: That's like saying the traveling salesman problem is a math problem, because it contains euclidean distances. Mathematically the problem is trivial: There's a finite number of possibilities, just try them out. The real problem is finding an efficient algorithm. That's CS, not math. –  nikie May 16 '11 at 7:42
    
@nikie There's nothing subjective about it. Maybe cstheory.stackexchange.com? –  Deckard May 16 '11 at 7:58
    
I can move it there, if it is hurting you too much ;-) –  incognita May 16 '11 at 8:02
2  
This is borderline on-topic for Programmers.SE, so I'm going to leave this open; but you might find more expert answers on other sites, like Math.SE or CSTheory.SE. However, I'm not confident they'll welcome the level of the question, so I'd ask on their meta discussion sites whether the question would be acceptable if you choose to go that route. –  user8 May 16 '11 at 8:03
show 2 more comments

3 Answers

Brute force is actually quite fast if you avoid pointless calculations.

In the worst case you have 2^(N-1) operators and N!(N-1)! ways of choosing the pairs of numbers for the N-1 operations. So for example, for N=4, this gives 1,152 possibilities.

But you can cut this down substabtially: if you are going to look at 6+2 and 6*2, then there is no need to look at 2+6 and 2*6: just do the bigger number first. This takes out a factor of 2^(N-1) bringing the number of possibilities down to N!(N-1)!, so 144 for N=4.

There are further possible savings as (20+6)+2 is the same as 20+(6+2), but I suspect this may not be worth optimising for until N becomes large. Another is that multiplication by 1 does not help much: this kind of thing may not be a saving with N=4, but could be if you were also for example looking at division (especially if the smaller number is not a factor or divisor of the larger number) as you can then remove a bunch of possibilities. rzzzwilson's suggestion of stopping when the target is exceeded works in a similar way, though only works if the all the operations are non-decreasing (i.e addition and multiplication but not subtraction or division)

As an illustration of something similar, try my old Java applet here, with six numbers and four operators. You can put your own numbers and target in the box. It is not prettily programmed, but is still quite quick.

share|improve this answer
    
Thanks a LOT for the ideas! You made my day! –  incognita May 16 '11 at 9:43
    
Sorry to bug you, the code seems very hard to understand, could you spend 5 minutes to explain it? You would make my week, I'd love to understand the strategy behind it. –  incognita May 16 '11 at 20:31
    
For example, what's the illness behind:((42 - ((6 - (level + 1)) * (7 - (level + 1)))) / 2); j < ((42 - ((6 - (level + 2)) * (7 - (level + 2)))) / 2); j++) –  incognita May 16 '11 at 20:57
add comment

Interesting problem.

I haven't written any code, but here's my thoughts. I haven't been able to think of an approach beyond brute force, with a little 'pruning'.

Using an RPN representation is the way to go, as it simplifies the handling of brackets (as such, they go away). Using your example, the RPN is 1 5 . 3 . 4 . where every '.' is a place where an operator might be, except for the right-most '.' where we know there has to be one or more operators, because it's RPN. Every other '.' has zero or more operators. For N values you must have N-1 operators, of course.

Now the problem splits into these parts: 1. Generate all combinations of N-1 operators (2^N) 2. For each operator combination, generate all 'fillings' of the operator points '.', ie, group the operator list by 1s, 2s, ..., N-1s, maintaining the operator order (my combinatorics-fu is weak, can't figure this out) 3. For each combination of combinations, evaluate the expression

The pruning occurs in the last step. As you evaluate, if the expression value goes beyond the desired result, stop with a fail, as there are no operators that might reduce the expression value.

share|improve this answer
    
I'm not enough into RPN, I wonder if I could sort all the possible expressions by value and then use a simple binary search. –  incognita May 16 '11 at 9:00
    
The RPN approach doesn't quite work here. One answer for 33 is 1 + (5 + 3) * 4, meaning that there is no operation on 1 and 5. Allowing the 1 5 3 4 order to change only works if it can change in the original problem. –  David Thornley May 16 '11 at 14:05
add comment

This problem is NP complete and therefore cannot be expected to be solveable in anything less than O(n!). However, as in all NP complete problems, you can of course approximate an algorithm that would get you close to 18, or alternatively, generate a list of similar numbers with operators that would result in 18.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.