# Order of Operations Game Solution

My AP Computer Science teacher likes to play a game with his students where he writes 4 random numbers on the board and a fifth, target number. The objective is to use the four basic operations (+,−,×,÷) to get the target number. Each number can only be used once, but the operations can be reused. Order of operations does apply, and the numbers can be reordered.

Ex: Given the numbers 6 9 5 4, get to 50

Solution: (9 + 5) × 4 - 6 = 50

My teacher and I are looking for a way to find the solution(s) to a set of 5 numbers with a computer program. Because there are 24 arrangements of 4 numbers and 24 ways to arrange the 4 operations, there are 576 potential solutions to check, so brute force is not exactly easy.

• AP Computer Science? 576 really isn't that many cases at all. – Edward Jiang Jan 7 '15 at 3:19
• And there are really $1536$ cases. $24$ for the number of ways you can permute the $4$ numbers, and $64=2^3$ for the number of ways you can put binary operations between them. – Edward Jiang Jan 7 '15 at 3:21
• As a teenager, I was obsessed with playing this game! I never thought it would become formalized! – Robert Lewis Jan 7 '15 at 3:27
• @EdwardJiang I'm not sure I understand why there are 1536 cases. There are 24 permutations for 4 operations applied 3 at a time. If each of the 24 arrangements of numbers is used with these 24 operation combinations, you get 24*24 which is 576. Where am I going wrong? – Eric Roch Jan 7 '15 at 3:52
• @EricRoch the operations can be reused, and you can use parentheses as well. – onetoinfinity Jan 7 '15 at 3:54

You are given $4$ numbers, and a target. There are $4!$ ways to arrange the $4$ numbers. There $4^3$ ways to add an operation between two numbers. Then, there are $8$ distinct ways to add parentheses to group numbers (this may be redundant over multiplication or division, but it does not add that much more to the computation time). This means there are $4!\cdot4^3\cdot8=12288$ possibilities for the computer to check, which should take about one to two seconds maximum.
• I would claim that this is not the way a human would solve it, but it is a good way to write a program. In your example, my first thought would be that $50=5\cdot 10$, so I would look for $10$ from $9\ 6\ 4$. After some playing I would fail unless you give me integer divide and $9+6/4=10$. I would then look at other things. I think the big point is that those humans who would attack the problem have a lot of facts about small numbers available, and will use those to guide the search. – Ross Millikan Jan 7 '15 at 3:54