ENGG1110 Problem Solving by Programming (2018-2019 Term 1) Project – Word Search Puzzle
_____________________________________________________________________________________
1. Introduction
A Word Search Puzzle is a classic game to find words hidden in a letter grid, where all the words are provided in a word list.
The letter grid consists of some cells organized in a square or a rectangle shape, where each cell contains a letter. An example is shown as follows:
T |
T |
O |
E |
K |
Y |
A |
Z |
C |
M |
A |
E |
I |
X |
N |
I |
R |
Q |
R |
O |
T |
T |
U |
V |
J |
The word list contains some words to be found in the letter grid. An example is shown as follows:
The words in the word list can be found in one of the 8 directions in the letter grid, i.e., 2 for horizontal (i.e., left to right or right to left), 2 for vertical, and 4 for diagonal. An example is shown as follows:
In this project, your task is to use Code::Blocks in Windows to create a Console Application of a Word Search Puzzle using C language.
TRICK |
OR |
TREAT |
1
2. Program Design
A skeleton code (in SkeletonCode.c) is given and you are required to complete it using Code::Blocks in this project. The program flow is shown as follows:
Start
A
Display letter grid
Word
in word list?
Display appropriate error message
Word matched before?
Read row, column, and direction from console
Word match in letter grid?
Update matching status
Display successful message
Puzzle finish?
Display word list with matching status and winning message
No Read data Yes from file?
Read letter grid from console
Read letter grid from file
Read word list from console
Read word list from file
Initialize matching status in word list
Display word list with matching status
Read input word from console
No
Yes
Yes
No
No Yes
No Yes
A
2
End
3. Schedule
The following shows the suggested schedule, the code submission deadline, and the date for the project demo and presentation:
Week |
Date |
Tasks |
9 |
Oct 31 |
o Print the letter grid and the word list that are read from the console |
10 |
Nov 7 |
o Print the letter grid and the word list that are read from the file the word list or matched before |
11 |
Nov 14 |
o Allow a player to finish the whole puzzle |
12 |
Nov 21 |
o Allow a player to enter the secret code to print the secret table project demo and presentation |
13 |
Nov 26 |
Project Submission (by 23:59 on Blackboard) |
Nov 28 |
Project Demo and Presentation (in the lesson) |
3
4. Detailed Design
4.1 Macros and Variable Declarations
Suppose the macro MAX_GRID is defined in the beginning of the source code: #define MAX_GRID 10
And we have the following in the other part of the source code:
The above will be replaced by
char letterGrid[MAX_GRID][MAX_GRID]
char letterGrid[10][10]
automatically before the source code compiles.
The following table shows the macros defined in the beginning of the skeleton code. They are mainly used for the declarations of arrays and parameters.
Macro |
Value |
Explanation |
MAX_GRID |
10 |
Maximum size of the letter grid, which is a square The value is no larger than 10 |
MAX_WORDLIST |
8 |
Maximum size of the word list |
MAX_WORD |
11 |
Maximum number of bytes of a word in the word list and a word inputted by the user, including the terminating NULL character |
MAX_FILENAME |
260 |
Maximum number of bytes in a filename, including the terminating NULL character |
Your program should run correctly even if the macro values are changed reasonably.
Besides, you cannot use any global variables in this project. In other words, all variables must be declared inside functions.
4.2 Choose Data Source: Console or File?
The program will first ask whether to read the letter grid and the word list from files with the following prompt:
You can assume that the user must input either Y or N. You are required to implement this feature in the main function.
Read data from file [Y/N]?
4
4.3 Read Data from Console
If the user did not choose to read the data from file, the program will simply read the letter grid and the word list from the console. The following two functions have already been implemented in the skeleton code. You are required to study them first and then invoke them from the main function:
int readLetterGridFromConsole(char letterGrid[MAX_GRID][MAX_GRID]) o Read the letter grid from console into the 2D array parameter letterGird
o Return the size of the letter grid
int readWordListFromConsole(char wordList[MAX_WORDLIST][MAX_WORD]) o Read the word list from console into the 2D array parameter wordList
o Return the size of the word list
The program will first ask the user for the size of the letter grid with the following prompt:
You can assume that the input must be an integer of at least 2 but no larger than MAX_GRID. Let the input be gridSize. Then, the program will ask the user for the letter grid with the following prompt:
You can assume that the input must be gridSize lines of uppercase letters, where the number of letters on each line is gridSize. An example is shown as follows (underlined characters in blue are user inputs):
Enter the size of the letter grid:
Enter the letter grid:
Enter the size of the letter grid:
5
Enter the letter grid:
CTOEK YAZCM AEIXN IRQRO TTUVJ
You can assume that:
- gridSize is at least 2 but no larger than MAX_GRID.
- All letters are uppercase letters.
5
After reading the letter grid, the program will ask the user for the size of the word list with the following prompt:
You can assume that the input must be an integer of at least 1 but no larger than MAX_WORDLIST. Let the input be listSize. Then, the program will ask the user for the word list with the following prompt:
You can assume that:
- listSize is at least 1 but no larger than MAX_WORDLIST.
- The length of each word is at least 2 but no longer than MAX_WORD – 1.
- There are no duplicate words in the word list.
- Each word must appear once and only once in the letter grid in one of the 8 directions.
- All letters are uppercase letters.
An example is shown as follows (underlined characters in blue are user inputs):
After reading the word list, we have listSize = 3 and
Enter the size of the word list:
Enter the word list:
Enter the size of the word list:
3
Enter the word list:
TRICK OR TREAT
wordList[0] is “TRICK” wordList[1] is “OR” wordList[2] is “TREAT”
6
4.4 Read Data from File
If the user chose to read the data from file, the program will ask for two filenames and then read the letter grid and the word list from the specified files. You are required to complete and then invoke the following two functions from the main function:
int readLetterGridFromFile(char letterGrid[MAX_GRID][MAX_GRID]) o Read the letter grid from file into the 2D array parameter letterGird
o Return
- the size of the letter grid if successful
- -1 if there is any file reading error
int readWordListFromFile(char wordList[MAX_WORDLIST][MAX_WORD])
o Read the word list from file into the 2D array parameter wordList o Return
the size of the word list if successful -1 if there is any file reading error
The program will first ask the user for the filename of the letter grid with the following prompt:
The file format is described as follows. The first number indicates the size of the grid, denoted as gridSize. Then, there are gridSize lines of uppercase letters, where the number of letters on each line is gridSize. An example is shown as follows:
Enter filename of the letter grid:
LetterGrid.txt |
5 CTOEK YAZCM AEIXN IRQRO TTUVJ |
You can assume that:
1. The length of the filename input by the user is no longer than MAX_FILENAME – 1. 2. The file format must be correct.
3. gridSize is at least 2 but no larger than MAX_GRID.
4. All letters are uppercase letters.
If the file cannot be found or there is any IO error, the program will display the following message and terminate.
Error in reading the letter grid file. Program terminates.
7
After reading the letter grid from the file, the program will ask the user for the filename of the word list with the following prompt:
The file format is described as follows. The first number indicates the size of the list, denoted as listSize. Then, there are listSize words on each line. An example is shown as follows:
You can assume that:
- The length of the filename input by the user is no longer than MAX_FILENAME – 1.
- The file format must be correct.
- listSize is at least 1 but no larger than MAX_WORDLIST.
- The length of each word is at least 2 but no longer than MAX_WORD – 1.
- There are no duplicate words in the word list.
- Each word must appear once and only once in the letter grid in one of the 8 directions.
- All letters are uppercase letters.
After reading the word list, we have listSize = 3 and
If the file cannot be found or there is any IO error, the program will display the following message and terminate.
Enter filename of the word list:
WordList.txt |
3 TRICK OR TREAT |
wordList[0] is “TRICK” wordList[1] is “OR” wordList[2] is “TREAT”
Error in reading the word list file. Program terminates.
8
4.5 Initialize Matching Status
After reading the letter grid and the word list from the console or the files, you are required to initialize the matching status of each word in the word list in the main function. In the skeleton code, the matching status is represented by the following integer array:
int matchingStatus[MAX_WORDLIST];
If an array element is 0, the corresponding word has not been matched. If an array element is 1, the corresponding word has already been matched. For example, suppose listSize is 3 and we have:
That means the word “TREAT” has been matched while the words “TRICK” and “OR” have not.
Before the game starts, all the elements from matchingStatus[0] to matchingStatus[listSize – 1] are initialized to 0. When a word is matched later, the corresponding matchingStatus element will be set to 1.
wordList[0] is “TRICK” wordList[1] is “OR” wordList[2] is “TREAT” |
matchingStatus[0] is 0 matchingStatus[1] is 0 matchingStatus[2] is 1 |
9
4.6 Display Letter Grid and Word List
After initializing the matching status of the word list, the program will display the puzzle on the screen. You are required to complete and then invoke the following two functions from the main function:
void printLetterGrid(char letterGrid[MAX_GRID][MAX_GRID], int gridSize) o Display the letter grid stored in letterGrid of size gridSize
void printWordList(char wordList[MAX_WORDLIST][MAX_WORD], int listSize, int matchingStatus[MAX_WORDLIST])
o Display the word list stored in wordList of size listSize with the matching status for each word (stored in matchingStatus)
An example is shown as follows, where all three words are not matched initially:
### 5 x 5 Letter Grid ### +01234
+++++++ 0+TTOEK 1+YAZCM 2+AEIXN 3+IRQRO 4+TTUVJ
### Word List of Size 3 ### [ ] TRICK
[ ] OR
[ ] TREAT
Suppose the word “TREAT” is matched later, the following will be displayed:
### 5 x 5 Letter Grid ### +01234
+++++++ 0+TTOEK 1+YAZCM 2+AEIXN 3+IRQRO 4+TTUVJ
### Word List of Size 3 ### [ ] TRICK
[ ] OR [X] TREAT
10
4.7 Read Input Word from Console and Check Word List
After displaying the puzzle, the program will ask the user for the word to be matched with the following prompt:
You can assume that the input must be a non-empty string no longer than MAX_WORD – 1. After reading the input word, you are required to complete and then invoke the following function from the main function:
int checkWordList(char wordList[MAX_WORDLIST][MAX_WORD], int listSize,
int matchingStatus[MAX_WORDLIST], char inputWord[MAX_WORD])
o Check whether inputWord is in wordList of size listSize and whether it is matched before o Return
theindexofinputWordinwordList(i.e.,avaluebetween0andlistSize–1inclusively)if inputWord is in wordList and has not been matched before
listSize if inputWord is in wordList but has been matched already -1 if inputWord is not in wordList
If the input word is not in the word list, the program will display the following message:
and then display the prompt again for another user input.
If the input word is in the word list but has already been matched before, the program will display the following message:
and then display the prompt again for another user input.
Enter the word:
The input word is not in the word list.
The input word has already been matched before.
11
4.8 Read Row, Column, and Direction from Console
After reading an input word in the word list that has not been matched before, the program will ask the user for the row number, the column number, and the direction by displaying the following prompt:
Row number
o You can assume that the input must be an integer of a valid row number.
Column number
o You can assume that the input must be an integer of a valid column number.
Direction
o You can assume that the user must input an integer in the range of 1-4 or 6-9. o The mapping of the input integer and the direction is shown as follows:
Examples for the matching are shown in the next subsection. You are required to implement the above in the main function.
Enter the row number, the column number, and the direction (1-4 or 6-9):
12
4.9 Check Letter Grid
After reading the user input, the program will try to match the input word in the specified location and direction in the letter grid. You are required to complete and then invoke the following function from the main function:
int checkLetterGrid(char letterGrid[MAX_GRID][MAX_GRID], int gridSize, char inputWord[MAX_WORD],
int matchRow, int matchCol, int matchDirection)
o Check whether inputWord is in letterGrid in the specified matchRow, matchCol and matchDirection
o Return
- 1 if inputWord is in letterGrid in the specified matchRow, matchCol and
matchDirection
- 0 if inputWord cannot be found in letterGrid in the specified matchRow, matchCol and
matchDirection
- -1 if the search of inputWord exceeds the boundary of the letterGrid
o Example:
+01234 +++++++ 0+TTOEK 1+YAZCM 2+AEIXN 3+IRQRO 4+TTUVJ
inputWord |
matchRow |
matchCol |
matchDirection |
RETURN VALUE |
TRICK |
4 |
0 |
9 (top-right) |
1 (word found) |
TREAT |
4 |
0 |
9 (top-right) |
0 (word not found) |
TRICK |
4 |
0 |
1 (bottom-left) |
-1 (search exceed boundary) |
You may need to invoke this function to print the secret table (see later for details). Hence, it is not recommended for this function to print anything (except debugging messages, if any).
After invoking the above function from the main function, the latter will check the return value, update the corresponding matchingStatus element to 1 (only if the word is found), and display one of the following messages:
The word is found!
The input word cannot be found in the given location.
The search exceeds the boundary of the letter grid.
13
4.10 Check Winning Condition
After matching a word, the program will check whether all the words in the word list are matched:
- If no, go back to “Display Letter Grid and Word List (Section 4.6)” and continue the puzzle.
- If yes, the program will display the word list with a winning message and then terminate. An
example is shown as follows:
### Word List of Size 3 ### [X] TRICK [X] OR [X] TREAT
You have finished the puzzle. Congratulations!
14
5. Secret Table
When the program prompts for the input word and the user enters SECTBL, a secret table will be shown. The secret table contains the correct answer (row, column, and direction) for each word in the word list. After that, the program will prompt for the input word again.
An example is shown as follows (underlined characters in blue are user inputs):
### 5 x 5 Letter Grid ### +01234
+++++++ 0+TTOEK 1+YAZCM 2+AEIXN 3+IRQRO 4+TTUVJ
### Word List of Size 3 ### [ ] TRICK
[ ] OR [X] TREAT Enter the word: SECTBL ### Secret Table ### TRICK: R4 C0 D9 OR: R3 C4 D4 TREAT: R4 C1 D8 Enter the word:
You are not allowed to accept extra input files to get the answers. Instead, please design your own algorithm to find the answers automatically. (Hint: you may find the checkLetterGrid() function useful.)
You are required to implement your algorithm in the following function and then invoke it in an appropriate location:
void printSecretTable(/* put your parameter list here*/)
For the size of the array parameter, you are required to use the macro (in Section 4.1) instead of hard
coding the value.
You can assume that:
- The word list does not contain the word SECTBL.
- MAX_WORD is at least 7 (= length of SECTBL + the terminating NULL character).
Note that the flow chart in “Program Design” does not include the secret table.
15
6. Sample Run
A sample run is shown as follows (underlined characters in blue are user inputs) for your reference. Blank lines are added to improve the readability, it is not necessary for your program to include them.
Read data from file [Y/N]?
N
Enter the size of the letter grid:
10
Enter the letter grid:
OSAMPLEOOO OOOOOOOOOO OOOOOOOOOO OOOOOOOOOO OOOOOOOOOO OOOOOOOOOO OOOOOOOOOO OOOOOOOOOO OOOOOOOOOO OOOOOOONUR Enter the size of the word list: 2
Enter the word list:
SAMPLE RUN
### 10 x 10 Letter Grid ### +0123456789 ++++++++++++ 0+OSAMPLEOOO 1+OOOOOOOOOO 2+OOOOOOOOOO 3+OOOOOOOOOO 4+OOOOOOOOOO 5+OOOOOOOOOO 6+OOOOOOOOOO 7+OOOOOOOOOO 8+OOOOOOOOOO 9+OOOOOOONUR
### Word List of Size 2 ### [ ] SAMPLE [ ] RUN Enter the word:
SAMPLE
Enter the row number, the column number, and the direction (1-4 or 6-9):
016
The word is found!
16
### 10 x 10 Letter Grid ### +0123456789 ++++++++++++ 0+OSAMPLEOOO 1+OOOOOOOOOO 2+OOOOOOOOOO 3+OOOOOOOOOO 4+OOOOOOOOOO 5+OOOOOOOOOO 6+OOOOOOOOOO 7+OOOOOOOOOO 8+OOOOOOOOOO 9+OOOOOOONUR
### Word List of Size 2 ### [X] SAMPLE [ ] RUN Enter the word:
SAMPLE
The input word has been matched already.
### 10 x 10 Letter Grid ### +0123456789 ++++++++++++ 0+OSAMPLEOOO 1+OOOOOOOOOO 2+OOOOOOOOOO 3+OOOOOOOOOO 4+OOOOOOOOOO 5+OOOOOOOOOO 6+OOOOOOOOOO 7+OOOOOOOOOO 8+OOOOOOOOOO 9+OOOOOOONUR
### Word List of Size 2 ### [X] SAMPLE [ ] RUN Enter the word:
RU
The input word is not in the word list.
### 10 x 10 Letter Grid ### +0123456789 ++++++++++++ 0+OSAMPLEOOO 1+OOOOOOOOOO 2+OOOOOOOOOO 3+OOOOOOOOOO 4+OOOOOOOOOO 5+OOOOOOOOOO 6+OOOOOOOOOO 7+OOOOOOOOOO 8+OOOOOOOOOO 9+OOOOOOONUR
### Word List of Size 2 ### [X] SAMPLE [ ] RUN Enter the word:
RUNE
The input word is not in the word list.
17
### 10 x 10 Letter Grid ### +0123456789 ++++++++++++ 0+OSAMPLEOOO 1+OOOOOOOOOO 2+OOOOOOOOOO 3+OOOOOOOOOO 4+OOOOOOOOOO 5+OOOOOOOOOO 6+OOOOOOOOOO 7+OOOOOOOOOO 8+OOOOOOOOOO 9+OOOOOOONUR
### Word List of Size 2 ### [X] SAMPLE [ ] RUN Enter the word:
RUN
Enter the row number, the column number, and the direction (1-4 or 6-9):
976
The input word cannot be found in the given location.
### 10 x 10 Letter Grid ### +0123456789 ++++++++++++ 0+OSAMPLEOOO 1+OOOOOOOOOO 2+OOOOOOOOOO 3+OOOOOOOOOO 4+OOOOOOOOOO 5+OOOOOOOOOO 6+OOOOOOOOOO 7+OOOOOOOOOO 8+OOOOOOOOOO 9+OOOOOOONUR
### Word List of Size 2 ### [X] SAMPLE [ ] RUN Enter the word:
RUN
Enter the row number, the column number, and the direction (1-4 or 6-9):
996
The search exceeds the boundary of the letter grid.
18
### 10 x 10 Letter Grid ### +0123456789 ++++++++++++ 0+OSAMPLEOOO 1+OOOOOOOOOO 2+OOOOOOOOOO 3+OOOOOOOOOO 4+OOOOOOOOOO 5+OOOOOOOOOO 6+OOOOOOOOOO 7+OOOOOOOOOO 8+OOOOOOOOOO 9+OOOOOOONUR
### Word List of Size 2 ### [X] SAMPLE [ ] RUN Enter the word:
SECTBL
### Secret Table ### SAMPLE: R0 C1 D6 RUN: R9 C9 D4 Enter the word:
RUN
Enter the row number, the column number, and the direction (1-4 or 6-9):
994
The word is found! ### Word List of Size 2 ### [X] SAMPLE [X] RUN You have finished the puzzle. Congratulations!
19
7. Academic Honesty and Declaration Statement
Attention is drawn to University policy and regulations on honesty in academic work, and to the disciplinary guidelines and procedures applicable to breaches of such policy and regulations. Details may be found at https://www.cuhk.edu.hk/policy/academichonesty/.
Please place the following declaration statement as the comment in the beginning of your .c source code and fill in your information.
/**
* ENGG1110 Problem Solving by Programming *
* Course Project
*
- * I declare that the project here submitted is original
- * except for source material explicitly acknowledged,
- * and that the same or closely related material has not been
- * previously submitted for another course.
- * I also acknowledge that I am aware of University policy and
- * regulations on honesty in academic work, and of the disciplinary
- * guidelines and procedures applicable to breaches of such
- * policy and regulations, as contained in the website. *
- * University Guideline on Academic Honesty:
- * https://www.cuhk.edu.hk/policy/academichonesty/ *
* Student Name : <your name>
* Student ID : <your student ID>
* Class/Section : <your class/section> * Date : <date>
*/
8. Testing Platform
Your submission will be graded by using Code::Blocks in Windows. Please note that there may be some problems in opening a project in Windows if the project is created in other operating systems, such as macOS and Linux.
9. Submission
The deadline of the project submission is Nov 26 (Mon) 23:59. Please follow the following steps to submit your work.
- Compress your whole Code::Blocks project folder into a file in ZIP format named as: ENGG1110<your class/section>_<your student ID>.zip (E.g., ENGG1110G_1155012345.zip)
- Visit Blackboard for CUHK and login with your OnePass (CWEM) password.
- Visit the page for ENGG1110 and go to ProjectProject Submission.
- Upload and submit your file prepared in Step 1.
- Download your submission from Blackboard to see if it can be extracted and then opened by
Code::Blocks in Windows successfully.
Resubmissions are allowed. But only the latest one will be graded. 10% of the project marks will be deducted for late submissions within one week (i.e., by Dec 3 (Mon) 23:59). Late submissions more than one week will not be graded.
20
10. Project Demo and Presentation
The project demo and presentation is scheduled on Nov 28 (Wed) in the lesson. It is conducted in English. Each student will need to:
- Compile and execute the program on a lab computer using Code::Blocks in Windows.
- Explain the code and the program design
This part contributes 10% of the project marks. Marks for this part will only be given during the project demo and presentation. Even if your project is incomplete or you plan to submit the project late, you should still come and try to get some marks. However, a student who is absent on that day will get 0 marks for this part.
– END – 21