CS1101C Practical Exam

Session 3 (1600 - 1745 hours)

Boggle

The name of your C program file must be called boggle.c, files with any other name will not be marked.

The deadline for this lab is Wednesday 11 April 2007, 17:45:59 hours. Strictly no submissions will be accepted after the deadline.

Background

In the traditional game of Boggle, players try to form words from random letters in a 4 x 4 board.

Board

The game takes place in a 4 x 4 board of letters. A sample board is shown below:

B S P L
I H A M
R C E D
N O T F

For simplicity, each letter can appear at most once in the Boggle board. That means all letters in a Boggle board are unique.

Words

Players try to find words in the Boggle board. Each player searches for words that can be constructed from the letters of that are adjuacent to one another in the board. Here, the meaning of “adjacent” includes horizontally, vertically, and diagonally. Words must be at least three letters long but may not use the same letter more than once per word.

Given the following board of letters (which is the same as the one shown above): 

B S P L
I H A M
R C E D
N O T F

The following are some possible words, but not all of them are valid:

  1. LAP: Valid word because L is adjacent to A and A is adjacent to P.
  2. IS: Invalid word because it is less than three letters long.
  3. MADE: Valid word.
  4. ACTOR: Valid word.
  5. MASHED: Valid word.
  6. TOECAPS: Valid word.
  7. NON: Invalid word because N is used more than once.
  8. DOT: Invalid word because D is not adjacent to O.
  9. GAME: Invalid word because G is not found in the board.

Scoring

Each invalid word is worth zero points. Each valid word is worth points according to the length of the word as shown in the following table:

Word Length
Points
1 - 2
0
3 - 4
1
5
2
6
3
7
5
8 or more
11

Task

Your task is to read the Boggle board of letters from a file called “board.txt”, and read a list of possible words from a file called “words.txt”. Indicate whether each word is invalid or not, and show the number of points for each valid word. Then show the sum of the number of points.

Files

Sample data files have been copied into your directory by the pesetup command.

The file “board.txt” contains the Boggle board in the following format: 

bsPL
IhAm
rceD
nOTf

Each line contains one row of the Boggle board, and the letters can be either lowercase or uppercase. Convert all letters into uppercase. For simplicity, each letter can appear at most once in the Boggle board. That means all letters in a Boggle board are unique.

The file “words.txt” contains the list of possible words in the following format: 

laP
Is
MADE
actor
MaShEd
toeCaps
noN
DoT
gaME

Each line contains one word, and the letters can be either lowercase or uppercase letters. Again, convert all letters into uppercase. Each word in the file has a minimum of one letter and a maximum of twenty letters, and there are an unknown number of words in each file. There is at least one word in each file.

You are not required to handle file I/O errors.

Sample Output

The following is the sample output using the above sample files. Remember that we will test your program with other input files. Do not print the lines “Begin Sample Output” and “End Sample Output”. 
===== Begin Sample Output =====
Boggle board:

B S P L
I H A M
R C E D
N O T F

Valid word: LAP, score: 1.
Invalid word: IS.
Valid word: MADE, score: 1.
Valid word: ACTOR, score: 2.
Valid word: MASHED, score: 3.
Valid word: TOECAPS, score: 5.
Invalid word: NON.
Invalid word: DOT.
Invalid word: GAME.

Total score: 12.
===== End Sample Output =====

You are reminded to follow the sample output exactly; else marks will be deducted.

We will test your programs with other (more complicated) text input files.

Do not use any structures or any form of dynamic memory allocation (using malloc or calloc) in your program, else no credit will be given.

Remember to submit your program frequently using the submit boggle.c command, and check your submission using the check command.

All the best!

UNIX commands

Some useful UNIX commands (in case you forgot what you did in Lab 0):

  1. “dir”: lists all the files in the directory.
  2. “cp a.txt b.txt”: copies a.txt to b.txt.
  3. “mv a.txt b.txt”: moves / renames a.txt to b.txt.
  4. “cat a.txt”: shows the contents of a.txt.