Description

Practice Project -- 5

Project Overview:  In this project, you will use the knowledge you have learnt from this course so far (selection, iteration, arrays and functions) to write a program to solve the 24 game. In the 24 game, four cards (or 4 numbers with ace being 1) are drawn from a deck of playing cards with all the Jokers, Jacks, Queens, and Kings removed. The player needs to make 24 out of these 4 numbers using four basic operations: addition, subtraction, multiplication and division. The player must use each number once and only once, but the player can use each operator any number of times. Of course, since there are only 4 operands, only three operators are needed, but these three operators do not need to be different. For example, given 9, 8, 4, and 5, one possible solution is (9-8+5)*4. For another example, given 2, 5, 5, and 10, one possible solution is (5-2/10)*5=24. Your job is to write a program to read in four integers, each of them ranging from 1 through 10, and to make 24 out of these 4 numbers and 4 operators using the rules specified above. If there are multiple solutions, your program needs to print out only one solution. And if there is no solution (9, 7, 7 and 6 for example), the program just prints out “no solution.” When writing a program to solve this problem, you need to try every possibility that involves permutation and enumeration.

Permutation: given 4 numbers, these 4 numbers can appear in any order in a solution. Therefore, your program needs to try all the permutations. Generating all the permutations out of 4 numbers (or any numbers) is a little hard for a beginning programmer. In this project, a way to generate all the permutations is provided. Specially we will produce all the permutations in lexicographical order. For example, given 4 numbers such as 8, 7, 6, and 9, this method will generate 24 permutations from the smallest (6 7 8 9) to the largest (9 8 7 6). In the permute.c file (provided on Blackboard), a function named findNext is given to find the next permutation (in lexicographical order) after a known permutation. For example, if the input permutation to the function is (7 6 9 8), the next permutation after it lexicographically will be (7 8 6 9). To generate all the permutations, you need to first sort the 4 numbers entered by the user in ascending order, which produces the first permutation in lexicographical order, i.e. (6 7 8 9). Then you call the findNext function again and again to find the next permutation until it reaches the last permutation in which the 4 numbers will be arranged in descending order, i.e. (9 8 7 6). Once it reaches the last permutation, the findNext function can’t produce another permutation by returning 0. Please see print.c (also provided on Blackboard) to see how to use the findNext function.  

Operator enumeration: once the order of these 4 numbers in a permutation is known, it is time to add operators. Assume the 4 numbers in a permutation is (a b c d). You need to add three operators, say op₁, op₂, op₃ to get an expression: a op₁ b op₂ c op₃ d. Each operator can be one of these +, -, * and /operators. Your program has to enumerate them.

Order of computation: with three operators, there are six possible orders of computation and let’s number them as 123, 132, 213, 231, 312, and 321 as below.

            123: ((a op₁ b) op₂ c) op₃ d

132: (a op₁ b) op₂ (c op₃ d)

213: (a op₁ (b op₂ c)) op₃ d

231: a op₁ ((b op₂ c) op₃ d)

312: (a op₁ b) op₂ (c op₃ d)

321: a op₁ (b op₂ (c op₃ d))

For example, 213 means performing op₂ first, then op₁, and finally op₃. Therefore, with the 213 order, the expression will be evaluated as (a op₁ (b op₂ c)) op₃ d. Please note the orders 132 and 312 will be produce the same value and only one of them needs to be evaluated.

Real number computation: although the input are all integers, the division operation could produce a real number. It is better to use real number computation to evaluate an expression in this project. However, the real number computation by the computer is not precise. When checking whether an expression value (say x) is 24, you need to use something like 24-0.0001 < x && x < 24+0.0001 instead of x==24.

Output optimization: for this project, if there are multiple solutions, you only need to output any one of them, and the output expression can contain two pairs of parentheses. When time permits, consider outputting the most elegant one out of all the solutions. For example, the output expression contains the minimal number of parentheses, the expression produces no real numbers or negative numbers as intermediate results during the evaluation, etc.

What You Need To Do

·         Create a directory named pproject5 on your machine. Download permute.h, permute.c and print.c to the pproject3 directory, compile the print.c program using gcc -Wall        -std=c99 print.c permute.c and check out how all the permutations are printed out.

·         Create a file named 24.c in the pproject5 directory. In 24.c, write the code needed to solve the problem stated above. Make sure that your program:

o   Has a line of #include "permute.h" in the include block.

o   Has a header block of comments that includes your name and a brief overview of the program.

·         Please compile the project using gcc -Wall -std=c99 24.c permute.c

                                Sample executions of the program

./a.out

Enter 4 integers ranging from 1 through 10: 9 7 7 6

No solution