CSCI1120 Introduction to Computing Using C++, Fall 2019/20
Department of Computer Science and Engineering, The Chinese University of Hong Kong
Assignment 4: Word Search Puzzles
Due: 20:00, Sat 9 Nov 2019 File name: wordsearch.cpp Full marks: 100
Introduction
The objective of this assignment is to let you practice using arrays and pointers. You will implement a computer program for solving word search puzzles, where words from a dictionary are to be found in a two-dimensional array of letters. For example, you might be given the following array in Figure 1(a) and your program is to find words from the dictionary that can be spelled out in the puzzle by starting at any character, then moving in a straight line right or down. In other words, the program performs two scanning phases: (1) horizontal scanning from left to right on every row, starting from row 0; and (2) vertical scanning from top to bottom on every column, starting from column 0. Horizontal scanning is done before vertical scanning. For example, in phase (1), the word “walk” is found at row 3 as Figure 1(b) depicts; in phase (2), the same word “walk” is found in a vertical sense at column 1 in Figure 1(c). Word matching in diagonal senses is not required in this program.
012345678 012345678 012345678 000 111 222 333 444 555 666 777 888
(a) (b) (c) Figure 1: An Example Word Search Puzzle
Figure 2(a) and (b) show all the words found in phases (1) and (2) respectively. Figure 2(c) shows the combined result of the two phases (words found highlighted in red). Since our output is displayed on a colourless console screen, we will capitalize letters of each word found in the program output.
012345678 012345678 012345678 000 111 222 333 444 555 666 777 888
(a) (b) (c) Figure 2: An Example Solved Word Search Puzzle
beerixape jrbteenag hkithbswy rwalkingh paixldzkq tlmlqiyjy akhapfabg hxmshwyny ujfjhrsot
beerixape jrbteenag hkithbswy r ingh paixldzkq tlmlqiyjy akhapfabg hxmshwyny ujfjhrsot
beerixape jrbteenag hkithbswy r alkingh p ixldzkq t mlqiyjy a hapfabg hxmshwyny ujfjhrsot
walk
w a l k
beerixape jrbteenag hkithbswy rh paixldzkq tlmlqiyjy akhapfabg hxmshwyny ujfjhrsot
Copyright © 2019 CSE, CUHK
Page 1 of 10
beerixape jrbteenag hkith swy rlkngh pxlzkq t lqiyjy a hapfabg hxmshwyny ujfjhrsot
BEERixape jrbTEENag hKIThBswy rWALKINGh pAIxlDzkq tLMlqiyjy aKhapfabg hxmshwyny ujfjhrsot
b i d
w a l k
a i m
wal
k
ing
CSCI1120 Introduction to Computing Using C++, Fall 2019/20
Department of Computer Science and Engineering, The Chinese University of Hong Kong
The program will also list every word found and the row or column it is located as follows:
row 0: bee
row 0: beer
row 1: teen
row 2: kit
row 3: walk
row 3: walking
row 3: king
col 1: walk
col 2: aim
col 5: bid
For the exact format of the output required, please refer to the Sample Runs section. What’s worth noting is that some word may be comprised of other words. For example, the word “walking” contains two other words “walk” and “king”. These should be counted as three matches.
Data Files
In this assignment, the program needs to read some text files to obtain the input data. There are two types of files needed:
Dictionary
The dictionary used for checking words in this program is contained in a text file of the following format. On the first line (the header line), the two numbers denote the total number of words and the length of the longest word in the dictionary. All words are stored on second line through the last line.
3964 10
act
add
age
…
bad
bag
…
able
acid
…
baby
back
…
zone
zoom
about
above
…
youth
zebra
zippy
abroad
absorb
…
xenophobia
xylography
Copyright © 2019 CSE, CUHK Page 2 of 10
CSCI1120 Introduction to Computing Using C++, Fall 2019/20
Department of Computer Science and Engineering, The Chinese University of Hong Kong
You may assume that the list of dictionary words has always been sorted in (1) ascending word length, and (2) then in alphabetic order. So, shorter words always appear earlier than longer words. For words of the same length, they are sorted in lexicographical order, e.g. “act” < “add”, “youth” < “zebra”, etc.There are two given sample dictionary files, namely dict.txt and dictbig.txt, for your program testing. The first file contains 3964 words; the longest word in it has 10 letters. The second file has 370103 words and 31 letters in its longest word. Your program should prompt the user to choose a dictionary file at the very beginning of the runtime.PuzzleA puzzle in form of a 2D board is contained in a data file in the following format. On the first line (the header line), the two numbers denote the number of rows and columns of the “puzzle game board”. In this example, 8 means there are 8 rows, or in other words, 8 letters on each column; 12 means there are 12 columns, or in other words, 12 letters per row. All the space characters in this file will be ignored when the data is being loaded into a 2D array in your program. 8 12 bearihappyen jvsteenagers xitthnswydxc rrulyenghost ptdxldzkqbte tuilqiyjxfwr aeoapfaither hxmshwynotea Helper FunctionsYou don’t need to write any code related to file I/O which is not yet taught. We have provided all the necessary functions to help you read these files into 2D arrays in the helper.cpp source file. Include the header file helper.h in your source file by adding the following line:#include “helper.h”The helper header file defines the following function prototypes. Please look at the comments in thehelper.cpp source file to understand how to use them.• char** create2DArray(int rows, int cols);• voiddelete2DArray(char**array,introws);• char** getDictionary(const char* filename, int& words, int& wlen);• char** getPuzzle(const char* filename, int& rows, int& cols);• voidbuildIndexes(char**dict,intwords,intwlen,intindexes[][26]);• void printIndexes(int indexes[][26], char** dict, int str, int end);This header file also defines three global constants that may be useful later.• const int MIN_WORD = 3; // length of the shortest word to search• const int MAX_WORD = 50; // length of longest possible word in a dictionary• const int MAX_FILENAME = 1000; // maximum length of a file nameCopyright © 2019 CSE, CUHK Page 3 of 10CSCI1120 Introduction to Computing Using C++, Fall 2019/20Department of Computer Science and Engineering, The Chinese University of Hong KongFor example, to read a dictionary file into a 2D array, it is as simple as calling the getDictionary() function with the dictionary filename as input. This function will return a pointer to a 2D array loaded with all words read from the dictionary file. It will also pass back the total number of words and the length of the longest word in the dictionary to the caller via the reference parameters words and wlen.char** dict = getDictionary(filename, words, wlen);Then you can read or write each element in the array dict by accessing dict[i][j] for some rowindex i and column index j.Note: dict is of char** type. That means it is a pointer to pointer type. In C/C++, a 2D array can be viewed as a 1D array of pointers, each of which stores the address of the first element of an 1D array corresponding to each row of the 2D array.Note: If you run on XCode, uncomment the line //#define XCODE in the helper.h header file. Program SpecificationThis section describes the requirements, program design, function decomposition, game flow, etc.Assumptions1. You may also assume that both the puzzle and the dictionary consist of only lowercase letters.2. Youmayassumethatthewordtosearchisalwaysatleast3letterslongandatmostwlenletters long, where wlen is the length of the longest word defined in a dictionary file. For your information, the longest word in any of the world’s major English dictionaries is 45 letters only. So, we assume that wlen is always bounded by 50. Using our sample dictionary file dict.txt (or dictbig.txt), wlen is 10 (or 31) only. The global constants MIN_WORD and MAX_WORD declared in the helperheader are set to 3 and 50 respectively.RestrictionsThere is something to avoid in your implementation or else marks will be deducted:• Don’t use global variables (variables declared outside any functions). However, you can use globalconstants for easier scaling and code maintainability.• Don’t use the std::string class but char arrays or char pointers in your code. (Exception: thehelper.cpp has some code using std::string for processing the input data.)• Non-standard C++ or third-party library functions are not allowed. However, standard library functions for processing C-strings are allowed, e.g. you may use the strlen() function (defined in
file can also be used if you find them fit.
• The use of the helper source is not optional but mandatory. That means, you should not reinvent
your own functions for doing file reading, say, which will complicate our grading.
• Don’t modify or add any code to the helper.h and helper.cpp files because they won’t be included in your submission. You must implement your program all inside the wordsearch.cpp
file which is the only file to be submitted.
Copyright © 2019 CSE, CUHK Page 4 of 10
CSCI1120 Introduction to Computing Using C++, Fall 2019/20
Department of Computer Science and Engineering, The Chinese University of Hong Kong
Required Functions
Your program must contain the following functions. They must be called somewhere in your program. You must not modify the prototypes of all these functions. You can design extra functions if needed.
void search(char** puzzle, int rows, int cols, char** dict, int words, int wlen,
int indexes[][26], char** solved_puzzle,
bool vertical = false);
This function is the core function to perform the word search process (corresponding to the horizontal scanning phase we mentioned). The puzzle parameter points to the puzzle array loaded with the input data read from the puzzle data file. The parameters rows and cols tell the dimensions of the puzzle array. The indexes parameter refers to a 2D array of integer type passed from the caller. This array is used to index the dictionary, thus speeding up dictionary lookups. We will give more details on this later. The solved_puzzle parameter points to a new array whose elements are copied from the puzzle array (pointed by puzzle) with letters of each word found in the puzzle capitalized. If your program design is to capitalize each word found in-place in the original puzzle array, then the usage of this parameter can be skipped. In this case, you may just pass a null pointer (NULL or nullptr) as its value from the caller. Finally, the Boolean parameter vertical (with default value false) is used to allow the caller to signify (by setting to true) to this function body that the search is now in a vertical scanning phase, and some behavior may need to change, e.g. replace “row” by “col” in the printout, if necessary. It is up to you whether to use and how to use the last two parameters.
void transpose(char** a, char** b, int rows, int cols);
In linear algebra, transpose is an operation that flips a matrix by switching its rows with its columns. This function transposes array a into array b. The parameters rows and cols are the dimension of array a. That is, a is a rows-by-cols array. The caller of this function has to pass in a cols-by-rows array b. Transpose here means the rows of the source array become columns of the destination array as depicted in Figure 3 below. You may need to create a new 2D array to store the transposed array elements. In this case, you may simply reuse the create2DArray() function provided in helper.cpp. Note also that transposing an array twice just returns the original array unchanged. Why we need this function is that we don’t want to implement another search function to do vertical scanning. Suppose the above search function implements horizontal scanning. We can simply reuse it to scan vertically as well by passing to it a transposed puzzle array and true for the vertical flag.
11
0123456789 0 1 01234567
array a
00 11
2 transpose. 2 33
44 55 66 77
8
9 10 11
Figure 3: Transpose of a 8-by-12 array
b earihappyen j vsteenagers x itthnswydxc r rulyenghost p tdxldzkqbte t uilqiyjxfwr a eoapfaither h xmshwynotea
b jxrptah e virtuex a studiom r ttlxlas i ehylqph h enedifw a nsnzyay p awgkjin p gyhqxto y edobfht e rxstwee n scterra
Copyright © 2019 CSE, CUHK
Page 5 of 10
array b
CSCI1120 Introduction to Computing Using C++, Fall 2019/20
Department of Computer Science and Engineering, The Chinese University of Hong Kong
void print2DArray(char** arr, int rows, int cols);
This function prints a puzzle array arr to the screen. Refer to the Sample Runs section for the expected format of the output.
Using Index Table for Faster Dictionary Lookup (worth 10% marks)
A dictionary may have tens of thousand words. Scanning the dictionary array from top to bottom sequentially to check for each search string in the puzzle is sort of slow or wasteful of compute cycles. In real applications that require dictionary search, they usually employ advanced data structures like tries, trees or hash tables to minimize the need or scope of sequential scanning. Those are beyond the level of this course. In this assignment, we will use a simple approach to indexing the dictionary for faster lookup by means of looking up another table (actually a 2D integer array) called indexes for shortcuts leading to a more relevant range of dictionary words, thus bypassing necessary checks. This method works under the assumption that the dictionary has been sorted in (1) ascending word length, and (2) then in alphabetic order. The structure of this index array is shown in Figure 4 below.
Figure 4: Index Table
As we have assumed, lengths of strings to search vary between 3 to wlen (=10 in this example). Each length value in this range corresponds to one row in the index table. For each row, we have 26 indexes referring to ‘a’ to ‘z’. They store the locations (i.e. array indexes) of the first words in the dictionary array that begin with letter ‘a’, ‘b’, … ‘z’, respectively. For example, indexes[3][2] stores the array index of the first word of 3 letters starting with the letter ‘c’ (0=’a’, 1=’b’, 2=’c’, and so on) in the dictionary array. Suppose your search string is “zoex” (4 letters long start with ‘z’), you can locate the index at indexes[4][25], which stores 852, and directly jump to the entry dict[852] (“zany”) to do the matching for a dictionary array dict. This helps skip all the preceding 851 words in dict that have no chance to match with the search string.
Copyright © 2019 CSE, CUHK Page 6 of 10
CSCI1120 Introduction to Computing Using C++, Fall 2019/20
Department of Computer Science and Engineering, The Chinese University of Hong Kong
Our helper code has provided the functions buildIndexes() and printIndexes() (for verification). You just need to call them to build or print the indexes array. You may declare an int array indexes of MAX_WORD + 1 rows and 26 columns, and pass it to the buildIndexes() function. Then the array will be filled with dictionary index values. One more thing is that if the dictionary has no words of 10 letters starting with ‘z’, then indexes[10][25] will store -1 (as every element was initialized to -1 in the beginning of the index building process). Think about what to do when hitting -1 in indexes. Note also that indexes[0] to indexes[2] and those rows beyond indexes[wlen] are not used. The user of this index table has to skip them. When calling the search() function, you should pass the indexes array to it, so that you can use it to speed up dictionary lookup in the function body. The performance benefit may not be obvious when using a small dictionary, but it becomes more evident when the dictionary is big. If you decide to give up using this index mechanism, you may just pass a null pointer (NULL or nullptr) as the indexes parameter for the search() function. But this means that you will get 90 marks at most in this assignment because this part is worth 10%.
Program Flow
The program flow is described as follows. You should call all the functions required above to aid your implementation.
1. The program starts asking the user to enter the file name of a dictionary file.
2. Load the data of the dictionary file into a dictionary array.
3. Build the index table (an int array) for the dictionary array.
4. Ask the user to enter the file name of a puzzle.
5. Load the data of the puzzle file into a puzzle array.
6. Perform horizontal scanning on the puzzle array for each possible word (from shortest to longest)
by looking up the word from the dictionary array.
a. for each search word w at a location in the puzzle,
i. locate the element in the dictionary array that corresponds to the first word having the same length and first letter as w using the index table.
ii. compare w with all words of the same length in the dictionary array.
iii. If matched, print w with its location (which row it lies) and capitalize its letters in the puzzle
array. (and skip comparing with the rest of the dictionary)
b. increment the search word length and repeat (a) until it hits the puzzle’s width.
c. move on to the next position in the same row, and repeat (a)-(b).
d. move on to the next row, and repeat (a)-(c).
7. Transpose the puzzle array.
8. Perform step 6 again, but printing “col” instead of “row” for the location of each word found. This
in effect achieves the vertical scanning phase.
9. Transpose the puzzle array again.
10. Print the solved puzzle array.
11. Delete the puzzle array.
12. Ask the user whether to play with another word search puzzle (y/n).
13. Repeat steps 2-12 while the user answers ‘y’es.
14. Delete the dictionary array.
In the above flow, the steps highlighted in blue are related to the use of the index table for speeding up the dictionary lookup process.
Copyright © 2019 CSE, CUHK Page 7 of 10
CSCI1120 Introduction to Computing Using C++, Fall 2019/20
Department of Computer Science and Engineering, The Chinese University of Hong Kong
Sample Runs
In the following sample runs, the blue text is user input and the other text is the program printout. You can try the provided sample program for other input. Your program output should be exactly the same as the sample program (same text, symbols, letter case, spacings, etc.) except for printing a possible trailing space at the end of each line. Please refer to the output produced by our provided sample program executable if there exists any discrepancy between its output and this document. Assume that files xyz and abc below are not existent. It is normal that accidental mixing up of dictionary files and puzzle data files may crash the program. You need not test against this issue.
Enter dictionary file name: xyz File xyz could not be opened
(Program ends with code 1)
Enter dictionary file name: dictbig.txt
Dictionary loaded with 370103 words; longest word: 31 letters Enter puzzle data file name: abc
File abc could not be opened
(Program ends with code 1)
Enter dictionary file name: dict.txt
Dictionary loaded with 3964 words; longest word: 10 letters Enter puzzle data file name: data1.txt
Words found:
row 0: bee
row 0: beer
row 1: teen
row 2: kit
row 3: walk
row 3: walking
row 3: king
col 1: walk
col 2: aim
col 5: bid
Puzzle solved: BEERixape jrbTEENag hKIThBswy rWALKINGh pAIxlDzkq tLMlqiyjy aKhapfabg hxmshwyny ujfjhrsot
Continue with next puzzle? (y/n): y Enter puzzle data file name: data2.txt
Words found:
row 0: bear
Copyright © 2019 CSE, CUHK
Page 8 of 10
CSCI1120 Introduction to Computing Using C++, Fall 2019/20
Department of Computer Science and Engineering, The Chinese University of Hong Kong
row 0: ear
row 0: happy
row 1: teen
row 1: teenage
row 1: teenager
row 1: age
row 3: ghost
row 3: host
row 6: faith
row 6: the
row 6: her
row 7: not
row 7: note
row 7: tea
col 1: virtue
col 2: studio
Puzzle solved: BEARiHAPPYen jVSTEENAGERs xITthnswydxc rRUlyenGHOST pTDxldzkqbte tUIlqiyjxfwr aEOapFAITHER hxmshwyNOTEA
Continue with next puzzle? (y/n): y Enter puzzle data file name: data3.txt
Words found:
row 0: hide
row 4: tea
row 7: long
row 8: hat
row 12: toe
col 1: its
col 2: and
col 7: teen
col 8: and
Puzzle solved: ureHIDEoiof nsisraeftgs dgemseziiel cysptnshrre gjnznfiyTEA tyarotbiola ftyeetnoArn iuorteLONGf vHATrsaTDte tlNsoraEien teDtnoeEopn lIscpsnNqpn hTOEorhnitf hSatfoouiwt
Copyright © 2019 CSE, CUHK
Page 9 of 10
CSCI1120 Introduction to Computing Using C++, Fall 2019/20
Department of Computer Science and Engineering, The Chinese University of Hong Kong
Continue with next puzzle? (y/n): n (Program ends with code 0)
Program Testing
We have provided some puzzle data files for your program testing. You may also create your own ones based on our specified format (on page 3) for further testing. For dictionary files, you may simply use either dict.txt or dictbig.txt that we provided. The above sample output assumes that the files are in a right folder that your program executable can locate and open. Our coming tutorial will cover where to put the data files when using Visual Studio and Xcode.
Submission and Marking
➢ Your program file name should be wordsearch.cpp. Submit this file only (skip all those helper source and data files) in Blackboard (https://blackboard.cuhk.edu.hk/).
➢ Insert your name, student ID, and e-mail as comments at the beginning of your source file.
➢ You can submit your assignment multiple times. Only the latest submission counts.
➢ Your program should be free of compilation errors and warnings.
➢ Your program should include suitable comments as documentation.
➢ Do NOT plagiarize. Sending your work to others is subject to the same penalty as the copying student.
Copyright © 2019 CSE, CUHK Page 10 of 10
Reviews
There are no reviews yet.