For this evaluative assignment, you will write a program to tell a random
story (kind of like Mad Libs) that generates a story, given a story
template and a list of words to choose from.

For example, if you had a story like the one in story.txt:

Once upon a time, there was a _animal_ who lived in a very _adjective_
_place_.

And some words to choose from like in words.txt:

animal:dragon
animal:walrus
place:cave
adjective:peculiar
adjective:scary
adjective:peaceful

The program might produce:

Once upon a time, there was a walrus who lived in a very peaceful
cave.

The story template will be provided in an input file, where the "blanks"
are the category name preceded and followed by an underscore
("_"). Eventually, your program should replace this blank with a word from
the word list of the appropriate category. The categories and word choices
are provided in a separate input file with the category name, colon (":"),
then word. Your program should print the story to stdout. 

You will write this program in four steps. The first step focuses on
parsing the story template. The second is reading categories and words,
storing them into an appropriate data structure. Step 3 combines the
functionality of steps 1 and 2 to create a random story program. Step 4
adds the option of not reusing words.

Open provided.h, and you will see two struct definitions, one for a
category_t to store information about a category, such as "animal" or
"verb" with an array of words that will contain possible replacement words
for that category. You will also see a struct catarray_t for an array of
category_t's and the prototypes for two functions, which we provide. 

The function

const char * chooseWord(char * category, catarray_t * cats);

takes a string representing the category name and a catarray_t * "cats",
from which it will select a word in the requested category. If "cats" is
not NULL, this function returns a pointer to the string in "cats"--it does
not allocate new memory. If the requested category does not exist in
"cats", or the category does not have any words, the function will exit the
program with a failure status. If "cats" is NULL, the function will return
the string literal "cat", i.e. chooseWord("verb", NULL) would return
"cat". 

The function

void printWords(catarray_t * cats);

prints out the catarray_t * "cats" for the purpose of testing the contents
of that data structure.

The definitions of these functions are in provided.o, which the Makefile
will link with your code.

You MUST submit a Makefile that compiles the program for each step, and
each step must work as described. If you name your source code files like
we suggest, you will not need to modify the provided Makefile, but you
may if you wish.

Step 1
===========================================================================

Write the program story-step1, which takes one command line argument: the
name of the file to read the story template from. This program should parse
the story template by printing the story and replacing blanks with the word
"cat". Your code should call the provided function chooseWord, for this
step passing in NULL as the second argument to get return value "cat".

For example, for the input in story.txt, this program would print:

Once upon a time, there was a cat who lived in a very cat
cat.

For the format of the input file, each blank must begin and end with an
underscore '_'. If a blank begins, it must have a matching underscore on
the same line; otherwise, it is an error. If there is anything wrong with
the input file, you should print an appropriate error message and exit with
a failure status.

As you plan your code for this step, consider how you can write re-usable
code for the subsequent parts. You will want to write as much code as
possible in rand_story.c to avoid code duplication. Then you can write the
prototypes of functions in rand_story.h and include this in your
story-step1.c.

Before you try to build your story-step1, you should do a few small things.
 1.  The Makefile is currently setup to build all 4 steps.  Find the line
 in it that says
   PROGS=story-step1 story-step2 story-step3 story-step4
 and comment out steps 2-4
   PROGS=story-step1 # story-step2 story-step3 story-step4
  As you do future steps, uncomment the program for the step you are working on.
 2. Create a .gitignore file in this directory that says
    story-step?
    rand_story.o
    
    This will cause git to ignore the object file and binaries you are building

Once you have tested this step to your satisfaction, add/commit/push/grade
to use the pregrader before going on to the next step.

As before, the pregrader will read your tests.txt file and use your testcase.
Unlike before, you do not need to put #success or #error (though we will ignore
any line that starts with # if you want to write comments for yourself).

You should write your tests for this step like this (note that the
provided test cases are already listed in tests.txt)

story-step1 mystory1.txt
story-step1 bogusstory.txt

Step 2
===========================================================================

Write the program story-step2, which takes one command line argument: the
name of the file with the categories and words. This program should read
from the file and store the words into a catarray_t and print them using
the provided function printWords.

For example, if given the file words.txt, the output would be:

animal:
  dragon
  walrus
place:
  cave
adjective:
  peculiar
  scary
  peaceful
  
Each line of the input file must have a colon (':'). The category name may
be any characters (except a colon), and the replacement word is everything
following the colon until (and not including) the newline. We place no
other restrictions on the words or the order the lines appear in the
file. If the input file does not have the right format, you should print an
appropriate error message and exit with a failure status.

Again, consider how you can write as much of this code in rand_story.c in a
re-usable way.

Remember to go back into your Makefile and edit PROGS so it now
includes step2.

Once you have tested this step to your satisfaction and ensured that step 1
still works, add/commit/push/grade before going on to the next step.

Don't forget to write lots of good tests for the pregrader. They should
start with story-step2, like

story-step2 words.txt
story-step2 mytrickywords.txt

etc.

Step 3
===========================================================================

Write the program story-step3, which takes two command line arguments: the
name of the file with the categories/words and the name of the file for the
story template. This program should make use of the functions you wrote
for step 1 and step 2, but it should add the functionality to 1) randomly
choose a word from the named category to replace each blank and 2) support
references to previously used words.

If the category name is a valid integer of at least one, you should replace
the blank with a previously used word, counting backwards from the current
word, such that 1 refers to the immediate previous word.

Otherwise, if the category name is a category in the catarray_t, you should
call chooseWord, which will return a random choice from that category
(since the second argument is not NULL). If a category name is neither a
valid integer nor a valid category name, the program should exit with a
failure status.

Note that blanks such as _-1_ _0_ _2asdb_ are not inherently invalid.
They are not backreferences, but may be category names (so would be valid
iff such a category exists).

For example, if the story template is story2.txt and the words file is
words.txt, the output would be:

Once upon a time, there was a walrus. This walrus lived in a very
scary cave. One day, it left its scary cave and met a walrus.

Note that in this example, if "walrus" is the word chosen for the first
_animal_ blank, the _1_ blank *must* be replaced with with "walrus". The
second _animal_ blank might be replaced with either "walrus" or "dragon",
but the random seed used in provided.o made chooseWord return "walrus" both
times. 

Hint: You will want a way to keep track of words that have been used. The
struct category_t already has an array of words and the length of that
array. You could maintain a category_t that keeps track of used words.

Remember to update PROGS in your Makefile.

Once you have tested this step to your satisfaction and ensured that steps
1 and 2 still work, add/commit/push/grade before going on to the next step.

Don't forget to write lots of good tests for the pregrader.  They should
generally look like

story-step3 words.txt story.txt
story-step3 trickywords.txt trickystory.txt

etc

Step 4
===========================================================================

Write the program story-step4, which takes one optional and two required
command line arguments: an option "-n" indicating no reuse of words, the 
name of the file with the categories/words, and the name of the file for
the story template. This program should make use of the functions you wrote
in previous steps, but should add optional functionality to prevent the
reuse of a word from a category. That is, if the argument "-n" is given,
your program should ensure that chooseWord will not return a word that has
already been used. Numbered blanks should still reference a previously used
word as in step 3.

For example, if you run this program

./story-step4 -n words.txt story2.txt

The output should be:

Once upon a time, there was a walrus. This walrus lived in a very
scary cave. One day, it left its scary cave and met a dragon.

If this program is run without the "-n" argument, its behavior should be
identical to the program in step 3.

Hint: consider passing an int to your story telling function that indicates
whether words should be removed from the data structure after they are used
in the story.

Remember to update PROGS in your Makefile.

Once you have tested this step to your satisfaction, git add/commit/push/grade,
to use the pregrader/submit your work.

Don't forget to write testcases for this step, which should look generally like

story-step4 words.txt story.txt
story-step4 trickywords.txt trickystory.txt
story-step4 -n words.txt story.txt
story-step4 -n trickywords.txt trickystory.txt

Code Quality
===========================================================================

Your code will also be graded for its quality. Your grader will assess the
quality of the abstraction, naming, formatting, and documentation of your
code. For this assignment, make sure the functions you write use good
abstraction, variable names are meaningful, formatting is standard (you can
do this automatically by saving in Emacs; otherwise, you should run
clang-format on your source code file), and that you document your work by
adding a comment describing each of the functions you write, as well as a
comment if you write anything complex or unusual.

Reminders
===========================================================================

Your code will be graded ONCE after a hard deadline. You may run "grade" as
many times as you like, but the last commit after which you run grade
before the deadline will be your submission. We have provided a
"pre-grader," which will compile and run YOUR test cases. You
should provide an extensive (but reasonable) set of test cases
to ensure your code works.

However, you should still be testing your code before you submit. 

This is an INDIVIDUAL assignment. You are only allowed to communicate
regarding this assignment with an instructor or TA.