[Previous] A Problem With School | Home | [Next] N

24 Game

game: you are given 4 numbers. combine them all to make 24 using + * - / and ().

examples:

numbers: 3 3 7 8
solution: 3*3+7+8

numbers: 1 5 9 12
solution: (5-1)*9-12

numbers I was given to solve:

2,3,10,10
3,3,7,7

Try them, it's fun.

I wrote a Ruby program to brute force these. Then I wrote a second much more elegant one.

The first program does this:

find all the different ways to put the numbers in order. find all the different ways to put the operations (+,-,*,/) in order (but making sets of only 3 of them). then make all possible pairs of the numbers in an order and the operations in an order, and interleave them. so we get all ways to combine the 4 numbers in any order with operations between them. *then* we can't just evaluate those because order of operations is important. so we try evaluating in all possible orders. (do the first, second, or third operation. that leaves 3 numbers and 2 operations. try both orders).

ugh.

the second program is smarter. i realized that one step towards a solution consists of combining 2 numbers with an operation. if you think about it this way, you don't have to worry about order of operations. so just find all the ways to pick 2 numbers from whatever numbers you have left, then try all 4 operations. make sure to put the numbers in either order, b/c 7-3 and 3-7 are different. if you divide by zero, throw that out. once you do this, you now have 3 numbers. you replaced 2 numbers with one number. ok, great, we made progress. now do it again, and you find yourself with 2 numbers, then one. make sure to stop when you get to one. much better. as it goes, it keeps track of the history so if it finds an answer it can tell you what it did.

UPDATE:

I cleaned up my code enough to show the second search function. but the formatting comes out awful when i paste it here. if you ask i can email it.

Elliot Temple on March 13, 2007

Comments

What do you think?

(This is a free speech zone!)