Starting from:
$25
CS204- Homework 1 Solved
Introduction
Word hunts are one of the rather common word puzzles out there. The aim is to find words from a seemingly random letters spread out on a 2D matrix, with each cell on the matrix containing one letter. In this version of the word hunt, players will be able to start from any letter and follow any path by going one cell a time in vertical and horizontal directions. Diagonal movement is not allowed, and the words do not have to be in a straight line. An example matrix and a word marked on it is given in Figure 1.
Figure 1: A sample puzzle and a word marked in the puzzle
Inputs, Outputs and Program Flow
First, player will be prompted for the name of the puzzle file. If the file with the given name cannot be opened, player will be prompted again until a file can successfully be opened. You must store this puzzle using a 2D matrix (i.e. a vector of vector of char). Once the puzzle is read from the file, the player will be prompted for the name of a dictionary file. Same as with puzzle file, player will be prompted for the name of the dictionary file until the file is successfully opened. You may store the contents of the dictionary file in a vector if you wish so. This dictionary file contains words in English in alphabetically sorted manner. There is one word in each line of this file; you do not need to check this. All letters are lowercase in this file. We provide this file (words.dat) within the homework package.
Once both files have been opened successfully, current state of the puzzle will be displayed, the game starts. The player's aim is to hunt valid words by concatenating neighboring letters in the matrix. To do so, the player first enters the coordinates of starting location (as x and y coordinates, both integers) and a path to follow from there. The path will be entered as a string that contains only 'r', 'l', 'u' and 'd' characters, representing "right", "left", "up" and "down". The word starts at the starting location, including the letter in that cell as the first letter of the word, and appending letters in each cell visited according to letters in the path string. Here note that the coordinates start with 0 both vertically and horizontally; i.e. the upper-left corner of the matrix has coordinate of (0,0). An example case is given in Figure 2.
Figure 2: The path followed by inputs 0 0 and rrdll on a sample matrix
The minimum length of a word must be 3, which means minimum length of the path string must be 2. If a meaningful word exists along the given path, which will be checked by looking for the word in the dictionary, (1) the player will be awarded points equal to square of number of letters in the word, and (2) the letters in the cells used to create the word will be removed from the matrix and be replaced by underscore
(‘_’) character. An example is given in Figure 3. In this example, first word found by player, in this case
“sample”, has a length of 6 character, therefore the player will receive 36 points, calculated by taking square of the length of word. Then the player manages to find the word “puzzle” to earn another 36 points, increasing the total score to 72 from 36. This is just an example to help you understand and visualize the flow of the program, how the matrix progressively changes and how the score is calculated.
Figure 3: Removal of found words from puzzle
The game will continue to hunt more words. The game will end either (i) when all letters in the matrix are used OR (ii) the player decides to quit by entering -1 as one of the coordinates of the starting position. If the player has managed to use all the letters, an additional message will be displayed to mention that the puzzle has been solved completely. Afterwards, the player will be shown his/her final score (no matter he/she finished puzzle or not) and the program will end.
Input Checks
There are a couple things you need to pay attention to when dealing with inputs. First, the puzzle should be a proper 2D matrix, meaning each line should contain same number of cells (letters). For example, if there are 5 cells in first line, every other line should also contain 5 cells. On top of it, each cell should only contain one lowercase character, meaning both non-letter characters and uppercase letters would be invalid entries.
Rows may contain arbitrary number of white characters (space, tab), you may not make any assumptions. You may assume there will not be any empty lines including before, in between and after the matrix.
Aside from puzzle, the inputs for hunting a word needs to be checked. The starting location should consist of two integer values, and this coordinate should be within the limits of the matrix. If there are 𝑛 rows and 𝑚 columns in the matrix, the first coordinate entry must be between 0 and 𝑛−1, and the second entry must be between 0 and 𝑚−1. Moreover, all of the cells visited along the path via r, l, u, d sequence must also stay within the limits of the matrix. Such an invalid move is called impossible move and if such a move is entered by the user, you have to display an error message and continue with the game.
The second type of impossible move is reuse of a cell. This can happen in two ways; (i) first being attempting to use a cell whose content has been replaced with an underscore, and (ii) the second being attempting a reuse of a cell in the within the current path. In such cases, you have to give an appropriate error message (see "sample runs" for examples).
Another error case is with path input characters. Of the four available directions, right is represented with ‘r’, left with ‘l’, up with ‘u’ and down with ‘d’. Any other character is considered an invalid input. You may choose to accept uppercase versions of these character, but it is not required. Please also note that since the minimum word length is 3, minimum number of characters in the path string must be 2.
Sample Runs
Some sample runs are given below, but these are not comprehensive, therefore you must consider all possible cases to get full mark.
Dictionary file (words.dat) and the puzzle sample files are provided within the homework package.
Sample 1:
Please enter the name of the puzzle file: puzzle.txt File could not be opened.
Please enter the name of the puzzle file: puzzle1.txt Please enter the name of the dictionary file: words.txt File could not be opened.
Please enter the name of the dictionary file: words.dat
e h w o d c e l r l n e l o c c i t u o s r e p m
Enter the starting location for word (x, y): 0 6
Invalid coordinate - out of range
e h w o d c e l r l n e l o c c i t u o s r e p m
Enter the starting location for word (x, y): 0 1
Enter the path: drruu
Invalid path - out of range
e h w o d c e l r l n e l o c c i t u o s r e p m
Enter the starting location for word (x, y): 0 1
Enter the path: ldd1rru
Invalid path - non-RLUD input
e h w o d c e l r l n e l o c c i t u o s r e p m Enter the starting location for word (x, y): 0 1
Enter the path: ldddrurull
Invalid path - cell visited twice
e h w o d c e l r l n e l o c c i t u o s r e p m
Enter the starting location for word (x, y): 0 1
Enter the path: ddd
Invalid word - non-existent word “heei”
e h w o d c e l r l n e l o c c i t u o s r e p m
Enter the starting location for word (x, y): 0 1
Enter the path: drdr Word found: hello
Word length: 5
Points gained: 25
Current score: 25
e _ w o d c _ _ r l n e _ _ c c i t u o s r e p m
Enter the starting location for word (x, y): 3 0
Enter the path: rrrruull
Invalid path - cell visited previously
e _ w o d
c _ _ r l
n e _ _ c
c i t u o s r e p m
Enter the starting location for word (x, y): 0 2
Enter the path: rdru Word found: world
Word length: 5
Points gained: 25
Current score: 50
e _ _ _ _ c _ _ _ _ n e _ _ c c i t u o s r e p m
Enter the starting location for word (x, y): 2 4
Enter the path: ddluldl
Word found: computer Word length: 8
Points gained: 64
Current score: 114
e _ _ _ _ c _ _ _ _ n e _ _ _ c i _ _ _ s _ _ _ _
Enter the starting location for word (x, y): 4 0
Enter the path: uruluu
Word found: science
Word length: 7
Points gained: 49
Current score: 163
Congratulations, you have solved the puzzle perfectly!
Your final score is 163.
Press any key to continue . . .
Sample 2:
Please enter the name of the puzzle file: puzzle2.txt
Please enter the name of the dictionary file: words.dat
g n c n t i o u u p m f
Enter the starting location for word (x, y): 0 0
Enter the path: l
Invalid path - path too short
g n c n t i o u u p m f
Enter the starting location for word (x, y): 0 2
Enter the path: dlu
Word found: coin
Word length: 4
Points gained: 16 Current score: 16
g _ _ n t _ _ u u p m f
Enter the starting location for word (x, y): -1 0
You didn't completely solve the puzzle.
Your final score is 16.
Press any key to continue . . .
Sample 3:
Please enter the name of the puzzle file: puzzle3.txt
Invalid matrix - inconsistent dimensions
Press any key to continue . . .
Sample 4:
Please enter the name of the puzzle file: puzzle4.txt Invalid matrix - char not lowercase letter
Press any key to continue . . .
Sample 5:
Please enter the name of the puzzle file: puzzle5.txt
Invalid matrix - cell entry is not a char
Press any key to continue . . .
Sample 6:
Please enter the name of the puzzle file: puzzle2.txt
Please enter the name of the dictionary file: words.dat
g n c n t i o u u p m f
Enter the starting location for word (x, y): 0 -1
You didn't completely solve the puzzle.
Your final score is 0.
Press any key to continue . . .
Word hunts are one of the rather common word puzzles out there. The aim is to find words from a seemingly random letters spread out on a 2D matrix, with each cell on the matrix containing one letter. In this version of the word hunt, players will be able to start from any letter and follow any path by going one cell a time in vertical and horizontal directions. Diagonal movement is not allowed, and the words do not have to be in a straight line. An example matrix and a word marked on it is given in Figure 1.
Figure 1: A sample puzzle and a word marked in the puzzle
Inputs, Outputs and Program Flow
First, player will be prompted for the name of the puzzle file. If the file with the given name cannot be opened, player will be prompted again until a file can successfully be opened. You must store this puzzle using a 2D matrix (i.e. a vector of vector of char). Once the puzzle is read from the file, the player will be prompted for the name of a dictionary file. Same as with puzzle file, player will be prompted for the name of the dictionary file until the file is successfully opened. You may store the contents of the dictionary file in a vector if you wish so. This dictionary file contains words in English in alphabetically sorted manner. There is one word in each line of this file; you do not need to check this. All letters are lowercase in this file. We provide this file (words.dat) within the homework package.
Once both files have been opened successfully, current state of the puzzle will be displayed, the game starts. The player's aim is to hunt valid words by concatenating neighboring letters in the matrix. To do so, the player first enters the coordinates of starting location (as x and y coordinates, both integers) and a path to follow from there. The path will be entered as a string that contains only 'r', 'l', 'u' and 'd' characters, representing "right", "left", "up" and "down". The word starts at the starting location, including the letter in that cell as the first letter of the word, and appending letters in each cell visited according to letters in the path string. Here note that the coordinates start with 0 both vertically and horizontally; i.e. the upper-left corner of the matrix has coordinate of (0,0). An example case is given in Figure 2.
Figure 2: The path followed by inputs 0 0 and rrdll on a sample matrix
The minimum length of a word must be 3, which means minimum length of the path string must be 2. If a meaningful word exists along the given path, which will be checked by looking for the word in the dictionary, (1) the player will be awarded points equal to square of number of letters in the word, and (2) the letters in the cells used to create the word will be removed from the matrix and be replaced by underscore
(‘_’) character. An example is given in Figure 3. In this example, first word found by player, in this case
“sample”, has a length of 6 character, therefore the player will receive 36 points, calculated by taking square of the length of word. Then the player manages to find the word “puzzle” to earn another 36 points, increasing the total score to 72 from 36. This is just an example to help you understand and visualize the flow of the program, how the matrix progressively changes and how the score is calculated.
Figure 3: Removal of found words from puzzle
The game will continue to hunt more words. The game will end either (i) when all letters in the matrix are used OR (ii) the player decides to quit by entering -1 as one of the coordinates of the starting position. If the player has managed to use all the letters, an additional message will be displayed to mention that the puzzle has been solved completely. Afterwards, the player will be shown his/her final score (no matter he/she finished puzzle or not) and the program will end.
Input Checks
There are a couple things you need to pay attention to when dealing with inputs. First, the puzzle should be a proper 2D matrix, meaning each line should contain same number of cells (letters). For example, if there are 5 cells in first line, every other line should also contain 5 cells. On top of it, each cell should only contain one lowercase character, meaning both non-letter characters and uppercase letters would be invalid entries.
Rows may contain arbitrary number of white characters (space, tab), you may not make any assumptions. You may assume there will not be any empty lines including before, in between and after the matrix.
Aside from puzzle, the inputs for hunting a word needs to be checked. The starting location should consist of two integer values, and this coordinate should be within the limits of the matrix. If there are 𝑛 rows and 𝑚 columns in the matrix, the first coordinate entry must be between 0 and 𝑛−1, and the second entry must be between 0 and 𝑚−1. Moreover, all of the cells visited along the path via r, l, u, d sequence must also stay within the limits of the matrix. Such an invalid move is called impossible move and if such a move is entered by the user, you have to display an error message and continue with the game.
The second type of impossible move is reuse of a cell. This can happen in two ways; (i) first being attempting to use a cell whose content has been replaced with an underscore, and (ii) the second being attempting a reuse of a cell in the within the current path. In such cases, you have to give an appropriate error message (see "sample runs" for examples).
Another error case is with path input characters. Of the four available directions, right is represented with ‘r’, left with ‘l’, up with ‘u’ and down with ‘d’. Any other character is considered an invalid input. You may choose to accept uppercase versions of these character, but it is not required. Please also note that since the minimum word length is 3, minimum number of characters in the path string must be 2.
Sample Runs
Some sample runs are given below, but these are not comprehensive, therefore you must consider all possible cases to get full mark.
Dictionary file (words.dat) and the puzzle sample files are provided within the homework package.
Sample 1:
Please enter the name of the puzzle file: puzzle.txt File could not be opened.
Please enter the name of the puzzle file: puzzle1.txt Please enter the name of the dictionary file: words.txt File could not be opened.
Please enter the name of the dictionary file: words.dat
e h w o d c e l r l n e l o c c i t u o s r e p m
Enter the starting location for word (x, y): 0 6
Invalid coordinate - out of range
e h w o d c e l r l n e l o c c i t u o s r e p m
Enter the starting location for word (x, y): 0 1
Enter the path: drruu
Invalid path - out of range
e h w o d c e l r l n e l o c c i t u o s r e p m
Enter the starting location for word (x, y): 0 1
Enter the path: ldd1rru
Invalid path - non-RLUD input
e h w o d c e l r l n e l o c c i t u o s r e p m Enter the starting location for word (x, y): 0 1
Enter the path: ldddrurull
Invalid path - cell visited twice
e h w o d c e l r l n e l o c c i t u o s r e p m
Enter the starting location for word (x, y): 0 1
Enter the path: ddd
Invalid word - non-existent word “heei”
e h w o d c e l r l n e l o c c i t u o s r e p m
Enter the starting location for word (x, y): 0 1
Enter the path: drdr Word found: hello
Word length: 5
Points gained: 25
Current score: 25
e _ w o d c _ _ r l n e _ _ c c i t u o s r e p m
Enter the starting location for word (x, y): 3 0
Enter the path: rrrruull
Invalid path - cell visited previously
e _ w o d
c _ _ r l
n e _ _ c
c i t u o s r e p m
Enter the starting location for word (x, y): 0 2
Enter the path: rdru Word found: world
Word length: 5
Points gained: 25
Current score: 50
e _ _ _ _ c _ _ _ _ n e _ _ c c i t u o s r e p m
Enter the starting location for word (x, y): 2 4
Enter the path: ddluldl
Word found: computer Word length: 8
Points gained: 64
Current score: 114
e _ _ _ _ c _ _ _ _ n e _ _ _ c i _ _ _ s _ _ _ _
Enter the starting location for word (x, y): 4 0
Enter the path: uruluu
Word found: science
Word length: 7
Points gained: 49
Current score: 163
Congratulations, you have solved the puzzle perfectly!
Your final score is 163.
Press any key to continue . . .
Sample 2:
Please enter the name of the puzzle file: puzzle2.txt
Please enter the name of the dictionary file: words.dat
g n c n t i o u u p m f
Enter the starting location for word (x, y): 0 0
Enter the path: l
Invalid path - path too short
g n c n t i o u u p m f
Enter the starting location for word (x, y): 0 2
Enter the path: dlu
Word found: coin
Word length: 4
Points gained: 16 Current score: 16
g _ _ n t _ _ u u p m f
Enter the starting location for word (x, y): -1 0
You didn't completely solve the puzzle.
Your final score is 16.
Press any key to continue . . .
Sample 3:
Please enter the name of the puzzle file: puzzle3.txt
Invalid matrix - inconsistent dimensions
Press any key to continue . . .
Sample 4:
Please enter the name of the puzzle file: puzzle4.txt Invalid matrix - char not lowercase letter
Press any key to continue . . .
Sample 5:
Please enter the name of the puzzle file: puzzle5.txt
Invalid matrix - cell entry is not a char
Press any key to continue . . .
Sample 6:
Please enter the name of the puzzle file: puzzle2.txt
Please enter the name of the dictionary file: words.dat
g n c n t i o u u p m f
Enter the starting location for word (x, y): 0 -1
You didn't completely solve the puzzle.
Your final score is 0.
Press any key to continue . . .
1 file (611.9KB)
