Program #5: Compare

Prof. Reed, CS 107, Fall `02
Due Wednesday 11/20/02 at 2:30 in the afternoon

Last update: 11/8 at 2:00

This is a word-guessing game. The computer generates a board at random and figures out how many valid words can be found on the board, displaying this number to the user. The user then tries to find as many as possible, where the computer keeps track of the words the user has found so far. The user can also request that the computer's words be displayed on the screen. Take a look at the sample run below:

[ernie] ~/programs/compare> compare

Author: Dale Reed 
Assignment: #5, Compare 
TA: Thef Inals Tretch, Sat 1:00-1:05 


See how many words you can find in the board below.  Words must be 
at least 3 characters long and can be placed vertically, horizontally, 
or diagonally in any direction.  The computer will help you keep track 
of which words you have found so far. Enter 'x' to exit the program, 
'l' to list the words you have found so far, or 's' to have the computer 
suggest words you have not yet found. 

 Computer has found 60 words.  User has found 0 words. 

   0 1 2 3 4 5 6 7 8 9 
  --------------------
A| r w v q z w q f i t 
B| u p n p q h i m w w 
C| k b v t d q l k a a 
D| p m s d b z t r n h 
E| f j e y e j r i p g 
F| s n l a d m v m c h 
G| z p i r d c o u h i 
H| z p o t a r u g x j 
I| v s v t p n k t z c 
J| t u j o o w d v z m 

Enter the starting position and the word (or l, s, or x): d 3 den

 Congratulations, you found: den 

 Computer has found 60 words.  User has found 1 words. 

   0 1 2 3 4 5 6 7 8 9 
  --------------------
A| r w v q z w q f i t 
B| u p n p q h i m w w 
C| k b v t d q l k a a 
D| p m s d b z t r n h 
E| f j e y e j r i p g 
F| s n l a d m v m c h 
G| z p i r d c o u h i 
H| z p o t a r u g x j 
I| v s v t p n k t z c 
J| t u j o o w d v z m 

Enter the starting position and the word (or l, s, or x): d 3 den

 Congratulations, you found: den 
You previously guessed that word. Try again.

 Computer has found 60 words.  User has found 1 words. 

   0 1 2 3 4 5 6 7 8 9 
  --------------------
A| r w v q z w q f i t 
B| u p n p q h i m w w 
C| k b v t d q l k a a 
D| p m s d b z t r n h 
E| f j e y e j r i p g 
F| s n l a d m v m c h 
G| z p i r d c o u h i 
H| z p o t a r u g x j 
I| v s v t p n k t z c 
J| t u j o o w d v z m 

Enter the starting position and the word (or l, s, or x): d 1 mead

 Congratulations, you found: mead 

 Computer has found 60 words.  User has found 2 words. 

   0 1 2 3 4 5 6 7 8 9 
  --------------------
A| r w v q z w q f i t 
B| u p n p q h i m w w 
C| k b v t d q l k a a 
D| p m s d b z t r n h 
E| f j e y e j r i p g 
F| s n l a d m v m c h 
G| z p i r d c o u h i 
H| z p o t a r u g x j 
I| v s v t p n k t z c 
J| t u j o o w d v z m 

Enter the starting position and the word (or l, s, or x): a 7 fits
That word is not on the board.

 Computer has found 60 words.  User has found 2 words. 

   0 1 2 3 4 5 6 7 8 9 
  --------------------
A| r w v q z w q f i t 
B| u p n p q h i m w w 
C| k b v t d q l k a a 
D| p m s d b z t r n h 
E| f j e y e j r i p g 
F| s n l a d m v m c h 
G| z p i r d c o u h i 
H| z p o t a r u g x j 
I| v s v t p n k t z c 
J| t u j o o w d v z m 

Enter the starting position and the word (or l, s, or x): l
den mead 


 Computer has found 60 words.  User has found 2 words. 

   0 1 2 3 4 5 6 7 8 9 
  --------------------
A| r w v q z w q f i t 
B| u p n p q h i m w w 
C| k b v t d q l k a a 
D| p m s d b z t r n h 
E| f j e y e j r i p g 
F| s n l a d m v m c h 
G| z p i r d c o u h i 
H| z p o t a r u g x j 
I| v s v t p n k t z c 
J| t u j o o w d v z m 

Enter the starting position and the word (or l, s, or x): s
add and ani art atop bed cat cit cut demo dna drip eli eye eye fit
gum ham haw him irk jut lad mph mug ned nit nrc oil ott pad ply pot 
pot pro prom ran rand rat raw ray rim rip rip romp rug spot tar tic 
tin top top tray twa wah wan war woo 


 Computer has found 60 words.  User has found 2 words. 

   0 1 2 3 4 5 6 7 8 9 
  --------------------
A| r w v q z w q f i t 
B| u p n p q h i m w w 
C| k b v t d q l k a a 
D| p m s d b z t r n h 
E| f j e y e j r i p g 
F| s n l a d m v m c h 
G| z p i r d c o u h i 
H| z p o t a r u g x j 
I| v s v t p n k t z c 
J| t u j o o w d v z m 

Enter the starting position and the word (or l, s, or x): x
Exiting...

[ernie] ~/programs/compare> 

You need to know the following concepts in order to write this program:

Notes:

1. Your board should be of size 10 by 10.
2. You must use srand( 63) in your program, which should give you exactly the board shown above. Generate the random characters one at a time, starting in the top left and working down row by row, ending up at the bottom right. (Note that your program should still work correctly if the random number seed were different, which would give a different board.)
3. Following are the teps to take in writing your program, along with corresponding point values (adds up to the 55 points for runs correctly):
   1. (0 points) Read in the dictionary words and make sure dictionary lookup is working correctly. Code to read in the dictionary words and do a binary search is found here. A copy of the Unix dictionary file is here (25,143 words, 227K), though for testing you may want to use something smaller of your own.
   2. (5 points) Generate the board, generating the random characters that go in each place. Also writing the function to display the board.
   3. (20 points) Write the code to generate all possible words on the board, printing them out. To do this you will likely need about 4 nested for loops.
      - The outer most 2 loops take you through each position on the board (each row & column)
      - For each position (row & column) you will then have an additional for loop to loop through the possible directions (8 of them) starting from that row & column position.
      - Then for each of those possible directions you will loop through possible word lengths (the 4th for loop).
      - For each word length determine whether or not this word would take you off the edge of the board, If not, then
      call a function that takes the board, the position on the board, direction, and length and gives you the word that corresponds to those values. Print out each of these words. These nested for loops in my program ended up looking something like this.
   4. (5 points) Once you have verified that your program is in fact generating all the words, lookup each of these generated words in the dictionary. Modify your program so that only the words found in the dictionary are displayed, and additionally your program counts how many words are found. You may want to compare the words you found with the positions and words from my program.
   5. (5 points) Now store these computer-found dictionary words in an array. This array should hold a maximum of 200 words, where each could be a maximum of 10 characters long.
   6. (5 points) Write a function (well o.k., copy it) to do a bubble sort of the computer-found words array. See the solution to the second in-lab problem for midterm 2 for a function to do this.
   7. (0 points) Make another array of the same size as the computer-found words array, that will be "parallel" to the computer-found words array. It will be an array of type bool, and will be used to keep track of whether or not the human user has found each of the words the computer found in the dictionary. You should initialize all its values to false.
   8. (15 points) Now write the main loop inside main() of your program, that allows the user to continue guessing. If the user guesses all the words, the program should exit with a congratulatory message. Handle the various user options at this point ('x' to exit, 'l' to list words found so far, and 's' for suggestions, displaying the computer-found words).
      - Since the computer-found words array is now in sorted order, you can use the same binary search function to lookup a word in that array that you use in looking up a word in the dictionary. (You just send it a different array as a parameter.) Every time the user correctly finds a word, the corresponding boolean value in the boolean array should be set to true.
      - When the 'l' option is selected, you will step through the computer-found words, displaying the ones that have a corresponding boolean array value of true. You can use this boolean array also to warn users when they guess a word that has already been guessed before.
      
4. If your program only gets part way through the above steps, you should make sure you display what you've gotten so far so you can be given credit for it. Your header in your code should also explicitly say what works and what doesn't.
5. Duplicate words found by the computer count as separate words. This means the user will not be able to find all the words on the board, because once the first one is found, the boolean flag value corresponding to that word will be set to true, and the computer will not continue to search for a second one. This is a problem that you don't need to solve. Just leave it that way.
6. Your program must exhibit good modular programming style, breaking up sections of code into functions. In particular if there is code that you execute more than once, it should be in a function.
7. Once it is ready, you can execute a version of this program at
   

~i107/programs/compare/compare


Note that this will not work unless you have the dictionary.txt file in your current directory. You can copy this from the web site, or enter the following Unix command to do this:

ln -s /usr/dict/words dictionary.txt

8. Use the g++ compiler on the CS machines. If you have trouble with formatting (i.e. indenting), use the"cb" or "indent" programs to help you. If you use either of these, be sure to document this fact in your program header.
   
9. Turnin your program electronically using the "turnin" command into the compare project as follows:

   turnin -c cs107 -p compare prog5.c

   where your file name in your account is prog5.c

   
   [CS Dept] [UIC] [Prof. Reed]