
Algorithms Algorithms and Data Structures  Analysis, Graph, Search, String, Sorting, Merge, Compression, Optimization, Quantum 
 LinkBack  Thread Tools  Display Modes 
September 20th, 2009, 05:54 AM  #1 
Joined: Sep 2009 Posts: 1  Computing all possible sums
Hello, I joined this forum in hopes of getting some help with a problem I've encountered in a semieducational game that I'm making. The basic object of the game is to create as large a difference between two sums as possible, by positioning 6 given numbers in various places relative to 4 operators. To show you what I mean, here's a rough visualization: The operators are all distributed randomly, and the user can then place the numbers freely in the colored boxes. The three numbers on the left (together with the two operators on the left) form one expression, and the ones on the right form another. Once all numbers have been placed, the two expressions should be evaluated to see if it creates the largest inequality possible. So basically, this is the objective of the game: Code: num[1] operator[1] num[2] operator[2] num[3] = sum[1] num[4] operator[3] num[5] operator[4] num[6] = sum[2] if sum[1] > sum[2] then difference = sum[1]  sum[2] else difference = sum[2]  sum[1] end if difference == LARGEST_POSSIBLE_DIFFERENCE then print "Winner!" end What I don't know is how to evaluate all possible configurations, and as such, that is what I would like you to help me with. Thank you, and please let me know if you have any questions. ~Nevon 
My Computer Forum is free to register and we welcome everyone! 
November 1st, 2009, 05:01 PM  #2 
Joined: Dec 2008 Posts: 30  Re: Computing all possible sums
I suppose if you knew which function generates the numbers, you could use calculus.

December 23rd, 2009, 04:26 PM  #3 
Joined: Dec 2009 Posts: 7  Re: Computing all possible sums
This looks like on of the NPhard problems if number of operators and numbers are not finite. There is no verifier or membership proof for this problem. But since you are dealing with special case there might be a solution. Let me check and I will reply after some time. 
December 24th, 2009, 04:38 AM  #4 
Site Founder Joined: Dec 2007 Posts: 414  Re: Computing all possible sums
An algorithm can definitely be written in order to find the solutions by bruteforce search ... the only difficulty would be to pay attention to the order of the operations and to come up with something that would be computationally satisfactory.

January 21st, 2010, 12:30 AM  #5 
Joined: Dec 2009 Posts: 7  Re: Computing all possible sums
I could not get the optimal soln. But this will work to some gooa approximation factor. To maximize the difference you need to maximize output of the operations on three numbers and minimize on other three. If numbers are greater than one then problem is easier. Clearly maximizing is easier. Use largest two numbers of the sequence for multiplication and add the third largest number to it. Just sort the array and use * and + as first and second operator. Unfortunately same logic does not hold optimally for the remaining three numbers. If x4 x5 x6 are last three numbers you need to check all cases. But its a small number. (3!) Hope this helps. sorry for late reply. Winter was lil long. 
April 30th, 2010, 02:07 PM  #6 
Joined: Apr 2010 Posts: 96  Re: Computing all possible sums
If the 6 numbers are hardcoded...hardcode the solutions which will make it run smoother for the enduser so the students could even use it on a netbook seamlessly. But if the 6 numbers are random to prevent cheating: put all the numbers in an array hard code all the possible variant such as "num1 ,2 ,3 : num 2,3,4" e.t.c add the answers to the above into an array and sort it select smallest/biggest from array and theres your answer where I said add them all...you can adjust that to this specific problem...but to be honest you are best hardcoding the answers. another way would be to have an array of 4 values, the first being the answer to the first, and the rest are the rest of the values...and after each calculation if the answer to the new one is bigger/ smaller than the old max/min then replace the array with current which would waste cpu time possibly...but might be more efficient 

Tags 
computing, sums 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Quantum Computing...  cknapp  Theory of Computation  22  April 21st, 2011 01:56 PM 
Cloud Computing Virtual Conference 2010  Adara Byme  Networking  0  January 30th, 2010 11:02 PM 