APS105 Lab 4

Objective

The objective of this lab is to give you practice writing C programs that use strings and recursion.

Anagram Generator

Take a look at the word festival. It has one f, one e, one s, one t, one i, one v, one a, and one l. There are many anagrams of festival. Here are a few:

Notice that each of these anagrams is built from valid words, and that they each use all of the letters from the original word. For example, vista fell is not an anagram of festival, because it tries to use two l's when only one is available.

In this lab, you will write a C program that outputs all anagrams of a string specified by the user. You will begin by writing and testing a helper function. You will then use that helper function to write a function that finds anagrams.

Part 1 - Setup

Download this dict.txt file. It is a text file that contains one English word per line, and it will be used as the dictionary of valid words. Only words found in this dictionary will be included in anagrams that your code generates. (If you prefer, the dictionary is also available by extracting this dict.zip zip file.)

Next, download reading.c and reading.h. reading.h includes the declaration of a function that you will use to read all of the words from a dictionary file given by the filename parameter.

Part 2 - Helper Function

Download the files helper.c and helper.h. In this part, you will write the subtract function in helper.c. Do not modify helper.h.

We can subtract string y from string x if and only if x contains all of the letters of y (including enough copies of those letters that are duplicated in y). For example, we can subtract evil from festival because the characters e, v, i, and l all exist in festival. We cannot, however, subtract flail from festival, because we would require two l's in festival to do so.

As more examples, we can subtract festival from festival, and we can subtract ll from fall. We cannot subtract all from caaaal.

If we can subtract one string from another (i.e. the subtraction is valid), then we can speak of the string of characters remaining after the subtraction. For example, subtracting evil from festival yields fsta. The order is not important here: fsta, fast, tsaf and so on are all correct results of subtracting evil from festival. As another example, subtracting fall from fall yields a string of no characters.

In the function subtract:

For this part, you are submitting only your subtract function, no main function. However, you'll certainly want to test this function by calling it with various inputs. Download the file test_helper.c, which includes a main function with some test cases. To test your subtract function, compile your code with the following command:
gcc -o subtract helper.c test_helper.c
You should add further test cases to test_helper.c; what I have included is enough just to get you started.

Part 3 - Generating Anagrams

Download the files anagram.c and anagram.h. In this part, you will write the recursive printAnagrams function in anagram.c; it will print all anagrams of a given string. Do not modify anagram.h.

A call of printAnagrams looks like printAnagrams ("festivall", ""); the first parameter, LettersRemaining, is the string (composed only of lowercase letters) whose anagrams will be printed, and the second parameter, currentWords, begins as the empty string. currentWords will be used in the recursion to keep track of the current anagram that is being built; it will be printed to the screen every time it represents a complete anagram of lettersRemaining.

Here is the strategy you should follow for implementing the recursive printAnagrams function:

For this part, you are submitting only your printAnagrams function, no main function. Like in part 2, however, you'll want to be able to test your function to make sure it's working properly. Download the file test_anagram.c, which includes a main function with some test cases. To test your printAnagrams function, compile your code with the following command:
gcc -o anagram helper.c reading.c anagram.c test_anagram.c
To verify your code on my sample test cases, compare your output with this sample test run output. Again, use other test cases as well, not just my samples.

Submitting your Lab

When you have completed the lab, use the command submitaps105s 4 helper.c anagram.c to submit your files. Make sure you name your files exactly as stated (including lower/upper case letters). You may check the status of your submission using the command submitaps105s -l 4, where -l is a hyphen followed by the letter 'ell'.