Proj4sum15 < CS107

CS107 Web>Sum15>AssignmentsSum15>Proj4sum15 (2015-07-22, Main.troy) (raw view)EditAttach
---+ CS 107 - Summer 2015
---+++ Programming Project 4 - Boggle - Phase 2
 *Due: Tuesday, July 28, 2015 at 11:59pm*

For this project, you are to complete the Boggle program that was started in Programming Project 3. This will need to add three parts to the user input phase.
   1 Comparing the words entered to a dictionary of words to verify each word is valid.
   1 Making sure the sequence of letters is actually on the 4-by-4 grid of letters.
   1 Scoring each word.
*Word Scoring*

The scoring for each word is determined by its length (the number of characters in the word). The point values are shown in the following table.
|  *Word Length*  |  *Points*  |
|  0 - 2  | 0 |
|  3 - 4  |  1  |
|  5  |  2  |
|  6  |  3  |
|  7  |  5  |
|  8+  |  11  |

The Letter Q has its own special rules. <span style="color: #000000; font-family: 'Times New Roman'; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 1; word-spacing: 0px; display: inline ! important; float: none">In the English language, the letter </span>Q<span style="color: #000000; font-family: 'Times New Roman'; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 1; word-spacing: 0px; display: inline ! important; float: none"> is almost always followed by the letter </span>U<span style="color: #000000; font-family: 'Times New Roman'; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 1; word-spacing: 0px; display: inline ! important; float: none">. Consequently in the official Boggle Game, the side of one die is printed with the two-letter sequence </span>Qu<span style="color: #000000; font-family: 'Times New Roman'; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 1; word-spacing: 0px; display: inline ! important; float: none"> instead of </span>Q<span style="color: #000000; font-family: 'Times New Roman'; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 1; word-spacing: 0px; display: inline ! important; float: none"> (and this two-letter sequence must be used together when forming words). When scoring, </span>Qu<span style="color: #000000; font-family: 'Times New Roman'; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 1; word-spacing: 0px; display: inline ! important; float: none"> counts as two letters; for example, the word </span>QuEUE<span style="color: #000000; font-family: 'Times New Roman'; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 1; word-spacing: 0px; display: inline ! important; float: none"> scores as a 5-letter word even though it is formed by following a sequence of 4 dice. We will be following this rule for own game, but it is let to you as how to display the letter Q in the 4-by-4 grid as ==Q== or as ==Qu==.</span>

*The Word Dictionary*

Each word entered by the user needs to be verified as an actual word. The program is to prompt the user for the name of a dictionary file and the game will use the words listed in that text file as the official dictionary.  Below are three such files:
   * [[%ATTACHURL%/dictionary-algs4.txt][dictionary-algs4.txt]]
   * [[%ATTACHURL%/5desk.txt][5desk.txt]]
   * [[%ATTACHURL%/dictionary-yawl.txt][dictionary-yawl.txt]]
The words in the dictionary are given in both upper and lower case. In Boggle, case does not matter. So you should covert all letters to either upper or lower case (it really doesn't matter which one you choose). When comparing the words entered by the user, again case does not matter. So those words should also be coverted to the same case as the words in the dictionary.

When storing the words in an array, we want to use a dynamic array of strings. A dynamic array will increase in size when the array fills up. You are NOT allowed to use the C++ Vector to implement this. Implementation of this will be covered in lecture.

When searching for the users word in the dynamic array, you are to use the binary search algorithm. Implementation of this will be covered in lecture.

<strong>Searching the Boggle Grid for a Word</strong>

The players compete to accumulate points by building _valid_ words out of the dice according to the following rules:
   * A valid word must be composed by following a sequence of <em>adjacent dice</em>&mdash;two dice are adjacent if they are horizontal, vertical, or diagonal neighbors.
   * A valid word can use each die at most once.
   * A valid word must contain at least 3 letters.
   * A valid word must be in the dictionary (which typically does not contain proper nouns).
<span style="color: #000000; font-family: 'Times New Roman'; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 1; word-spacing: 0px; display: inline ! important; float: none">Here are some examples of valid and invalid words:</span><table align="center" border="0"><tbody><tr><td><img width="220" alt="pins" align="middle" src="http://coursera.cs.princeton.edu/algs4/assignments/pins.png" title="pins" /></td><td> </td><td><img width="220" alt="pines" align="middle" src="http://coursera.cs.princeton.edu/algs4/assignments/pines.png" title="pines" /></td><td> </td><td><img width="220" alt="dates" align="middle" src="http://coursera.cs.princeton.edu/algs4/assignments/dates.png" title="dates" /></td></tr><tr><td align="center">PINS<br />( _valid_)</td><td> </td><td align="center">PINES<br />( _valid_)</td><td> </td><td align="center">DATES<br />( _invalid&mdash;dice not adjacent_)</td></tr><tr><td> </td></tr><tr><td><img width="220" alt="pint" align="middle" src="http://coursera.cs.princeton.edu/algs4/assignments/pint.png" title="pint" /></td><td> </td><td><img width="220" alt="tepee" align="middle" src="http://coursera.cs.princeton.edu/algs4/assignments/tepee.png" title="tepee" /></td><td> </td><td><img width="220" alt="sid" align="middle" src="http://coursera.cs.princeton.edu/algs4/assignments/sid.png" title="sid" /></td></tr><tr><td align="center">PINT<br />( _invalid&mdash;path not sequential_)</td><td> </td><td align="center">TEPEE<br />( _invalid&mdash;die used more than once_)</td><td> </td><td align="center">SID<br />( _invalid&mdash;word not in dictionary_)</td></tr></tbody></table> To determine if a word exists in the boggle grid, the following recursive algorithm is given to you. Note this is given in psuedo-code, so you will need to translate it to match how you have implemented the rest of your program. It uses two functions and only one is recursive. The first function looks for the first letter in the given word, then calls the second function to determine if the remaining letters actually exist in the boggle grid. Note: this does not solve for the Q/Qu case. A modification is needed that will be discussed during lecture. Also note: the algorithm is being given as an attachment as this wiki tends to remove indentation. 
   * [[%ATTACHURL%/boggleFindAlg.txt][boggleFindAlg.txt]]
After the 3 minutes of time is finished, you should display a message showing the number of correct words found and the total points earned.

---+++ The Write-up for Boggle - Phase 1
 For this project, you will write a program in "C+" that will create the a set of 16 semi-random letters in a 4-by-4 grid and have the user enter in as many words as possible that can be made from these letters in a 3 minute time frame.

This game has been marketed as <a target="_top" href="https://www.google.com/search?q=boggle+rules&ie=utf-8&oe=utf-8">Boggle</a>. The <a target="_top" href="https://en.wikipedia.org/wiki/Boggle">wikipedia page for Boggle</a> has a good discussion of the game as does the <a target="_top" href="http://www.wikihow.com/Play-Boggle">wikihow Boggle page</a>. The official rules of Boggle can be found at the Hasbro Web Site:
   * <a target="_top" href="http://www.hasbro.com/common/instruct/boggle.pdf">http://www.hasbro.com/common/instruct/boggle.pdf</a>
The letters used come from 16 6-sided cubes (or dice) with one letter per side. Each of the 16 locations in the 4-by-4 grid will use one letter from one of the dice. Since the letters on each of the dice are pre-determined, we can call this a "semi-random" distribution. We will use the following dice combinations: 
   1 AAEEGN
   1 ABBJOO
   1 ACHOPS
   1 AFFKPS
   1 AOOTTW
   1 CIMOTU
   1 DEILRX
   1 DELRVY
   1 DISTTY
   1 EEGHNW
   1 EEINSU
   1 EHRTVW
   1 EIOSST
   1 ELRTTY
   1 HIMNUQu
   1 HLNNRZ
Storing the above information as an array of 16 strings may be a good way to keep track of the information.

Note that the 15th dice has a final letter as the combination Qu. Since the letter Q is almost always followed by the letter U in most English words, the game automatically allows this combination. Note, you may want to just use the letter Q

Your program is to display the Boggle grid of 4-by-4 letter based on randomly placing the 16 dice into the 16 grid positions and randomly selecting one of the 6 letters from each dice.

After the grid has been displayed your program is to allow the user to enter in as many words as possible until 3 minutes has elapsed. Since we are not making a truly interactive User Interface, we will only check for the time after the user enters in a work. When a user enters a word, check to see how long it have been since the letter grid was displayed. If it have been less than 3 minutes (or 180 seconds), loop and allow the user to enter another word. If it has been more than 3 minutes, display the number of words entered by the user and the end the program. This manner will allow the user to enter in one word after the 3 minutes has expired, but that will be OK for this program.

Note: This program is not validating the words entered by the user nor keeping track of the points scored. That will be done in Phase 2 (Project 4).

Your program must determine and store the letters in the grid first. Then it can display the grid after all 16 locations have been determined. The 4-by-4 grid of letters may best be stored in a 2 dimensional array. This is not a requirement for Phase 1, but will be a requirement for Phase 2.

You should use functions as much as possible when writing this program. You are REQUIRED to have
   * a function to determine and store the letters in the grid
   * a function to print out the letters to user
   * a function to monitor the users input of words and keep track of the 3 minutes of time
The array used to store the letters in the grid will be passed out of the first function and into the second function. For Phase 2, this array will also need to be passed into the third function.

---+++ User Input

At the start of your program, you should give the user some instructions on how the play the game. The exact verbiage is left up to you, but some points will be given for the appropriateness of this message.

After the grid has been displayed, allow the user to enter in input. Reading this information as string is probably the easiest. We are not doing anything with this data except counting the number of words entered by the user and checking how long it has been since the grid was displayed.

At the end of the program, you should thank the user for playing and give some information on the "development team" (i.e. your name, that this program was developed for CS 107, etc).
---+++ Random Numbers and More on Time
 While there really is no such thing as a real random number, the sequences of numbers generated are complicated enough that to just about everyone, they seem random. A nice discussion of random numbers is given on the <a target="_top" href="http://www.cplusplus.com/articles/EywTURfi/">cplusplus.com</a> web page.

The primary library function for random numbers in C/C++ is <a target="_top" href="http://www.cplusplus.com/reference/cstdlib/rand/">rand()</a> in the C library stdlib.h or in the C++ library cstdlib.

The rand() library function returns an integer value from 0 to the largest integer usable on the machine. To get this value into a desired range the modulus operator % is normally used. The modulus operator will get the random value to be in the range from 0 to some number. If we want to have our random number to be in the range from 1 to N, we will want to add 1 to the random number after the modulus operation by N is performed.

Note that rand() when used by itself will generate the same random numbers everytime a program runs. While this is useful for testing, if makes playing a game like codebreaker a bit boring. Thus we will also want to use the library function of <a target="_top" href="http://www.cplusplus.com/reference/cstdlib/srand/">srand()</a> to make things become truly random. The most common way to use srand() is to use the library function of time(). All of the cplusplus.com web pages that discuss rand() show how to use srand() and time() to create truly random numbers.

The time library also has a function called <a target="_top" href="http://www.cplusplus.com/reference/ctime/difftime/">difftime()</a>. This function will take two instances of the type <a target="_top" href="http://www.cplusplus.com/reference/ctime/time_t/">time_t</a> and return the number of seconds between the two times. Consider the following example.
<blockquote> // Example program<br />#include &lt;iostream&gt;<br />#include &lt;string&gt;<br />#include &lt;ctime&gt;<br /><br />using namespace std;<br /><br />int main()<br />{<br /> time_t now, then;<br /> double seconds;<br /> // get the starting time<br /> time(&now);<br /> <br /> std::string name;<br /> std::cout &lt;&lt; "What is your name? ";<br /> getline (std::cin, name);<br /> std::cout &lt;&lt; "Hello, " &lt;&lt; name &lt;&lt; "!\n";<br /> <br /> // get the ending time<br /> time(&then);<br /> <br /> seconds = difftime(then, now);<br /> <br /> cout &lt;&lt; "You took " &lt;&lt; seconds &lt;&lt; " seconds to type in your name." &lt;&lt; endl;<br />} </blockquote>

---+++ Submittal of your Program
 Use the submission link in Blackboard to electronically submit your .cpp file for grading.

Please name your program file using both your NET-ID and the Project Number. Thus for Project 4, if you NET-ID was ptroy4, your program should be named: *ptroy4Proj4.cpp*

-- Main.troy - 2015-07-22
Attachments
Topic attachments
I	Attachment	Action	Size	Date	Who
txt	5desk.txt	manage	626.6 K	2015-07-22 - 13:10	UnknownUser
txt	boggleFindAlg.txt	manage	1.3 K	2015-07-22 - 13:35	UnknownUser
txt	dictionary-algs4.txt	manage	50.7 K	2015-07-22 - 13:43	UnknownUser
txt	dictionary-yawl.txt	manage	2657.8 K	2015-07-22 - 13:43	UnknownUser
Topic revision: r2 - 2015-07-22 - 16:48:21 - Main.troy
CS107
[edit this menu]
WISEST
Helping Women Faculty Advance
Funded by NSF