In the 24 game you receive four cards (1 to 13) and must combine all four with +, −, ×, ÷ and parentheses to obtain exactly 24. Write TwentyFour, which reads groups of four numbers until the end of the input.
Recursive idea: from a list of numbers, pick two, replace them by the result of one operation, and solve the shorter list; when a single number remains, check whether it is 24. Keep, next to each number, the text of the expression that produced it.
- Pairs are tried by positions
i,jin increasing order; for each pair the operations are tried in the order+,×(only when i < j, since they are symmetric),−,÷(never divide by zero). - The new value is added at the end of the list of the remaining numbers.
- Compare real numbers with a tolerance: |value − 24| < 10⁻⁹.
Print the first expression found and how many successful ways the search met, or no solution. For the input
4 7 8 8
1 1 1 1
3 3 8 8
5 5 5 1
the program prints
4 7 8 8: (8 * ((4 + 7) - 8)) = 24 (16 ways to combine the cards)
1 1 1 1: no solution
3 3 8 8: (8 / (3 - (8 / 3))) = 24 (4 ways to combine the cards)
5 5 5 1: (5 * (5 - (1 / 5))) = 24 (6 ways to combine the cards)