The twenty-four points is a Poker game. In this game, cards A~K represent numbers 1~13, and take four of them randomly to construct an expression with four basic operations - plus, subtract, multiplication and division to get 24. For example, there are four numbers 2, 3, 8 and 10. You can do calculation 2-8+3*10 to get 24. Sometimes there are other approaches, like 2*3+8+10. You can use this four numbers to do plus, subtraction, multiplication and division in any order you want. At last I find there are 1820 different combinations of different operands and only 1362 of them are solvable.
Expression Analysis
Expression Analysis
It seems like a simple problem. And the truth is not complex, too. We start with an expression:
In[]:=
expr=a*(b+c)+d;
We use TreeForm to see the structure of the expr
In[]:=
expr//TreeForm
Out[]//TreeForm=
For every subtree, it’s an subexpression. For example, b+c is a subexpression of the whole expression and is a subtree of the whole tree. Every subtree corresponds to a sub expression. And the whole expression consists of many subexpressions as the whole tree consists of many subtrees. We can calculate every sub tree from bottom to top. The following list shows a process of calculate a tree:
In[]:=
TreeForm/@{"a"*("b"+"c")+"d","a"*"b+c"+"d","a*(b+c)"+"d","a*(b+c)+d"}
Out[]=
,
,
,
If we want to calculate the whole expression, we can calculate the subtrees from bottom to top. But sometimes, it’s hard to know where the lowest subtree is. So we can just consider the root of every subtree from the top root. If its left subtree hasn’t been calculated, then calculate. So does its right subtree.
In[]:=
Tree["root",{"leftsubtree","rightsubtree"}]
Out[]=
Every root of a subtree should be an function or operation with two inputs. Like the operation Plus is actually a function with two input and one output. Here we can use func1, func2, func3 and so on to denote every operation, which is more universal. As for the commutative law of plus and multiplication, we will consider later.
Now let’s consider four operations: func1, func2, func3 and func4.
In[]:=
operations={func1,func2,func3,func4};
In twenty-four points game, there are four operands in total. But we don’t pay attention to the number of the operands. With the analysis before, we can regard every expression is an operation with two subexpressions recursively. For example, a+b+c+d seems an expression with four inputs because its FullForm is:
In[]:=
{FullForm[a+b+c+d],ExpressionTree[a+b+c+d]}
Out[]=
Plus[a,b,c,d],
That’s because the Plus operations is attributed with Flat. So the tree has more than two kids. But we can do some transformation to make it a binary tree:
In[]:=
Tree["Plus",{"a",Tree["Plus",{"b",Tree["Plus",{"c","d"}]}]}]
Out[]=
So we just need to consider a tree like . After we calculate the result of left subtree and right subtree, we use operation represented by the root on the two subtrees and get the value of this tree. We do the work for every subtree recursively and finally we will get only one value.
Build Expressions
Build Expressions
Now let’s consider how to build all possible expressions with four different operations and four operands.
If I have a list of operands in order like {a, b, c, d}. We can do every possible operation to every two of them. While the simplest idea is to do on the first and second.
If we do operation func to a and b, we will get func[a,b] as a result. We can add it to the operands list.
If I have a list of operands in order like {a, b, c, d}. We can do every possible operation to every two of them. While the simplest idea is to do on the first and second.
If we do operation func to a and b, we will get func[a,b] as a result. We can add it to the operands list.
In[]:=
{a,b,c,d}->{func[a,b],c,d};
The expression tree will be like . And after the first operation, we have three operands left. We can do what we have done before, do the all possible operations on the first and the second operands. For example, we still do func on func[a,b] and c and we obtain func[func[a,b], c] as a new operand.The operands list become {func[func[a, b], c], d}. And do it again, the list become {func[func[func[a, b], c], d]}, which is a single element set. That element is the expression we construct.If we have four different functions: func1, func2, func3 and func4. We can do different operation every time. The expressions can be constructed as func1[func2[func3[a, b], c], d] or func2[func1[func4[a, b], c], d], which contain 4*4*4=64 different results. But we don’t have to choose to operate on first two operands. They can be any two of all operands. Then, there are
different combinations to construct expressions. Next, let’s find them all.
If the operands list is a single element set, it does not need to be calculated.
Otherwise, we can do different operations on the any two of operands. I use function f to return all the possible expressions with input operands. We can divide the operands list into two smaller sublists and do function f on both of them respectively.
We can enter {a, b, c} to see how many possible expressions can be constructed and what they are.
Or we can check them in tree form:
For our game, there are four operands. So the operands list should be {a, b, c, d}.
There are 320 possible expressions can be built. But that’s not all. Because I do the operations on the ordered operands list. We can change the order of the operands to build more possible expressions. So there is one more step to do.
We act f on every possible permutation of the operands and join them together, then delete the duplicate elements.
There are 7680 possible expressions can be constructed with four operations and four operands. So, if you can’t figure out the game, it’s okay because there are too many possible results.
Solution Function
Solution Function
In this specific game, the four operations are Plus, Subtract, Multiplication and Division. There is commutative law held for Plus and Multiplication. So the possible expressions are less than 7680. So we reset the values of the operations list and calculate all possible expressions again.
There are only 1260 possible expressions left, much less than 7680. They are
In fact, although the numbers of expressions reduce, we can’t easily figure out answers to questions. There are still too many. But we can replace every symbol into specific numbers and find out which expressions are exactly the value we want, 24.
The target is the final value we want, which is 24 in this game. The nums is a list of all available operands. I turn off the infy message because it will show up when there are two equal operands causing 0 as a denominator. Turning it off won’t have effect on the results.
Solve Problem
Solve Problem
And now we can use our function to solve the game. There are no more difficult problems!
For example, to get 24 with {2, 3 ,8, 10} can be calculated like:
And {3, 7, 10, 11}
Oh, there are so many solutions!
As for {5, 5, 5, 12}, it seems like a hard question. But it can be solved immediately now.
And I list some problems as following, whose targets are all 24. If you are interested in, you can try on your own and use the function to check the answer.
You can enter the following command to get all the results.
All Solvable Problems
All Solvable Problems
There are some sets of numbers unsolvable. For example, {1, 1, 1, 1} is obviously unsolvable. The candidates include numbers from 1 to 13. So we can list all possible outcomes and check if there is any solution.
First like all possible combinations of operands, {1, 1, 1, 2}, {1, 1, 2, 1}, {1, 2, 1, 1} and {2, 1, 1, 1} are regarded as the same. Because the function solve will do all possible permutations, which means we can choose the order we do operations on operands as we want.
First like all possible combinations of operands, {1, 1, 1, 2}, {1, 1, 2, 1}, {1, 2, 1, 1} and {2, 1, 1, 1} are regarded as the same. Because the function solve will do all possible permutations, which means we can choose the order we do operations on operands as we want.
There are only 1820 different possible combinations, which can also be calculate by:
Let’s find out all solvable problems, and it will take over 3 mins to check.
{1, 1, 1, 1} and {13, 13, 13, 13} are both unsolvable.
This algorithm is based on enumerate, which is inefficient. Since I produce all possible combinations of operands and operations as every four operations are general without any operation laws, and then replace them with plus, subtract, times and division, it makes it necessary to delete many duplicate outcomes in function allPossibleExp. The generating and deleting process for redundant expressions spend too much time.
If the commutative law were taken into consideration at first, a faster algorithm might be built. But we may need to program more code. The advantage of previous approach is the code is very short, I think. Ha ha!
Summary
Summary
◼
The problem can be solve by enumerating as what I did. The key to solve game “24 points”, or “Make 24” is to permute both operations and operands to change the calculation order.
◼
There are 1820 different combinations of operands, but the solvable questions are only 1362.
◼
There may be a better way to solve this problem at lower level time complexity.
◼
The game is interesting and worth playing.