CMU 15-211 Fundamental Structures of Computer Science I

Assignment # 1: Fancy Electronic MAD-LIBS

Due: Monday, January 29, at 11:59 pm

This assignment is due electronically by 11:59 PM on Monday Jan. 29 (Monday night). Read Section 8 in the Course Information guide for details on the electronic handin procedures. Also, please put your name and recitation section at the top of your handin. Programs in all homework assignments should be well documented -- see the C++ Programming Guidelines handout for details. Before starting on this assignment, we encourage you to go through the ObjectCenter Tutorial that was handed out.

1. The assignment

MAD-LIBS is a game played between two people that we might call the Reader and the Chooser. In this game there is a text, usually some story, in which some of the words are replaced by parts-of-speech indicators. For instance, the text might be:
Once upon a time there were two professors named [name] and [another_name] who liked to stay up late at night and eat [name]'s [plural_noun].
(This would be a really short game). The reader looks at this text, which is hidden from the chooser, and asks the chooser for words to fill in the place-holders representing parts of speech. Then, when all the spaces are filled in, the reader reads out loud the (usually very silly) resulting story. For instance, a transcript of a game using the above text might go like this:
Reader: give me a name.
Chooser: Danny.
Reader: give me another_name.
Chooser: Bruce.
Reader: give me a plural noun.
Chooser: floppy disks.
Reader: OK, ``Once upon a time there were two professors named Danny and Bruce who liked to stay up late at night and eat Danny's floppy disks.''

This game is slightly fancier than the standard MAD-LIBS game because each response by the Chooser (like ``Danny'') may be used in several places (all places that have ``name'').

In this assignment, you will write a program that plays the role of the Reader in this game. The user will play the role of the Chooser. The text will be stored in a file, and your program will read it in, asking the user for words to fill in the parts of speech listed. When all the parts of speech are filled in, your program will then print out the resulting story.

We have broken this task into five parts, but your answers to all these parts may be placed into a single file. (I.e., you don't need to turn in 5 files). We have also given you some startup code and definitions in the files madlib.c and madlib.h in the assignments/assign1 directory. These files contain code for doing file I/O and some useful type definitions. We suggest you just copy them over to your working directory and add your code to them.

1.1. Part A - Inserting (20pts)

  1. Consider the following definition of a list type:

    typedef char word_t[40];
    struct list_struct {
      word_t word;
      list_struct *next;
    typedef list_struct *list_t;   // list_struct is a struct, list_t is a pointer.

    In this definition, a list_struct contains two things: a character array of length 40, and a pointer that may point to another list_struct. (A real C++ hacker would use a ``class'' instead of a ``struct'' but structs work fine for our purposes.)

    Write a function insert_word with the prototype: list_t insert_word(list_t lis, char * new_word);

    Your function should take a list and a word and insert the word onto the front of the list, returning the new list created. You may assume that the word has at most 39 characters. For instance, suppose we run the code fragment:

       word_list_t mylist;
       mylist = insert_word(NULL, "hello");
       mylist = insert_word(mylist, "goodbye");

    Then, at the end, mylist will be a list with its first element containing the word ``goodbye'' and the second element containing the word ``hello''.

  2. Consider the following structure for a list where each element contains two words.

    struct pair_list_struct {
      word_t pattern, replacement;
      pair_list_struct *next;
    typedef pair_list_struct *pair_list_t;

    Write a function insert_word_pair with the prototype:

    pair_list_t insert_word_pair(pair_list_t pl, char *pattern, char *replacement);

    This function should do exactly what insert_word does, but the node it inserts contains two strings (pattern and replacement), not just one.

1.2. Part B - Printing (20 pts)

Write a function that prints out the words in a list in the reverse order that they appear in the list. Your function should have the prototype: void print_in_reverse(list_t lis);

Your function should print out the words in the list with a single space separating adjacent pairs of words. This function can easily be written recursively.

1.3. Part C - Searching (20 pts)

Write a function with the following prototype:

     char * find_replacement(pair_list_t lis, char * pattern);

This function searches lis for an element whose pattern component matches the given pattern, and returns the corresponding replacement. If there is no such pattern it returns NULL. For example, suppose:

   pair_list_t mylist;
   mylist = insert_word_pair(NULL, "*verb", "runs");
   mylist = insert_word_pair(mylist, "*person", "John");

Now find_replacement(mylist, "*verb") returns "runs", and find_replacement(mylist, "doggie") returns NULL.

Note: This can be implemented either recursively, or with a for or while loop. The standard strcmp() function will be useful for finding the matching pattern.

1.4. Part D: The MAD-LIBS program (40pts)

Now your job is to write the MAD-LIBS program. We encourage you, though we do not require you, to use your solutions to parts (A) through (C) and to use the code we have given out, in your solution to this part. If you wish, you may change the function prototypes or the struct definitions we have given, but you shouldn't need to. If you decide not to use your solutions to (A) through (C) or not to use the code we have provided or to change the structs or function prototypes, be especially careful to document your code well. (Of course, you should document your code well in any case.)

We have placed object code in the assign1 directory (called madlib.dec for the DECstation, madlib.sparc for the sparcstation, and madlib.hp for the Hewlet Packard workstation) showing the sort of behavior that we expect from your code. We have placed sample text files in the files input1, input2, and input3.

Text file format: The format of a text file is that words representing parts of speech have a ``*'' as their first character. For instance, the above example (also in input1) looks like:

Once upon a time there were two professors named *name and *another_name who liked to stay up late at night and eat *name 's *plural_noun.
This way you can determine if a word is a part-of-speech by just looking at the first character.

File I/O: madlib.c contains a code fragment that asks a user for a file name, and then attaches that to an input stream called ``the_text_file''. You can read words from the_text_file just like you read words from cin. For instance, if foo is a character array, you can type: the_text_file >> foo

to read a word into foo.

You will need to use this stream to read words from the text file, you will need to use ``cout'' to print requests to the user, and you will need to use ``cin'' to receive the responses from the user.

Your job: Your job is to write a program with the same basic behavior as the object code we have handed out. It should read through the text file one word at a time. Each time it sees a word that begins with '*', it should check to see if that word has already appeared in the text. If so, then the program should go on to the next word in the file. If not, then it should ask the user for a part of speech specified by the word. Once the program has finished reading the file, it should print out the words in the text file with each part of speech replaced by the user's word. Note that even if the same part of speech word, such as ``*name'' appears more than once in the file, the user should only be asked to provide that word once, and the user's response should replace all occurrences of the word. You may assume that each part of speech and each response of the user is a single word. For instance, the response to ``Give me a noun:'' won't be ``telephone pole'', though it might be ``telephone_pole''. Also, you may assume that each word in the file and each word given by the user is at most 39 characters long. You should not assume any maximum number of words in the text files. Finally, it is fine if the output of your program puts all the words onto one single line (just like our object code does). The reason for this is that the ``>>'' operator skips blanks, tabs, and newlines in the text file.

Hints: The easiest way to do this is to process the text file one word at a time. As you process the text file, you should maintain two lists, one that contains the bindings between the different part of speech words that have appeared in the text file and the corresponding responses from the user, and another that contains the words of the output (in reverse order). Each time a word is read from the text file, it (or the corresponding replacement word from the user if it is a part of speech) is inserted at the front of the output list. After creating the list of output words in reverse order, the solution to part (B) can be used to print out the words in the list. Also, one convenient fact about C++ is that the ``>>'' operator returns 0 when it gets to the end of a file.

Good luck!