File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
The moose likes Java in General and the fly likes Tricky task! Help needed... Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Tricky task! Help needed..." Watch "Tricky task! Help needed..." New topic

Tricky task! Help needed...

Fredrik Mark

Joined: Nov 03, 2003
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

Joined: Jan 04, 2001
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

Joined: Oct 02, 2003
Posts: 11955

do you have to find A combination, or ALL the combinations?

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Jaap van Hengstum

Joined: Jul 24, 2003
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

Joined: Nov 03, 2003
Posts: 2
Thanx Jaap van Hengstum!
Jaap van Hengstum

Joined: Jul 24, 2003
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 ]
I agree. Here's the link:
subject: Tricky task! Help needed...
It's not a secret anymore!