I am trying to implement the 24 Game in ansi C. This game goes as follows:
For a list of four given numbers, try to find a solution involving these four numbers, that, using addition(+), subtraction(-), multiplication(*) and division(/) ends up at 24. Each number can only appear once, but the order of the numbers might be changed of course. It is possible to use brackets to change the order of the operands (and you have to do so for many of the solutions).
I wanted to build on top of this problem, and invent a M Game, where M can be an arbitrary number, and you can give an arbitrary length N list of values.
What I know:
- Operators can be re-used multiple times in the formula. Thus, when iterating over the operators, I can just use flags to check if a certain operator should be used at a certain place.
- Numbers can only be used once. There exist great tutorials out there that explain how to permute an array until all different orders have been exhausted.
However, what I still am having trouble with, is how to decide the different combinations of operators.
Say I have a function
This function is non-commutative, e.g. op(A,B) != op(B,A). Now, if I have four values, I want to know in what ways I need to combine these functions. I know that the sequence of Catalan numbers tells us how many options there are. (for four numbers, there are 5 sequences). These are:
- op(A, op(B, op(C,D)))
Using a simple bitVector with recursion I am able to find the first four. But not the fifth, where two nodes share the same 'level'.
Is there an iterative way to test all these different options?
Or, as Ordous aptly put it:
how to enumerate/generate all possible binary trees from N leaves and N-1 nodes?