This week's book giveaway is in the Design forum.We're giving away four copies of Design for the Mind and have Victor S. Yocco on-line!See this thread for details.
Win a copy of Design for the Mind this week in the Design forum!

# Tricky task! Help needed...

Fredrik Mark
Greenhorn
Posts: 2
I have this problem I need to solve and I have no idea even where to begin! Given 6 integers (int) the method I have to create shall determine wheter it exists any combination of the first 5 integers and + - * that gives the 6th argument as a result. If it does exists then the output should be an expression. Ex: java Expr 1 1 1 1 1 100 -> "no solution", java Expr 15 4 13 18 80 200 -> (18+80)*(15-13)+4.
I would appreciate any tip that can help my in the process of solving this problem!

Zkr Ryz
Ranch Hand
Posts: 187
I say this look pretty easy.
0.- while there are more combinations
1.- try a combination
3.- if the result == lastArgument
finish you've found the solution
4.- else try with a new combination
If there's no more combinations there's no solution.
Try some code with these ideas and if you have specific questions, I'll be glad to respond.

fred rosenberger
lowercase baba
Bartender
Posts: 12098
30
do you have to find A combination, or ALL the combinations?

Jaap van Hengstum
Greenhorn
Posts: 24
This sounds like a homework question
Anyway, what you need to do, is to find all permutations of the 5 numbers and combine them with all the four-position combinations you can find of the three operators (+,-,*). To find the permutations and combinations, you can use simple recursive functions.
If I've done everything correctly, the code below should print all the permutations of the 5 numbers and all the combinations of the three operators. Now all that needs to be done, is combine every permutation with every combination and check the result.

Edit: okay, so this problem is a bit trickier than I initially thought, since you also have to take into account the order in which to take the operations (the parenthesis).... (drat )... it would make a good homework assignment though
[ November 03, 2003: Message edited by: Jaap van Hengstum ]

Fredrik Mark
Greenhorn
Posts: 2
Thanx Jaap van Hengstum!

Jaap van Hengstum
Greenhorn
Posts: 24
If you are interested, I have made a Java program which does the job. It doesn't use the most optimal solution, but it gets all the possible answers, f.e. operating on your example numbers it gives the following solutions:

4+((18+80)*(15-13)) = 200
((18+80)*(15-13))+4 = 200
4+((15-13)*(18+80)) = 200
((15-13)*(80+18))+4 = 200
4-((18+80)*(13-15)) = 200
((15-13)*(18+80))+4 = 200
4+((80+18)*(15-13)) = 200
4-((13-15)*(80+18)) = 200
4-((80+18)*(13-15)) = 200
4+((15-13)*(80+18)) = 200
4-((13-15)*(18+80)) = 200
((80+18)*(15-13))+4 = 200
233280 combinations processed.

You see, it doesn't take into account the commutative and associative nature of the operators, so it gives too much solutions. To solve that, you probably need to use a totally different algorithm (than the one described above).
It'll be nice to see if you or anyone else has come up with a better way though...
[ November 05, 2003: Message edited by: Jaap van Hengstum ]