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

 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 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 operator num operator num = sum num operator num operator num = sum if sum > sum then difference = sum - sum else difference = sum - sum 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 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 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. 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 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. 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 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 Tags computing, sums Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post cknapp Theory of Computation 22 April 21st, 2011 01:56 PM Adara Byme Networking 0 January 30th, 2010 11:02 PM

 Cryptocurrency Forum - Contact - Home - Top       