0

How to write a program that computes a mathematical expression consisting of given numbers, which evaluates to the also given result? If no expression which evaluates to the exact result exists, then the closest result is computed. Example: You are given a random result: 520, and you are given 6 random integers: 2,4,1,6,15,44. Using operands +,-,*,/ and 6 random integers, find that given result 520 or closest number to 520. Any ideas?

ShomyLee
  • 11
  • 1
    This might be NP hard... – invalid_id Aug 22 '14 at 07:23
  • Are you allowed to use the same random number twice? For your example, something like `44 + 44 * 6 + ...`...? – Tony Delroy Aug 22 '14 at 08:05
  • 1
    If he were allowed to use them more than once, he could do (X/X)+(X/X)+... until he reaches to the result, without even using any second integer. – Seyf Aug 22 '14 at 08:22
  • Recognising / guessing the original source of the problem, I searched for [algorithm countdown is:question](http://stackoverflow.com/search?q=%5Balgorithm%5D+countdown+is%3Aquestion) and I found these dupes: [How to design an algorithm to calculate countdown style maths number puzzle](http://stackoverflow.com/q/15293232) ; [24 Game/Countdown/Number Game solver, but without parentheses in the answer](http://stackoverflow.com/q/16510634) ; [Code Golf: Countdown Number Game](http://stackoverflow.com/q/4586814) of which the first seems best so is my VTC dupe target – AakashM Aug 22 '14 at 09:14
  • You get 4 random numbers from 1 to 10, 1 random number from 10 to 20 and 1 random number from 20 to 100. Numbers can't be used more then once. – ShomyLee Aug 22 '14 at 09:58

1 Answers1

1

This is an NP-hard problem. You should brute-force all the possibilities to come up with a solution. If you want to reduce the time, you may try to find a heuristic method to get closer to a possible solution (and reduce the time to solve). However, it might not be as easy as developing the brute-force method.

It will take quite a time when number of inputs are large.

If you want to go further, here are the keywords: np, np-complete, np-hard, complexity, heuristic

Seyf
  • 889
  • 8
  • 16