I need help writing a recursive c++ program: Some word games like Scrabble, requ
ID: 3919033 • Letter: I
Question
I need help writing a recursive c++ program: Some word games like Scrabble, require rearranging a combination of letters to make a
word. This type of arrangement is generally referred to as an anagram, 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 anagram.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). 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: opt
Matching word opt
Matching word pot
Matching word top
Please enter a string for an anagram: blah
No matches found
Requirements
You must write these three functions with the exact same function signature (include
case):
int dictionaryReader(istream &dictfile, string dict[]);
Places 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 recurCombos(string word, const string dict[], int size,
string results[]);
Places all the combinations 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 recursiveDisp(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 recurCombos 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[] = {"foster", "the", "people"};
int numResults = recurCombos("softer", exampleDict, 3,
results);
assert(numResults == 1 && results[0] == "foster");
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 anagram.cpp example provided to you.
#include
#include
#include
#include
using namespace std;
const int MAXRESULTS = 20; // Max matches that can be found
const int MAXDICTWORDS = 30000; // Max words that can be read in
int main()
{
string results[MAXRESULTS];
string dict[MAXDICTWORDS];
ifstream dictfile; // file containing the list of words
int nwords; // number of words read from dictionary
string word;
dictfile.open("words.txt");
if (!dictfile) {
cout << "File not found!" << endl;
return (1);
}
nwords = dictionaryReader(dictfile, dict);
cout << "Please enter a string for an anagram: ";
cin >> word;
int numMatches = recurCombos(word, dict, nwords, results);
if (!numMatches)
cout << "No matches found" << endl;
else
recursiveDisp(results, numMatches);
}
Explanation / Answer
SOLUTION:
According to the given data the following code is given:
#include<iostream>
#include<fstream>
#define MAXDICTWORDS 10
#define MAXRESULTS 10
using namespace std;
int readDictionary(ifstream &dictfile, string dict[]);
int recursivePermute(string word, const string dict[], int n, string results[]);
void recurPrint(const string results[], int sz);
int checkAZero(int a[], int n);
int match(const string dictWord, int a[], unsigned int n);
void buildA(int a[], unsigned int n, const string word);
int main(){
ifstream dictfile("words.txt");
string dict[MAXDICTWORDS], word, results[MAXRESULTS];
cout << "Please enter a string for an anagram: ";
cin >> word;
int n = readDictionary(dictfile, dict);
int sz = recursivePermute(word, dict, n, results);
recurPrint(results, sz);
return 0;
}
int readDictionary(ifstream &dictfile, string dict[]){
string data;
if(dictfile.eof())
return 0;
dictfile >> data;
int x = readDictionary(dictfile, dict);
if(x < MAXDICTWORDS){
dict[x] = data;
x++;
return x;
}
else
return MAXDICTWORDS;
}
int recursivePermute(string word, const string dict[], int n, string results[]){
int a[26]={0};
if(n == 0)
return 0;
int sz = recursivePermute(word, dict, n-1, results);
if(sz < MAXRESULTS){
buildA(a, 0, word);
int flag = match(dict[n-1], a, 0);
if(flag == 1){
results[sz]=dict[n-1];
sz++;
}
return sz;
}
else
return MAXRESULTS;
}
void recurPrint(const string results[], int sz){
if(sz-1 < 0)
return;
cout << "Matching word: " << results[sz-1] << endl;
recurPrint(results, sz-1);
}
void buildA(int a[], unsigned int n, const string word){
if(n == word.size())
return;
a[word[n]-'a']++;
buildA(a, n+1, word);
}
int match(const string dictWord, int a[], unsigned int n){
if(n == dictWord.size()){
return checkAZero(a,0);
}
a[dictWord[n]-'a']--;
return match(dictWord, a, n+1);
}
int checkAZero(int a[], int n){
if (n == 26)
return 1;
if(a[n] == 0)
return checkAZero(a, n+1);
else
return 0;
thus by using the above code we can get our required output