My Computer Forum Computer Science Forum

Go Back   My Computer Forum > Computer Science Forum > Algorithms

Algorithms Algorithms and Data Structures - Analysis, Graph, Search, String, Sorting, Merge, Compression, Optimization, Quantum


Reply
 
LinkBack Thread Tools Display Modes
September 20th, 2009, 04: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 semi-educational 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
To do this, I assume the program would have to evaluate all possible configurations of the numbers, put them in a list and find the largest one. If the player's configuration evaluates to that value, he or she has won.

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
Nevon is offline  
 

My Computer Forum is free to register and we welcome everyone!

November 1st, 2009, 04: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.
SidT is offline  
December 23rd, 2009, 03:26 PM   #3
 
Joined: Dec 2009
Posts: 7
Re: Computing all possible sums

This looks like on of the NP-hard 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.
vin.san is offline  
December 24th, 2009, 03:38 AM   #4
Site Founder
 
julien's Avatar
 
Joined: Dec 2007
Posts: 414
Re: Computing all possible sums

An algorithm can definitely be written in order to find the solutions by brute-force 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.
julien is offline  
January 20th, 2010, 11:30 PM   #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.
vin.san is offline  
April 30th, 2010, 01:07 PM   #6
 
Joined: Apr 2010
Posts: 96
Re: Computing all possible sums

If the 6 numbers are hard-coded...hard-code the solutions which will make it run smoother for the end-user 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 hard-coding 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
asbo is offline  
Reply

  My Computer Forum > Computer Science Forum > Algorithms

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 12:56 PM
Cloud Computing Virtual Conference 2010 Adara Byme Networking 0 January 30th, 2010 10:02 PM





Copyright © 2018 My Computer Forum Forum. All rights reserved.