Here’s another random fact that I’m going to share about myself.  I went to North

Hollywood High School (NHHS) Highly Gifted Magnet (HGM) for school.  You probably are wondering what is a Highly Gifted Magnet and how does one get there?  You take

an IQ test and if you get at least a 150 (which is genius level), you are eligible to get in.  Believe it or not, at one point, I tested to that level.  (That is probably before all of these  adult beverages got into my system, probably lowering that mark. =])  Well, the reason I mention this is because we recently just celebrated our 25 year class reunion!  Twenty-  five years is more time than some of you reading this have been alive, which makes me a fossil to you at this point. (Yes, your professor has jokes and is self-deprecating. =])

The thing about a reunion is that it is a big game of trying to figure out who is doing what now, what happened to a certain person, and what are the stories and memories that

you take from that time.  It’s a fun game indeed.

There are also other games that you can play.  Take word games, like Scrabble and    Words with Friends, that require rearranging a combination of letters to make a word.  This type of arrangement is generally referred to as an anagram, while it's known as a permutation in mathematics.  This assignment will give you some experience thinking

about and writing recursive functions. Write a C++ program that searches for

"anagrams" in a dictionary. An anagram is a word obtained by scrambling the letters of some string. For example, the word "pot'' is an anagram of the string "otp." A sample    run of the program is given below. Your output does not have to be formatted exactly    the same as that shown in the sample, but it should be in a similar style. You can use   words.txt as your dictionary file and anagrams.cpp as an example of a main

program.

Since the purpose of this assignment is to give you experience using recursion, you     may not use any of C++'s iteration constructs (do, while, for, and goto) or any STL algorithms (if you have no idea what this means, you're OK). In fact, similar to

homework #2, you may only use the substr() and size()/length() functions in the string class.  All repetition must be accomplished using recursion. This applies to every

operation in the program, even file operations. Obviously, you would never write a

program like this in industry but as an exercise it should be useful to gain experience with recursion.

Sample Runs

Here are two examples of how the program might work:

Please enter a string for an anagram: rat

Matching word art

Matching word rat

Matching word tar

Please enter a string for an anagram:  regardless

No matches found

Requirements

You must write these three functions with the exact same function signature (include case):

int vocabularyCreator(istream &dictfile, string dict[]);

Puts each string in dictfile into the array dict. Returns the number of words read into dict. This number should not be larger than MAXDICTWORDS since that is  the size of the array.

int potentialSequences(string word, const string dict[], int size, string results[]);

Puts all the possibilities of word which are found in dict into results. Returns the number of matched words found. This number should not be larger than

MAXRESULTS since that is the size of the array. The size is the number of words inside the dict array.

void outcomeDisclosure(const string results[], int size);

Displays size number of strings from results. The results can be printed in any order.

For words with double letters, you may find that different permutations match the same word in the dictionary. For example, if you find all the permutations of the string kloo

using the algorithm we've discussed you may find that the word look is found twice. The  o's in kloo take turns in front. Your program should ensure that matches are unique, in    other words, the results array returned from the potentialSequences function should have no duplicates. A nice way to test this, and your function in general, might be to use the assert facility from the standard library. If done properly the following code should

run without a runtime error being generated.

string exampleDict[] = {"kool", "moe", "dee"};

int numResults = potentialSequences("kloo", exampleDict, 3, results);

assert(numResults == 1 && results[0] == "kool");

Again, your solution must not use the keywords while, for, or goto or any STL

algorithm functions. You must not use global variables or variables declared with the

keyword static, and you must not modify the function parameter lists.  You must use the integer constants MAXRESULTS and MAXDICTWORDS, as the declared sizes of your arrays, as in the anagrams.cpp example provided to you.

Helpful Tips

In this project you will also have to deal with one of the drawbacks of using recursive

functions. Repeated recursive calls may exhaust the stack space (we will talk about

stacks soon) that's been allocated for your program. If you use the sample dictionary file provided, you are almost guaranteed to have a default stack size that is not large

enough. Here is how to change the stack size on different platforms:

Visual Studio

In the Property Pages dialog, in the left panel, select Configuration Properties / Linker / System. In the right panel, select Stack Reserve Size, and in the drop-down list to its

right, type in a new stack size (8000000 is approximately 8MB). Click OK.

Xcode

Click on the Project Name, Select Build Settings at the top then scroll below to find the Linker subsection. Add -Wl,-stack_size,8000000 to the Other Linker Flags field.

Linux

Run the command ulimit -s 8000 before compiling your program.

While completing this assignment you may find it helpful to review file operations and using the substr function.

The source file you turn in will contain all the functions and a main routine. You can

have the main routine do whatever you want, because we will rename it to something

harmless, never call it, and append our own main routine to your file. Our main routine will thoroughly test your functions. You'll probably want your main routine to do the

same. If you wish, you may write functions in addition to those required here. We will     not directly call any such additional functions.  The only thing to make sure is that it has the line “return 0;” at within the body of main at the very minimum.

Turn It In

You will use BruinLearn to turn in this project. Turn in one zip file that contains your solution to the project. The zip file itself must be named in the following format (no spaces):  LastNameFirstName_SID_AssignmentTypeAssignmentNumber.zip

(AssignmentType:  P=project, H=homework; AssignmentNumber = {1,2,3,4}).  An example is BruinJoe_123456789_P3.

The zip file that you will turn in for this assignment must contain these two files:

.    A file named anagrams.cpp that contains the source code for your C++

program. Your source code should have helpful comments that tell the purpose of the major program segments and explain any tricky code.

.    A file named report.doc or report.docx (in Microsoft Word format), report.txt (an ordinary text file), or  report.pdf that contains of: