submitaps105s command to electronically submit your solution. The lab is due on Monday, March 22 at 11:59 PM.
The objective of this lab is to give you practice writing C programs that use strings and recursion.
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:
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.
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.
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:
lettersRemaining is the string from which we are subtracting. Assume each character in this string is a lowercase letter of the alphabet. lettersRemaining is not to be modified by the function.
curWord is the string we are subtracting. Assume each character in this string is a lowercase letter of the alphabet. curWord is not to be modified by the function.
result is the array into which the result of the subtraction is placed. The function must assume that sufficient memory for result has already been allocated prior to the function call.
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.
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:
lettersRemaining has zero letters (i.e. it is the empty string), we have found a complete anagram. Print the anagram that was found, and return from the function.
lettersRemaining. If the subtraction is unsuccessful, move on to the next word. If it is successful, make a recursive call to printAnagrams, updating both parameters to reflect the subtraction and the new word that you have added to your current anagram.
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.
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'.