CS 16, Summer 2012
Programming Project 3

Due: Friday, August 31, 11:59pm
Worth: 4% of final grade (6% of bonus is also available)

1. Write a C program that prompts the user for a series of letters. The program will read in the letters and print out which dictionary words can be made from the provided letters. The dictionary is provided. See below for an example run with a dictionary containing “able”, “anvil”, “ape”, “apple”, and “apt”:

   -bash-4.2$ ./words enter letters: atebp atebp: ape apt enter letters: moo moo: enter letters: appble appble: able ape apple enter letters: exit -bash-4.2$

   • The source code file must be named words.c and we suggest you create a directory named ~/cs16/p3 to store it in. Type your name and the date in a comment at the start of the file.
   • For full credit, the program must behave and produce results exactly like our solution. You can run that solution from your CSIL account as follows:
     
     ~kyledewey/cs16/p3/words
     Notice especially:
     (a) The program keeps asking the user for letters until the letters are exit.
     (b) The program prints words in the dictionary that could be made, in the same order as specified in the dictionary.
     (c) The program prints out what letters were typed in, followed by a colon (:), followed by a list of the words that could be made (if any).
     (d) Each word that could be made is prefixed by a tab character (\t).
   • You may make the following assumptions about input letters:
     (a) No more than 99 input letters will be entered per group. (For example, in the output for words above, “atebp” and “moo” are groups of letters.)
     (b) Each sharacter will be lowercase, in the range a-z (inclusive). You do not need to worry about spaces or special characters, since they fall out of this range.
   • Use ~kyledewey/cs16/p3/words_skeleton.c as a base to develop your program. Note that the dictionary specified in this file must be identical to the dictionary turned in. You may add or remove words from this dictionary as you see fit (adjusting the DICT_SIZE constant as necessary) while testing, but the code turned it must have this exact same dictionary.
   • In very general terms, determining if a given word can be made from the given letters will require counting how many distinct kinds of letters there are in the given letters and in the words. For example, assume that the word “bull” is in the dictionary. The word “bull” contains 1 ‘b’ character, 2 ‘l’ characters, and 1 ‘u’ character. Now say the input letters were “lblld”. In “lblld”, we have enough ‘b’ characters for “bull”, since “lblld” contains at least 1 ‘b’ character. Similarily, “lblld”, has enough ‘l’ characters for “bull”, since “lblld” contains at least 2 ‘l’ characters. However, “lblld” does not have at least 1 ‘u’ character, and as such we know that we cannot make “bull” from “lblld”. There are a LOT of different ways to perform this sort of counting, but the shortest (and likely most efficient) way will probably involve an array of 26 integers, one for each letter of the alphabet. The first index in this array refers to the number of ‘a’ characters, the second index the number of ‘b’ characters, and so on. A nifty way to access the integer corresponding to the appropriate character given an index is via:
     
     array[ character - ‘a’ ]
     (Of course, you should take care to understand what this code does before you use it!)
   • It is best to break this down into multiple independent problems, and build them individually. Once these have been shown to work individually, they can be tied together to solve the whole problem. One possible logical progression is below (you do not have to do it this way if you so choose):
     (a) Write code that can count the number of times each character appears in a given word.
     (b) Write code that can determine if a word can be made given the letter counts for the word and the input letters.
     (c) Iterate through the dictionary, executing the above code for each word in the dictionary. Print out the words that can be made, using the format specified before.
   • It is highly recommended to embrace functions with this code. For example, the code for counting the letters in dictionary words and in the input letters should be identical. As such, it is best to place this common code in one function, and call the function twice with different parameters. (As in call the function once with the dictionary word, and once with the input letters.) You can still get full credit without using functions, but there will likely be repetitive code and it will be more difficult to understand.
   • For full credit, you may not use goto. goto can lead to ugly code fast, it is very rarely used in practice, and it generally not well-received by other programmers. You may be interested in reading one of the original writings advocating against goto, written a whopping 44 years ago.
2. Compile the program and thoroughly test it at CSIL. Make sure the version that you turn in will successfully compile and execute, so we will be able to test it too. Remember that partial credit will be awarded for partial solutions - but only if we can test your solution. That means you should only turn in working code, and remove (or completely "comment out") any failed attempts to solve the more advanced problems. If we cannot compile and test your program, then we cannot award more than minimal credit for your efforts.
3. Go to CSIL (in person unless you can manage this step remotely without any assistance from us). Open a terminal window, cd to the same directory as your source code file, then type the following:
   
   turnin p3@cs16 words.c
   

Bonuses

A series of bonuses are available with this project. In total, your final grade in the whole class can be boosted by as much as 6%. However, you may find these bonuses to be quite challenging. They are comprehensive of the entire course. Note that if you do choose to persue the bonuses, be advised that you must do them in sequence. That is, you cannot get credit for a later bonus without doing all the earlier ones. To get credit for bonus #2, you must have completed bonus #1, to get credit for bonus #3 you must have completed bonuses #1 and #2, and so on. A description of the bonuses follows.

1. Bonus #1 (+2%): Read in the dictionary words from a file. The name of the dictionary file is “dictionary.txt”. An example dictionary file can be found at ~kyledewey/cs16/p3/dictionary.txt. You may make the following assumptions about the dictionary file:
   (a)Each word is on its own, separate line.
   (b)Each word consists only of lowercase letters in the range a-z.
   (c)The maximum length of a single word is 99 characters.
   (d)The maximum number of words is 100.
   If you cannot open the dictionary file, you should print “Failed to open dictionary file "dictionary.txt"”, followed by a newline, and then exit the program. If you aim for this bonus (and nothing beyond it), you should save your code as words1.c. You can run this particular solution from your CSIL account as follows:
   
   ~kyledewey/cs16/p3/words1
   This bonus should be submitted with this command line:
   
   turnin p3@cs16 words1.c
2. Bonus #2 (+0.5%): There is no longer an arbitrary maximum word length. Words can be as long or as short as they want to be. If you aim for this bonus (and nothing beyond it), you should save your code as words2.c. You can run this particular solution from your CSIL account as follows:
   
   ~kyledewey/cs16/p3/words2
   This bonus should be submitted with this command line:
   
   turnin p3@cs16 words2.c
3. Bonus #3 (+0.5%): There is no longer an arbitrary maximum number of words in the dictionary. The dictionary can contain as many or as few words as it wants. If you aim for this bonus (and nothing beyond it), you should save your code as words3.c. You can run this particular solution from your CSIL account as follows:
   
   ~kyledewey/cs16/p3/words3
   This bonus should be submitted with this command line:
   
   turnin p3@cs16 words3.c
4. Bonus #4 (+0.5%): Instead of prompting the user for input letters, read in the input from a file named “input.txt”. Each group of letters is separated by a newline. An example input file can be found at ~kyledewey/cs16/p3/input.txt. You may continue to assume that each group of letters will not exceed 99 letters. If you cannot open the input file, you should print “Failed to open input file "input.txt"”, followed by a newline, and then exit the program. If you aim for this bonus (and nothing beyond it), you should save your code as words4.c. You can run this particular solution from your CSIL account as follows:
   
   ~kyledewey/cs16/p3/words4
   This bonus should be submitted with this command line:
   
   turnin p3@cs16 words4.c
5. Bonus #5 (+0.5%): Instead of printing out the words to the terminal, write the results to an output file named “output.txt”. An example output file can be found at ~kyledewey/cs16/p3/output.txt. If you cannot open the output file, you should print “Failed to open output file "output.txt"”, followed by a newline, and then exit the program. If you aim for this bonus (and nothing beyond it), you should save your code as words5.c. You can run this particular solution from your CSIL account as follows:
   
   ~kyledewey/cs16/p3/words5
   This bonus should be submitted with this command line:
   
   turnin p3@cs16 words5.c
6. Bonus #6 (+2%): Read in the input file, dictionary file, and output file from the command line. The format should be like the following: ./words6 -d dictionary_file.txt -i input_file.txt -o output_file.txt, where
   -d means that the next argument should refer to a dictionary file name,
   -i means that the next argument should refer to an input file name, and
   -o means that the next argument should refer to an output file name.
   The ordering of the these switches (also called flags, a.k.a. anything that begins with a -) does not matter. In other words, both
   ./words6 -o output_file.txt -d dictionary_file.txt -i input_file.txt and
   ./words6 -i input_file.txt -o output_file.txt -d dictionary_file.txt
   ...are also valid. Note that your error messages from before that print out file names should be updated so that they print the file names of whatever the user specified. (I.e. if the user specified a nonexistent dictionary file named “badDictionary.txt”, it should print “Failed to open dictionary file "badDictionary.txt"”.)
   Additionally, not all of these options need to be provided, or even any at all. There are also a wide variety of error conditions for the arguments. If an error condition occurs, then the nature of the error should be printed out (always terminated with a newline), and the program should be exited. (You may be interested in using the exit( int ) fuction in stdlib.h; see this link if you are interested.) The conditions under which an error occurs along with what should be printed for each error are below:
   (a)If no dictionary is specified, as with ./words6 -i input_file.txt -o output_file.txt, then the default is to try to use “dictionary.txt” as a dictionary file name.
   (b)If no input file is specified, as with ./words6 -d dictionary.txt -o output_file.txt, then the default is to ask for input from the user interactively (as with the original words program).
   (c)If no output file is specified, as with ./words6 -d dictionary.txt -i input_file.txt, then the default is to print out the matching words to the terminal (as with the original words program).
   (d)If the user skips over putting in a dictionary and instead jumps to another switch, as with ./words6 -d -i input_file.txt, then it should print “Expected a dictionary, but received "‹‹whatever switch was received here››"”. For this particular command line, the appropriate thing to print would be “Expected a dictionary, but received "-i"”.
   (e)If the user skips over putting in an input file and instead jumps to another switch, as with ./words6 -i -d dictionary_file.txt, then it should print “Expected an input file, but received "‹‹whatever switch was received here››"”. For this particular command line, the appropriate thing to print would be “Expected an input file, but received "-d"”.
   (f)If the user skips over putting in an output file and instead jumps to another switch, as with ./words6 -o -d dictionary_file.txt, then it should print “Expected an output file, but received "‹‹whatever switch was received here››"”. For this particular command line, the appropriate thing to print would be “Expected an output file, but received "-d"”.
   (g)If multiple skips were made in this fashion, as with ./words6 -i -o -d, then only the first skip should be printed. For example, with this particular command line, the appropriate thing to print would be “Expected an input file, but received "-o"”.
   (h)If a user skips over putting in the dictionary file at the end of the command line, as with ./words6 -i input_file.txt -d, then it should print “Expected a dictionary, but it is missing”.
   (i)If a user skips over putting in the input file at the end of the command line, as with ./words6 -d dictionary_file.txt -i, then it should print “Expected an input file, but it is missing”.
   (j)If a user skips over putting in the output file at the end of the command line, as with ./words6 -i input_file.txt -o, then it should print “Expected an output file, but it is missing”.
   (k)If a user specifies multiple dictionary files on the command line, as with ./words6 -d dictionary_file1.txt -d dictionary_file2.txt, then it should print “Attempted to pass multiple dictionary files”.
   (l)If a user specifies multiple input files on the command line, as with ./words6 -i input_file1.txt -i input_file2.txt, then it should print “Attempted to pass multiple input files”.
   (m)If a user specifies multiple output files on the command line, as with ./words6 -o output_file1.txt -o output_file2.txt, then it should print “Attempted to pass multiple output files”.
   (n)If there is some other argument passed without context, as with the command line ./words6 -i input_file foobar, then it should print “Unrecognized argument: "‹‹whatever argument was not recognized››"”. For this particular command line, the appropriate thing to print would be “Unrecognized argument: "foobar"”.
   (o)If there is an error in the specified command line, then the first error found going left to right should be the only one reported (as specified above), and then the program should terminate. For example, with the very erroneous command line ./words6 -i input_file1.txt -d -i input_file2.txt -o, the error reported should be “Expected a dictionary, but received "-i"”, since that is the first error encountered going left to right across the different arguments.
   If you aim for this bonus, you should save your code as words6.c. You can run this particular solution from your CSIL account as follows:
   
   ~kyledewey/cs16/p3/words6
   This bonus should be submitted with this command line:
   
   turnin p3@cs16 words6.c

To get a better idea of how challenging each bonus may be (and whether or not a persuing a particular bonus would be worth the effort), you may be interested in some summary statistics of my own code as more bonuses were added, along with my impression of the difficulty / hints:

Version	Number of lines (including whitespace)	Number of functions	Dificulty / hints (Purely subjective)
Original (no bonuses)	70	5	Less tricky than Project #2
With bonus #1	96	7	A bit annoying, especially with reading in dictionary words. Somewhat surprisingly, malloc and strcpy (from string.h) were needed.
With bonuses #1 - #2	109	7	No, now reading in dictionary words is annoying. realloc was needed.
With bonuses #1 - #3	110	7	Same process as in bonus #2, so not much tricker than that.
With bonuses #1 - #4	135	10	A bit of extra work to open the file, but existing code was able to be adapated without much change.
With bonuses #1 - #5	149	12	Very similar to bonus #4. The adaption was almost identical.
With bonuses #1 - #6	276	19	Ouch. Once you see a way to handle the ordering portion it becomes straightforward, but lengthy.

(This is just to get a rough idea; your milage may vary.)

Created by Kyle Dewey