THINK FIRST·CODE LATER

← All labs

The 24 game: backtracking over expressions

Problem

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, j in 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)

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

d1-9-data-1.txt

4 7 8 8
1 1 1 1
3 3 8 8
5 5 5 1
What your program must print for d1-9-data-1.txt
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)

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < d1-9-data-1.txt

Windows PowerShell does not understand <:

Get-Content d1-9-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.