Fredrik Mark

Greenhorn

Posts: 2

posted 13 years ago

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!

I would appreciate any tip that can help my in the process of solving this problem!

Zkr Ryz

Ranch Hand

Posts: 187

posted 13 years ago

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.

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.

Jaap van Hengstum

Greenhorn

Posts: 24

posted 13 years ago

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 ]

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 ]

Jaap van Hengstum

Greenhorn

Posts: 24

posted 13 years ago

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:

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 ]

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 ]