So I need help writing a code in C++ using recursion. Some word games, like Scra

Question

So I need help writing a code in C++ using recursion.

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 should be in a similar style.

All repetition must be accomplished using recursion.

Sample Runs

Here are two examples of how the program might work:

Requirements

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

int readDictionary(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 recursivePermute(string word, const string dict[], int size, string results[]);

Places all the permutations 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 recurPrint(const string results[], int size);

Prints 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 recursivePermute 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.

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.

Basically, the dictionary we are using is a word file called words.txt and it holds 30,000 words in it, so MAXDICTWORDS = 30000 and MAXRESULTS = the max number of words that can be formed, aka 20.

Explanation / Answer

#include <iostream>
#include <fstream>
#include <istream>
#include <cstring>
#include <string>

#include <assert.h>

#include <chrono>

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 readDictionary(istream &dictfile, string dict[]);

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

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

// Auxiliary functions

void recursive_readDict(istream &dictfile, string dict[], int& words_count);

void findPermutations(string prefix, string rest, const string dict[], const int& size, string results[], int& count);

void permutation_loop(int i, int max, string prefix, string rest, const string dict[], const int& size, string results[], int& count);

int checkDict(const string& target, const string dict[], int size, string results[], int& count);

bool isDuplicated(const string& target, const string results[], int start, int max);

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 = readDictionary(dictfile, dict);
  
//    string exampleDict[] = {"kool", "moe", "dee"};
//    int numResults = recursivePermute("look", exampleDict, 3, results);
//    assert(numResults == 1 && results[0] == "kool");

    cout << "Please enter a string for an anagram: ";
    cin >> word;
  
    chrono::steady_clock::time_point begin = chrono::steady_clock::now();
  
    int numMatches = recursivePermute(word, dict, nwords, results);
    if (!numMatches)
        cout << "No matches found" << endl;
    else
        recurPrint(results, numMatches);
  
    dictfile.close();
  
    chrono::steady_clock::time_point end = chrono::steady_clock::now();
  
    cout << "Time difference (sec) = " << (chrono::duration_cast<chrono::microseconds>(end - begin).count()) /1000000.0 << endl;
}

int readDictionary(istream &dictfile, string dict[])
{
    int words_count = 0;
  
    recursive_readDict(dictfile, dict, words_count);
  
    return words_count;
}

int recursivePermute(string word, const string dict[], int size, string results[])
{
    int count = 0;
  
    findPermutations("", word, dict, size, results, count);
  
    return count;
}

// It prints all the elements in results into console.
void recurPrint(const string results[], int size)
{
    if(size == 0)
        return;
    else
    {
        cout << "Matching word " << *results << endl;
        recurPrint(results + 1, size - 1);
    }
}

// This function takes one more parameter to count the number of words.
// It reads the file and add each word into an array called dict[].
void recursive_readDict(istream &dictfile, string dict[], int& words_count)
{
    string line;
  
    if(dictfile >> line)
    {
        words_count++;
      
        // if the number of words exceeds MAXDICTWORDS, stop reading the file.
       if (words_count > MAXDICTWORDS)
       {
           // reset the value to previous one.
           words_count--;
           return;
       }
          
        *dict = line;

        recursive_readDict(dictfile, dict + 1, words_count);
    }
}

// findPermutations and permutation_loop ensure that I can find all the permutations of a word.
// I pass the variable count by reference so that wherever I go, the count will still be incremented.

// Making size to be const and passed by reference because I do not need to change the value of size
// within these two functions, and it will help me save some stack spaces.
void findPermutations(string prefix, string rest, const string dict[], const int& size, string results[], int& count)
{
    if (rest.length() == 0)
    {
        // when I find one possible permutation, call checkDict().
        // It would return 1 if this word is found in the dictionary, return 0 if not found.
        count += checkDict(prefix, dict, size, results, count);
        // if the number of words found in the dictionary is greater than MAXRESULTS,
        // stop adding anything into results[].
       if (count > MAXRESULTS)
       {
           // reset the value to previous one.
           count--;
           return;
       }
    }
    else
        permutation_loop(0, static_cast<int>(rest.length()), prefix, rest, dict, size, results, count);
}

// It acts as a for loop.
void permutation_loop(int i, int max, string prefix, string rest, const string dict[], const int& size, string results[], int& count)
{
    if(i >= max)
        return;
  
    findPermutations(prefix + rest[i], rest.substr(0, i) + rest.substr(i + 1), dict, size, results, count);
  
    permutation_loop(i + 1, max, prefix, rest, dict, size, results, count);
}

// since we do not change the value of target, mark target const and passed by reference.
// It checks whether the target word is in the dictionary.
int checkDict(const string& target, const string dict[], int size, string results[], int& count)
{
    // if we run through the whole dictionary, and there is no match, return 0.
    if(size == 0)
        return 0;
  
    // if we find a match in the dictionary, call isDuplicated() to check
    // whether there is already a duplicated one in the result[].
    if(target == *dict)
    {
        // if we do find one duplicated word, simply return 0 to end.
        if(isDuplicated(target, results, 0, count))
           return 0;
        // if there isn't one, add target into result[] and return 1.
        else
        {
            results[count] = target;
            return 1;
        }
    }
    // keep looping through if we haven't found a match.
    else
        return checkDict(target, dict + 1, size - 1, results, count);
}

// this function is to check if there is one word in results[] that is identical to target.
// since no need to change the value of target and results[], mark them const.
bool isDuplicated(const string& target, const string results[], int start, int max)
{
    if(start >= max)
        return false;
  
    if(target == *results)
        return true;
    else
        return isDuplicated(target, results + 1, start + 1, max);
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.