CMPT 102 - Assignment 4

Out: Friday, Nov. 4, 2005
Due: Friday, Nov. 18, 2005 at 5:00pm
Weight: 10%
Total: 100 marks

Question 1 [25]

Write a program that will let the user to interactively play the eight puzzle.

The eight puzzle consists of a 3x3 grid with eight tiles numbered from 1 to 8 and a blank space. We can make a move by sliding a tile adjacent to the blank space into the blank space. For example, the following shows three possible configurations of the tiles. In configuration (a), we can slide the tile numbered 2 into the blank space and obtain configuration (b). Given any configuration, the object is to make a series of moves and achieve configuration (c).
```
1 2 5             1   5            1 2 3
4   6             4 2 6            4 5 6
7 8 3             7 8 3            7 8  
 (a)               (b)              (c)
```
Your program begins with generating a random configuration and displaying the configuration. In order to generate a different configuration on every run of your program, you can use the following statement in your program:
srand(time(NULL));
This statement assigns the current system clock as the seed to the random number generator. To use the time function, you will need to include the time.h file.
Then your program repeatedly asks the user to input a move and processes the user input as follows.
- The user can input one of the following moves: 'u', 'd', 'b', and 'f', meaning moving the blank space up, down, backward, and forward, respectively. To process the input, your program should first check whether that move is possible. If not, your program should print "Invalid move!". Otherwise, your program should update the current configuration accordingly and display the new configuration. If the new configuration is the goal configuration, your program should print "Congratulations!" and exit.
- The user can also input 'q'. With such an input, your program should exit.
- If the user inputs any other characters, your program should print "Illegal input!". You can assume that the user always inputs a character.
Save your program in a file called puzzle.c.
You should test your program to make sure it works properly. But you do not need to submit any tests.

Question 2 [25]

Write a program to do word frequency count. Given a text file, your program will generate a file which consists of an alphabetic listing of the words and the number of times each word appears in the input file.

You will modify the getword function in the notes of Lecture 23 so that it reads a word from a text file.
Your program should keep the list of words in alphabetic order.
Your program should use binary search to decide whether an incoming word is in the current list of words and if not, where to insert that word.
Your program will ask the user to enter the names of the input and output files.
Save your program in a file called frequency.c.
Download the sample text file and save it in a file called sample.txt. Test your program using this file. Call the output file of your program results.dat.

Question 3 [50]

In this question, you will implement a simple grades management system which allows the instructor and students to view and manage the grades for a course.

Your program will read in a grades file, which has the following format.
- The first line contains the instructor's id, which is a 9 digit number.
- The second line contains a list of five names of activities, that is, assignments or exams.
- The next part of the file consists of one line for each activity, and that line contains the total mark and the weight of that activity.
- The rest of the file consists of one line for each student, and that line contains his/her student id and grades for all the activities. If the grades for an activity have not been entered, then the grades of all the students for that activity are 0.
- The following is an example of such a grades file.
```
305021911
A1 A2 A3 Midterm Final
50  10
100 20
100 20
50  15
120 35
921510066  48  63  0  37  0  
921050547  38  60  0  48  0  
921970610  43  55  0  28  0  
931580448  45  96  0  45  0  
...
```
Both instructor and students can use this system. Your program begins with asking the user to input his/her id. If the user inputs an invalid id, your program should print an error message and exit. Otherwise, your program should enter an interactive mode and print a prompt of the form: gms>
The user can interact with your system using the following eight commands. The names of all commands are single characters. Some commands take one or two arguments. The first four commands can be used by both instructor and students. The fifth command can only be used by students. The rest commands can only be used by the instructor. If a user tries to use a command he/she is not authorized for, your program should print an error message.
1. q: exit the system.
2. a: print the list of activity names.
3. s act: print the statistics for the grades for activity act. The statistics include: the minimum, the maximum, the average, the median, and the standard deviation.
4. d act: print the distribution of the percentage grades for activity act. Your program should print the number of students whose percentage grade is 100%, from 90 to 99%, ..., and from 0 to 9%. The percentage grade is the grade divided by the total mark of the activity. The output should have the following form:
```
100%: 1
90-99%: 3
80-89%: 5
...
0-9%: 1
```
5. v act: print the grade of the user for activity act.
6. w stu act: print the grade of student stu for activity act.
7. m stu act: modify the grade of student stu for activity act. Your program should print the current grade, a colon symbol, and then wait for the user to input the new grade.
8. e act: enter the grades for activity act. Your program should allow the user to enter the grades for all the students. For each student, your program should print his/her student number, print a colon symbol, and then wait for the user to input the grade.
You can assume that the only possible errors in user inputs are the following: invalid command name, invalid student id, or invalid activity name. For all these errors, your program should print a corresponding error message. After processing a non-exit command, your program should again print the prompt and process user input.
You can simply use sequential search for your search purposes.
You will need to download the two files for the statistics library: stat_lib.c and stat_lib.h, and store them in your directory for this assignment. To use the library, you should include the following in your program:
#include "stat_lib.h"
Since all the statistical functions are defined over one-dimensional arrays, if your program uses a two-dimensional array to store all the grades, it may need to first copy all the grades for an activity to a one-dimensional array and then call the statistical functions with this array.
Since the median function is defined over a sorted array, your program will need to first sort the array before it calls the function. You can use selection sort for your sorting purpose.
Your program should keep track of whether the grades have been updated. If so, before it exits, your program should write the current grades into the grades file.
Save your program in a file called gms.c.
Compile your program with the following command:
gcc -o gms gms.c stat_lib.c
Download the sample grades file and save it in a file called grades.dat. Test your program using this file to make sure it works properly. But you do not need to submit any tests.

How to submit

Electronic submission

You should submit the files puzzle.c, frequency.c, results.dat, gms.c. You can do this by typing these commands:

tar cvf a4.tar puzzle.c frequency.c results.dat gms.c
gzip a4.tar

Then submit the file a4.tar.gz

Hard-copy submission

You should submit the printout of the files you submit electronically. Also, don't forget to print out a copy of the sample cover page, fill it out, and sign it.