2

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.

Eric Roch
  • 123
  • AP Computer Science? 576 really isn't that many cases at all. – Edward Jiang Jan 07 '15 at 03: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 07 '15 at 03:21
  • As a teenager, I was obsessed with playing this game! I never thought it would become formalized! – Robert Lewis Jan 07 '15 at 03: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 07 '15 at 03:52
  • @EricRoch the operations can be reused, and you can use parentheses as well. – onetoinfinity Jan 07 '15 at 03:54
  • @onetoinfinity ah of course. Thank you for clearing that up – Eric Roch Jan 07 '15 at 04:04

1 Answers1

1

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.

Some pseudocode for this would have some data structure (Array, or an equivalent) with 15 cells to hold all possible combinations of numbers, operations, and parentheses, with an iterator like a for loop running through and testing all possible arrangements. I know this is a little oversimplified, but programming isn't my strong suit and I would appreciate it if someone with a little more experience could add something more substantial.

onetoinfinity
  • 437
  • Care to post pseudocode? – Edward Jiang Jan 07 '15 at 03:28
  • @Edward added as much as I could. – onetoinfinity Jan 07 '15 at 03:36
  • @onetoinfinity that is an interesting way to approach it. I was looking for a more elegant way to solve it though. What you have described is essentially how a human would go about solving it, just many many times faster. – Eric Roch Jan 07 '15 at 03:47
  • 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 07 '15 at 03:54
  • @onetoinfinity I counted 10 distinct ways to put parentheses around 4 numbers. So it would actually be 15360 cases. Also, I'm a little confused as to what you mean by using an array. How can I take an array and turn it into an algebraic expression which the program can compute? I get that I could make a string to represent the expression, but then what? I program in Java, but a general answer will help too. – Eric Roch Jan 09 '15 at 13:41