Tutorial7(Assignment4)
CSCI 1120
Introduction to Computing Using C++
Tutorial 7
WANG Fangzhou
Email : fzwang@cse.cuhk.edu.hk
QI Lu
Email : luqi@cse.cuhk.edu.hk
28th Oct, 2019
1
Table of contents
● Complementary Knowledge
○ C string
○ 2D array and char**
○ Case conversion
● Assignment 4
○ Introduction
○ Input & output requirements
○ Helper functions
○ Required Functions
○ Restrictions
● Indexes array for faster dictionary lookup(10% marks)
2
Complementary Knowledge
(1) C string
Examples:
● char str1[6] = {‘H’, ‘e’, ‘l’, ‘l’, ‘o’, ‘\0’};
● char str2[] = “Hello”;
● If you look into the memory, the
above str1 and str2 should look the
same. (As the right figure shows)
Strings are actually one-dimensional array of characters
terminated by a null character ‘\0’
3
Complementary Knowledge
(1) C string
How can we get the length of a cstring?
Ans : strlen ( const char * str ) returns the
length of the C string str.
The function is from
4
Example:
char str[10] = “WFZ”;
cout << strlen(str) << endl; // will print 3
char str[10] = “”;
cout << strlen(str) << endl; // will print 0
Complementary Knowledge
(2) 2D array and char**
Static 2D array:
int c[2][3] = {{1, 2, 3}, {4, 5, 6}};
char matrix1[3][3] = { {'a', 'b', 'c'}, {'d', 'e', 'f'}, {'c', 's', 'e'}};
char matrix2[3][3] = { {'a', 'b', 'c'}, {'d', 'e', '\0'}, {'c', ‘\0', 'e'}};
What will be the output if you cout matrix1[0] ?
1 2 3
4 5 6
c :
matrix1:
'a' 'b' 'c'
'd' 'e' 'f'
'c' 's' 'e'
matrix2:
'a' 'b' 'c'
'd' 'e' '\0'
'c' '\0' 'e'
Ans: abcdefcse + some random sequence until we luckily hit a '\0'
5
Complementary Knowledge
(2) 2D array and char**
Static 2D array:
int c[2][3] = {{1, 2, 3}, {4, 5, 6}};
char matrix1[3][3] = { {'a', 'b', 'c'}, {'d', 'e', 'f'}, {'c', 's', 'e'}};
char matrix2[3][3] = { {'a', 'b', 'c'}, {'d', 'e', '\0'}, {'c', ‘\0', 'e'}};
What about matrix2[0], matrix2[1], matrix2[2] ?
1 2 3
4 5 6
c :
matrix1:
'a' 'b' 'c'
'd' 'e' 'f'
'c' 's' 'e'
matrix2:
'a' 'b' 'c'
'd' 'e' '\0'
'c' '\0' 'e'Ans: abcde ; de ; c
6
Complementary Knowledge
(2) 2D array and char**(con’t)
Dynamic 2D array:
char* : pointer to char
char**�pointer to pointer to char
How to visit a char via char** ?
Assume p is a char**,
p[0]: a char* pointing to certain address
p[0][0]: the char in the address pointed by p[0]
p[0][1]: the char in the address pointed by (p[0] + 1) Example of char**
7
Complementary Knowledge
(3) Case conversion Example:(i)
char upper = 'a' - 32;
cout << upper; // prints A
(ii)
char lower = 'B' + 32;
cout << lower; // prints b
8
…
Difference = 32
Complementary Knowledge
(3) Case conversion
From
Uppercase to lowercase: int tolower(int c)
Lowercase to uppercase: int toupper(int c)
Note: Since the return value of the above functions is
int, type conversion may be involved.
Example:
(i)
char str[] = “Test”;
for(int i = 0; i <= 3; i++)
{
cout << (char)tolower( str[i] );
}
Output: test
(ii)
char str[] = “Test”;
for(int i = 0; i <= 3; i++)
{
cout << (char)toupper( str[i] );
}
Output: TEST
9
Assignment 4: Word Search Puzzles
(1) Introduction
Given:
I. A matrix consisting of
lowercase alphabets
II. A dictionary containing some
words (we call it “legal words”
for convenience)
Matrix example
3964 10
act
add
...
able
acid
...
zippy
absorb
...
xenophobia
xylography
Dictionary example
10
Assignment 4: Word Search Puzzles
(1) Introduction
Matrix example
3964 10
act
add
...
able
acid
...
zippy
absorb
...
xenophobia
xylography
Dictionary example
Want to:
I. Find all legal words in the matrix
(Scan for each row and column)
One hit: bee
11
Assignment 4: Word Search Puzzles
(1) Introduction
Matrix example
3964 10
act
add
...
able
acid
...
zippy
absorb
...
xenophobia
xylography
Dictionary example
Want to:
I. Find all legal words in the matrix
(Scan for each row and column)
Another hit: beer
12
Assignment 4: Word Search Puzzles
(1) Introduction
Matrix example
3964 10
act
add
...
able
acid
...
zippy
absorb
...
xenophobia
xylography
Dictionary example
Want to:
I. Find all legal words in the matrix
(Scan for each row and column)
13
Assignment 4: Word Search Puzzles
(1) Introduction
Matrix example
3964 10
act
add
...
able
acid
...
zippy
absorb
...
xenophobia
xylography
Dictionary example
Want to:
I. Find all legal words in the matrix
(Scan for each row and column)
14
Assignment 4: Word Search Puzzles
(1) Introduction
Matrix example
3964 10
act
add
...
able
acid
...
zippy
absorb
...
xenophobia
xylography
Dictionary example
Want to:
I. Find all legal words in the matrix
(Scan for each row and column)
15
Assignment 4: Word Search Puzzles
(1) Introduction
Matrix example
3964 10
act
add
...
able
acid
...
zippy
absorb
...
xenophobia
xylography
Dictionary example
Want to:
I. Find all legal words in the matrix
(Scan for each row and column)
16
Assignment 4: Word Search Puzzles
(1) Introduction
Matrix example
3964 10
act
add
...
able
acid
...
zippy
absorb
...
xenophobia
xylography
Dictionary example
Want to:
I. Find all legal words in the matrix
(Scan for each row and column)
17
Assignment 4: Word Search Puzzles
(1) Introduction
Matrix example
3964 10
act
add
...
able
acid
...
zippy
absorb
...
xenophobia
xylography
Dictionary example
Want to:
I. Find all legal words in the matrix
(Scan for each row and column)
18
Assignment 4: Word Search Puzzles
(1) Introduction
Matrix example
3964 10
act
add
...
able
acid
...
zippy
absorb
...
xenophobia
xylography
Dictionary example
Want to:
I. Find all legal words in the matrix
(Scan for each row and column)
19
Assignment 4: Word Search Puzzles
(1) Introduction
Want to:
I. Find all legal words in the matrix
(Scan for each row and column)
II. Capitalize those words in the
matrix
20
Assignment 4: Word Search Puzzles
(2) Input & Output requirement
Input:
The matrix to be solved and dictionary will be stored in two
text files(eg: data1.txt, dict.txt).
Output:
(1) Print words with their row/col number
(2) Print the solved matrix(with words capitalized)
Notes: For interaction part, please refer to the assignment
specification for detail (Sample Run section)
21
Assignment 4: Word Search Puzzles
(2) Input & Output requirement
File structure(where to put data files?)
For visual studio user:
The data files should be put in the project folder, at
the same directory level with the source files.
22
Assignment 4: Word Search Puzzles
(2) Input & Output requirement
File structure(where to put data files?)
For Xcode user:
Pay attention to where the executable files are
generated. And put the data files at the same directory
level with the executable file.
For reference(Xcode):
https://www.youtube.com/watch?v=JM1D0yxAYHk
Notes: You can also choose to place the data files in
another folder, and use absolute path to locate those
data files, e.g. typing C:\Users\xxxx\Desktop\datafiles\dict.txt
23
https://www.youtube.com/watch?v=JM1D0yxAYHk
Assignment 4: Word Search Puzzles
(3) Helper Functions
helper.h and helper.cpp will be provided to help you with the assignment.
24
Example of using helper functions:
Assignment 4: Word Search Puzzles
(3) Helper Functions
25
Notes: Do remember to call delete2DArray when you will no longer use it. (To avoid memory leaks )
More: https://www.geeksforgeeks.org/memory-leak-in-c-and-how-to-avoid-it/
https://www.geeksforgeeks.org/memory-leak-in-c-and-how-to-avoid-it/
Note: If you run on XCode, uncomment the line //#define XCODE in the helper.h header file.
Assignment 4: Word Search Puzzles
(3) Helper Functions
26
Assignment 4: Word Search Puzzles
(4) Required Functions
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 will search the puzzle according to the given dictionary dict in
one direction(either horizontally or vertically).
• And indexes (we will talk about it later) can help to increase the matching
speed. Result will be stored in solved_puzzle and you can specify the
searching direction via vertical.
Notes: The vertical flag may be used to control whether you output “row” or
“col” when you found a match. (But you are free to use it in other ways)
27
Assignment 4: Word Search Puzzles
(4) Required Functions
void transpose (char** a, char** b, int rows, int cols);
Transpose is an operation that flips a matrix
by switching its rows with its columns.
Intuition:
Searching a matrix A vertically equals
searching the transpose of A horizontally.
So that we will not need to write another
function to search matrix vertically.
28
Assignment 4: Word Search Puzzles
(4) Required Functions
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.
Notes: You must not modify the prototypes of the aforementioned functions.
29
Assignment 4: Word Search Puzzles
(5) Restrictions
• No global variables (except global constants)
• Don’t use std::string class in your code. Use char arrays or char pointers instead.
• No Non-standard C++ or third-party library functions. But standard library functions
for processing C-strings are allowed, like strlen(), tolower(), toupper(), etc.
• The use of the helper source is not optional but mandatory. That means, you
should not reinvent your own functions for doing file reading.
• 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.
30
31
Indexes array for faster dictionary lookup(10% marks)
Indexes array: indexes[i][x-'a']: stores the index for the first words in
dictionary whose length is i and start with character x.
Q: How can indexes speed up the
dictionary lookup? (note that large
dictionary has over 370k words!)
A: The dictionary is sorted in (1)
ascending word length, and (2) then
in alphabetic order.
For example, a word with length 6 will
never appear in the section where
word lengths are less than 6. Then
we can skip plenty of meaningless
comparison.
Notes: 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 10% marks will be lost)
'a'
0
'b'
1
'c'
2
'z'
25
0 -1 -1 -1 … -1 -1 -1
1 -1 -1 -1 … -1 -1 -1
2 -1 -1 -1 -1 -1 -1
3 0 15 35 … 217
4 219 231 283 … 852
… … … … … … … …
10 3688 3723 3728 … 3962 -1 -1
… -1 -1 -1 … -1 -1 -1
50 -1 -1 -1 … -1 -1 -1
Index Word
0 act
1 add
... ...
15 bad
... ...
35 cab
... ...
217 zap
... ...
219 able
... ...
852 zany
... ...
3688 absolutely
... ...
3962 xenophobia
... ...
Dictionary array
Indexes array
word
length
first letter of word
Indexes array
32
What to do when we hit a -1 at a particular indexes element like
indexes[10][25] ?
Ans: This implies that words of length 10 starting with letter ‘z’ do not exist in
the dictionary. Simply bypass this checking.
Assignment 4: Word Search Puzzles
Better way to check your answer:
Copy and paste your program output and our sample program output to a
diff checker like https://www.diffchecker.com and see if there are any
differences.
33
https://www.diffchecker.com/
Assignment 4: Word Search Puzzles
Due: 8:00 PM , Saturday, November 9, 2019
Submission: wordsearch.cpp file only
34
Reference:
http://www.annigeri.in/2011/11/dynamic-two-dimensioned-
arrays-in-c.html
35
http://www.annigeri.in/2011/11/dynamic-two-dimensioned-arrays-in-c.html