The following
thread was originally started by Sameer Jamal. I'm reposting it this way because it was accidentally deleted during the move to Programming Diversions:
***************************************************
Posted by: Sameer Jamal, 05-12-2003 09:50 AM
Can you build an algorithm for computing a given number from a given array of integers.
Example: Target number to calculate = 937
Array(5) of integers: {100,10,9,8,7,3}
Each array number can only be used once.
The human answer would be:
100 * 9
+ 10 * 3
+ 7
-----
= 937
======
Of course the example is oversimplified, but it communicates the general idea. The algorithm must be sufficiently general to calculate any number from any combination of numbers.
It may be possible that the array combination may not yield a solution equal to the TargetNumber, in which case the solution should be the closest possible number to the TargetNumber.
Here is an example:
TargetNumber = 789
myArray {75,50,25,7,4,1} ' or is it possible to compute the TargetNumber?
***************************************************
Posted by: Simon Lee, 05-12-2003 11:29 AM
there is a tv show in the UK called 'countdown'. I am 100% sure (I'm not even going to hit google) that if you search for 'countdown solver channel4' you will find dozens of javascript implementations...
***************************************************
Posted by: Jason Menard, 05-19-2003 12:24 PM
I was playing around with this one. I solved it using a brute force method.
Given an int array "seed" of size n ,and an int "target", with seed being the array of integers used to compute target, and a set of operations OPS {"*","+","-"}:
1. Find all permutations of seed (n P 1..n) along with each combination of operations from OPS that may be performed on each permutation.
2. Solve each permutation p. If the solution for a permutation equals the target, we have our solution. Otherwise, if the abs(target - p) is the closest solution so far, store it as the solution and continue.
I stored each permutation as a stack. If seed = {1,2,3}, a few of the permutation stacks for this set would be:
[1]
[3,2,*]
[1,3,-,2,+]
The stack [1,3,-,2,+] evaluates as follows:
1 - 3 = -2
-2 + 2 = 0
Some performance enhancements that could be made to the included code:
1. Don't keep a collection of all permutations and then iterate through the collection to find the solution, simply solve each permutation as it is discovered. I wanted to see all the various permutations so this is why I did it the way I did.
2. Don't bother storing and/or solving permutations which are essentially the same. For example [1,3,+] is the same as [3,1,+].
I'm sure there are more, but these are the obvious ones. Of course as I stated previously, there must be a better way to find the solution aside from this brute force method.
[ May 20, 2003: Message edited by: Jason Menard ]
***************************************************
Posted by: Paul Stevens, 05-19-2003 04:44 PM
This doesn't look MDish to me.
***************************************************
Posted by: Simon Lee, 05-20-2003 02:23 AM
Maybe
you should watch countdown (the tv show). Imagine watching two people taking 30 seconds to come up with a solution, then they explain it to carol for 10 points.
MD is the best describtion for it.
***************************************************
Posted by: Don Kiddick, 05-20-2003 03:35 AM
I actually got this question in an interview ! Solution given (which I didn't get) was recursive and it involved finding each pair of numbers and the possible values that could result from them (using +-*/), then calling the function recursively with the result and the other numbers. Something like that anyway - it was long time ago !
***************************************************
Posted by: Joel McNary, 05-22-2003 08:48 AM
Originally posted by Don Kiddick:
I actually got this question in an interview ! Solution given (which I didn't get) was recursive and it involved finding each pair of numbers and the possible values that could result from them (using +-*/), then calling the function recursively with the result and the other numbers. Something like that anyway - it was long time ago !
OK, OK...I was a little bored and worked out the recursive method...
and the solution to:
TargetNumber = 789
myArray {75,50,25,7,4,1}
***************************************************
Posted by: Jason Menard, 05-22-2003 10:17 AM
I was a little bored and worked out the recursive method...
Actually, both solutions are recursive.
***************************************************
Posted by: Joel McNary, 05-22-2003 11:19 AM
Oops...I guess they are. Silly me.
It was a good exercise anyway.
I note that your solution does not include division; is division permitted? (I included it in mine...)
I think that most interesting result I got was calculation 788 using the same numbers as for 789:
C:\>
java CountdownSolver 788 75 50 25 7 4 1
Target: 788
Best Solution(7 - ((1 - (25 * (75 + 50))) / 4))
Value: 788.0
Deviation: 0.0
***************************************************
Posted by: Jason Menard, 05-22-2003 11:37 AM
[quote
riginally posted by Joel McNary:
I note that your solution does not include division; is division permitted? (I included it in mine...)
Trying to find out some info about the game Countdown, it seemed that the only operations allowed were multiplication, addition, and subtraction, so that's the direction I headed. Besides, as you found out, division leads to all sorts of nastiness.
I think that most interesting result I got was calculation 788 using the same numbers as for 789:
I just reviewed a book called Java Number Cruncher: The Java Programmer's Guide to Numerical Computing. It goes into detail about precisely the type of problems you ran into. It's worth a read if you get the chance.
[ May 22, 2003: Message edited by: Jason Menard ]
***************************************************
Posted by: Randall Twede, 05-22-2003 11:55 AM
how about one using mod, trig functions, integrals, derivatives, and factorials?
***************************************************
Posted by: Jason Menard, 05-22-2003 11:57 AM
Originally posted by Joel McNary:
I think that most interesting result I got was calculation 788 using the same numbers as for 789:
C:\>java CountdownSolver 788 75 50 25 7 4 1
Target: 788
Best Solution(7 - ((1 - (25 * (75 + 50))) / 4))
Value: 788.0
Deviation: 0.0
Without division, it looks like that one can't be solved exactly. I ended up with the following solution:
Seed Numbers: [75,50,25,7,4,1]
Target: 788
Solution: 75 + 25 = 100
100 + 4 = 104
104 + 1 = 105
105 * 7 = 735
735 + 50 = 785
Distance from target: -3
***************************************************
Posted by: Randall Twede, 05-22-2003 12:01 PM
oh and lets not forget exponents and logarithms
***************************************************
Posted by: Jason Menard, 05-22-2003 12:07 PM
Originally posted by Randall Twede:
how about one using mod, trig functions, integrals, derivatives, and factorials?
Luckily, the game seems to only allow the three operations. If you are trying to solve using brute force, the number of possible permutations gets ridiculous with all those other operations, not to mention the problems of accuracy that would arise. However if you'd like to tackle a version with all these extras, I know I'd be interested in seeing it.
[ May 22, 2003: Message edited by: Jason Menard ]
***************************************************
Posted by: Joel McNary, 05-22-2003 12:52 PM
Originally posted by Jason Menard:
Without division, it looks like that one can't be solved exactly. I ended up with the following solution:
Seed Numbers: [75,50,25,7,4,1]
Target: 788
Solution: 75 + 25 = 100
100 + 4 = 104
104 + 1 = 105
105 * 7 = 735
735 + 50 = 785
Distance from target: -3
Interesting. I thought you should come up with 789 (((75 - 1) * (7 + 4)) - (50 - 25)), which is 1 away...or can't you use parens to group?
***************************************************
Posted by: Jason Menard, 05-22-2003 01:23 PM
hatever page I looked at to try to figure out the rules didn't use either division or parens, but now that I am looking on other sites I can see many that do use these. I would of course have to alter not only my evaluation but the way I found permutations.
Maybe you have to be British to really understand it. In any case, it was a fun exercise. I think I should at least get style points for my stacks and evaluate methods! Although somewhere out there is a genetic algorithm solution (whatever that is exactly) for these types of problems, which is probably far more elegant than anything my lowly brain can produce in its current state.
To be honest I'd like to see more of these kind of postings. Particularly if several people take a stab at solving them.
[ May 22, 2003: Message edited by: Jason Menard ]
***************************************************
Posted by: Joel McNary, 05-23-2003 06:08 AM
Originally posted by Jason Menard:
Although somewhere out there is a genetic algorithm solution
I'll get to work on it...but it'll take a back seat to some of my other projects
To be honest I'd like to see more of these kind of postings. Particularly if several people take a stab at solving them.
Me too....I'll se what I can come up with...
[ May 31, 2003: Message edited by: Jim Yingst ]