CMSC 389C: Homework #1 -- Hello World!

Project #1	CMSC 389C
Due: Friday 1/13 at 11:00PM	C++ Programming

Markov Chain Random Text Generation

Objective

We'll have some fun practicing strings and vectors in C++. We'll also be practicing how different kinds of variables can be used as parameters.

Overview

We will create a program that will generate random text. The goal is for the text to resemble (at least somewhat) text written by a human. We will rely on a mathematical construct known as Markov Chains. This is not a new idea... unfortunately spammers frequently use these kinds of techniques to generate random email messages that appear as though they may have been written by humans. This will frequently fool spam filters into believing they are legitimate messages instead of junkmail! Of course there are also other, more constructive applications of Markov Chain Random Text Generation!

The idea behind the technique is to begin by having the program read in a large body of text, written by a human. The program will record chains of words of a fixed length, and will keep track of which particular word appeared immediately after each chain. This information is then used by a very simple algorithm that generates random text. We'll describe the process fully, below.

To give us something to work with, let's pretend the the following text is the input to the program:

THE DOG IS YELLOW THE CAT IS YELLOW SO IS THE DOG THE CAT

The program will begin by collecting all of the "chains" of words for a fixed length. Here are the chains that the program would store for several different potential "lengths". After each chain, we record the word that immediately followed the chain in the original passage:

length 1 length 2 length 3

[THE] DOG
[DOG] IS
[IS] YELLOW
[YELLOW] THE
[THE] CAT
[CAT] IS
[IS] YELLOW
[YELLOW] SO
[SO] IS
[IS] THE
[THE] DOG
[DOG] THE
[THE] CAT
[CAT] THE_END [THE, DOG] IS
[DOG, IS] YELLOW
[IS, YELLOW] THE
[YELLOW, THE] CAT
[THE, CAT] IS
[CAT, IS] YELLOW
[IS, YELLOW] SO
[YELLOW, SO] IS
[SO, IS] THE
[IS, THE] DOG
[THE, DOG] THE
[DOG, THE] CAT
[THE, CAT] THE_END [THE, DOG, IS] YELLOW
[DOG, IS, YELLOW] THE
[IS, YELLOW, THE] CAT
[YELLOW, THE, CAT] IS
[THE, CAT, IS] YELLOW
[CAT, IS, YELLOW] SO
[IS, YELLOW, SO] IS
[YELLOW, SO, IS] THE
[SO, IS, THE] DOG
[IS, THE, DOG] THE
[THE, DOG, THE] CAT
[DOG, THE, CAT] THE_END

Notice that we invented a terminal symbol "THE_END" to denote the end of the original passage.

Study the table above and make sure you understand how it was generated before you read further!

The program will actually store the data a bit more efficiently. Some of the chains appear more than once, so rather than storing duplicate chains, we will store each kind of chain just once, along with a list of the various endings that were seen in the original text after that kind of chain:

length 1 length 2 length 3

[THE] {DOG, CAT, DOG, CAT}
[DOG] {IS, THE}
[IS] {YELLOW, YELLOW, THE}
[YELLOW] {THE, SO}
[CAT] {IS, THE_END}
[SO] {IS}
[THE, DOG] {IS, THE}
[DOG, IS] {YELLOW}
[IS, YELLOW] {THE, SO}
[YELLOW, THE] {CAT}
[THE, CAT] {IS, THE_END}
[CAT, IS] {YELLOW}
[YELLOW, SO] {IS}
[SO, IS] {THE}
[IS, THE] {DOG}
[DOG, THE] {CAT}
[THE, DOG, IS] {YELLOW}
[DOG, IS, YELLOW] {THE}
[IS, YELLOW, THE] {CAT}
[YELLOW, THE, CAT] {IS}
[THE, CAT, IS] {YELLOW}
[CAT, IS, YELLOW] {SO}
[IS, YELLOW, SO] {IS}
[YELLOW, SO, IS] {THE}
[SO, IS, THE] {DOG}
[IS, THE, DOG] {THE}
[THE, DOG, THE] {CAT}
[DOG, THE, CAT] {THE_END}

Study the table above and make sure you understand how it was generated before you read further!

We will now describe how the data structure above can be used to create a randomly generated passage! Let's use chains of length two, so focus your attention on the center column from the table above.

We start with the first chain (of length 2) that appeared in the original text:

THE DOG

Now we have to choose a single word to follow this chain. We look up this chain in the table, and find that there are two choices for a following word: "IS" or "THE". We use a random number generator to pick. Let's suppose it chooses the second one (THE). Now we have:

THE DOG THE

We now take the ending chain [DOG, THE] and look for a word to follow it. According to the chart, there is only one choice: CAT. So now we have:

THE DOG THE CAT

We now take the chain [THE CAT] and look for a word to follow it. We have two choices (IS, or THE_END) and so we choose one randomly. Let's suppose we choose the second one, "THE_END". Now we have:

THE DOG THE CAT THE_END

We stop now, since we encountered the terminal symbol "THE_END".

Let's consider another example. This time we'll use chains of length 1. We start with the first chain from the original text:

THE

When we look up the chain [THE] in the chart, we see that we have a list of four things (some repeats) to choose from. We use a random number to choose an index from 0 to 3. Let's suppose it gives us 3, which corresponds to CAT. Now we have:

THE CAT

Now we look up the chain [CAT] in the chart. Two possible endings: IS or THE_END. Let's suppose we randomly choose IS:

THE CAT IS

Looking up IS, we see three possible endings. We use a random number generator to give us a value from 0 to 2. Let's suppose it gives us 2:

THE CAT IS THE

Next we look up the chain [THE]. Again, the random number generator gives us a value from 0 to 3. Let's pretend it is 1:

THE CAT IS THE CAT

Now looking up [CAT], we see two possible endings, IS or THE_END. Let's imagine we select the second one, so that the final passage is:

THE DOG IS THE CAT THE_END

Consider what would happen if you use this technique with this particular input data to generate a random passage using chains of length 3.

Data Structures

During a particular run of the program, the length of the chains will remain fixed. We must read some words as input, and then construct data structures as depicted above for that particular chain size.

A "chain" will be stored as a vector of strings.
A "list of endings" will also be stored as a vector of strings.

We will use "parallel vectors" to store the list of chains and their corresponding endings. In other words, we will use a vector<vector<string>> to store all of the chains and we will use a vector<vector<string>> to store the corresponding endings.

For example, suppose the chain length is currently 2, and we use the example above as our input. We will construct two big vectors:

chains will be a vector<vector<string>> containing the 9 chains (each of which is a vector of strings):
[[THE, DOG], [DOG, IS], [IS, YELLOW], [YELLOW, THE], [THE, CAT], [CAT, IS], [YELLOW, SO], [SO, IS], [IS, THE], [DOG, THE]]
endings will be a vector<vector<string>> containing the 9 corresponding "ending lists" (each of which is a vector of strings):
[[IS, THE], [YELLOW], [THE, SO], [CAT], [IS, THE_END], [YELLOW], [IS], [THE], [DOG], [CAT]}

These two vectors are "parallel", which means that, for example, the third entry of the chains vector corresponds to the third entry of the endings vector.

Syntax Hint

The g++ compiler is very fussy about spacing when you compose templates. Instead of typing:
vector<vector<string>>

Be sure to use:
vector< vector<string> >

Getting the Project Files

Login to the grace system. Go into the course directory; go into the "student" directory, and from there go into your own personal directory. Once you are in your own directory, type:

cp -r ../../public/Proj1 .
(Notice the "space dot" at the end. Also, don't forget to use the -r option.)

That should give you the necessary files in a directory called Proj1.

driver.cpp

Here we have given you a main function that you can compile with your code to try it out. This main function is not being used for any testing, so feel free to modify it if you want.

Before you read any further, look over the main function we have provided to see how the program will work.

You will see that it will read three parameters from the command line. They are:

name of the input file -- you can use any text file
size of the chains to be used -- we recommend values from 1 to 3, but your code should work with any size bigger than 0.
seed for random number generator -- use any integer. (If you use the same integer for multiple runs, you will always get the same output.)

To compile the main function with your code type:

make driver

This will produce an executable called "driver" that you can run. (Be sure to provide the three command line arguments.) For example:

./driver myFile.txt 2 7777

Sample Input Files

You can run the driver with just about any text file, but we have provided two text files for you to play around with:

forecast.txt -- a weather forecast
Godfather.txt -- The entire script from the movie "The Godfather". If you run the driver with this input file, expect it to take a few minutes to produce any output!

textGenerator.cpp

You will be adding code to a file called TextGenerator.cpp. You will see that the following function has already been written for you. DO NOT MODIFY IT!

readWordsFromFile -- This function will read the contents from a specified text file and populate a vector of strings with each word that it finds in the file. You will use this list of words to construct the your data structures.

You may write as many functions as you want, but you must include the following functions:

createDataStructures -- You will see the call to this function in main. It looks like this:
createDataStructures(originalWords, chains, endings, CHAIN_SIZE);
Notes:
- originalWords is a vector of strings representing the original text that will be used to create the data structures.
- chains and endings are empty objects of type vector<vector<string>>. The function will populate these two vectors with the data taken from the "originalWords", as described previously.
- The final argument, CHAIN_SIZE is just an int that specifies how long the chains must be.
- Be sure to create a string that says "THE_END" to use as we have shown in the preceeding examples.
- Be sure to populate your data structures in the same order that things were populated in the examples we have shown previously. If you construct them in a different order you will not pass our tests.
- Do not add or remove any punctuation marks that may or may not be present in the originalWords.
generateRandomText -- You will see the call to this function in main>. It looks like this:
generateRandomText(chains, endings, CHAIN_SIZE);
Notes:
- chains and endings are the data structures that were populated by the createDataStructures function.
- CHAIN_SIZE is just an int that specifies how long the chains must be.
- The function will generate random text as described previously and will send it's output directory to the standard output stream using cout
- IMPORANT When you need to select an ending randomly from the list of endings, use the rand() function. This function will return a large integer. Use the modulus operator to restrict the range. For example, if you are trying to select one of 4 possible endings, use the following expression to determine the appropriate index:
  int index = rand() % 4; // index will be in the range 0 to 3
  Failure to follow this procedure will result in failing all of the tests!
- You should put a single space between each word in the output
- There should be just a single endl at the very end of the text (after you display the word "THE_END").
- Do not add or remove any punctuation marks that may or may not be present in the words stored in your data structures.

textGenerator.h

Be sure to update the file textGenerator.h so that it includes function prototypes for the two functions that you are writing. These are part of the API for this module, so it is important to include their prototypes in the header file. (You do not need to include prototypes for other functions you have written, since they are not part of the API -- they are like "private" methods in Java.)

Using the Makefile (Provided)

As discussed previously, to build an executable program that will generate random text using your code, type:

make driver

To run the executable, type something like:

./driver forecast.txt 2 878787

There are three public tests. To run them type either "make pub1", "make pub2", or "make pub3". If you'd like to see the sourcecode for the public tests, they are in the files testDataStructures.cpp, testTextGenerationFunction.cpp, and testConstness.cpp respectively.

Submitting

To submit the assignment, make sure you are inside the project directory and then type:

java -jar submit.jar
(Remember that you might have to type "tap -q java" before attempting to submit.) The first time you submit it will ask you to authenticate -- use your University of Maryland directory ID and password.

After you've submitted, go to the Winter submit server to see your submission. In addition to the three public tests, there is one secret test. You will not be able to see the results of the secret test. (There are no "release tests" for this project, just public tests and a secret test.)

Have fun!

Web Accessibility

length 1	length 2	length 3
[THE] DOG [DOG] IS [IS] YELLOW [YELLOW] THE [THE] CAT [CAT] IS [IS] YELLOW [YELLOW] SO [SO] IS [IS] THE [THE] DOG [DOG] THE [THE] CAT [CAT] THE_END	[THE, DOG] IS [DOG, IS] YELLOW [IS, YELLOW] THE [YELLOW, THE] CAT [THE, CAT] IS [CAT, IS] YELLOW [IS, YELLOW] SO [YELLOW, SO] IS [SO, IS] THE [IS, THE] DOG [THE, DOG] THE [DOG, THE] CAT [THE, CAT] THE_END	[THE, DOG, IS] YELLOW [DOG, IS, YELLOW] THE [IS, YELLOW, THE] CAT [YELLOW, THE, CAT] IS [THE, CAT, IS] YELLOW [CAT, IS, YELLOW] SO [IS, YELLOW, SO] IS [YELLOW, SO, IS] THE [SO, IS, THE] DOG [IS, THE, DOG] THE [THE, DOG, THE] CAT [DOG, THE, CAT] THE_END