Assignment 4 Real Deal: Crier On Us
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 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). 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
CS 20A – Spring 2019 E. Ambrosio
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[] = {"kool", "moe", "dee"};
int numResults = recurCombos("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 (12000000 is approximately 12MB). 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,12000000 to the Other Linker Flags field.
CS 20A – Spring 2019 E. Ambrosio
Linux
Run the command ulimit -s 12000 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.
Turn It In
You will turn in a zip file electronically via Canvas. What you will turn in for this assignment is a zip file containing 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) or report.txt (an ordinary text file) that contains of:
o A brief description of notable obstacles you overcame.
o A list of the test data that could be used to thoroughly test
your program,
along with the reason for each test. You do not have to include the results of the tests, but you must note which test cases your program does not handle correctly.
Remember that most computing tasks take longer than expected. Start this assignment now!
Sample Main.cpp
#include <iostream>
#include <fstream>
#include <istream>
#include <string>
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);
}
#include <iostream>
#include <fstream>
#include <istream>
#include <string>
using namespace std;
const int MAXRESULTS = 20; // Max matches that can be found
const int MAXDICTWORDS = 30000; // Max words that can be read in
// Function to check and print whether two parameter strings are anagram or not
bool checkAnagram(string first, string second)
{
int match = 0, tempFirst[26] = {0}, tempSecond[26] = {0};
// Checks if first string and second string length is same
if(first.length() == second.length())
{
// Loops till end of the first string and stores it in ASCII value position
for(int index = 0; first[index] != '\0'; index++)
tempFirst[tolower(first[index]) - 'a']++;
// Loops till end of the second string and stores it in ASCII value position
for(int index = 0; second[index] != '\0'; index++)
tempSecond[tolower(second[index]) - 'a']++;
// Loops 26 times
for (int index = 0; index < 26; index++)
{
// Checks if the current index position of each string is not match
if (tempFirst[index] != tempSecond[index])
// Sets the match status to 1
match = 1;
}// End of for loop
// Checks if match value is one then not anagram return false
if (match == 1)
return false;
// Otherwise match value is zero then anagram return true
else
return true;
}// End of if condition
// Otherwise length of both the string are not equal not anagram return false
else
return false;
}// End of function
// Recursive function to store anagram words in result array of string
// Returns number of matches
int recurCombos(string word, string dict[], int nwords, string results[])
{
// Static counter for number of matches
static int counter = 0;
// Checks if number of words is less than zero then return counter value
if(nwords < 0)
return counter;
// Call the function to check word and nwords index position string are anagram or not
// If the function returns true then assign the word to result
// Increase the counter by one1
if(checkAnagram(word, dict[nwords]))
{
results[counter] = dict[nwords];
counter++;
}// End of if condition
// Recursively calls the function by decreasing nwords by one
return recurCombos(word, dict, --nwords, results);
}// End of function
// Function to read the file contents and stores the string in dict string array
// Returns number of records read
int dictionaryReader(ifstream &dictfile, string dict[])
{
// Record counter
int counter = 0;
// Loops till end of the file
while(!dictfile.eof())
// Reads a word and stores it at counter index position
// Increase the counter by one
dictfile>>dict[counter++];
// Returns the counter
return counter;
}// End of function
// Recursive function to displays the result string array contents
void recursiveDisp(string results[], int numMatches)
{
// Checks if number of words counter numMatches is less than zero then stop
if(numMatches < 0)
return;
// Displays the match
cout<<"\n Matching word: "<<results[numMatches];
// Recursively calls the function by decreasing numMatches value by one
recursiveDisp(results, --numMatches);
}// End of function
// main function definition
int main()
{
// String array to store matches
string results[MAXRESULTS];
// Srring array to store dictionary words
string dict[MAXDICTWORDS];
ifstream dictfile; // file containing the list of words
int nwords; // number of words read from dictionary
string word;
// Opens the file for reading
dictfile.open("words.txt");
// Checks if file is unable to open then display error message and stop
if (!dictfile)
{
cout << "File not found!" << endl;
return (1);
}// End of if condition
// Calls the function to read the file contents and stores the word in dict string array
// Stores the return value as number of records
nwords = dictionaryReader(dictfile, dict);
// Accepts a word
cout << "\n Please enter a string for an anagram: ";
cin >> word;
// Calls the function to check anagram word from dictionary and stores the match
// in string array result
// Stores the return value as number of matches
int numMatches = recurCombos(word, dict, nwords-1, results);
// Checks if number of matches is 0 then display error message
if (!numMatches)
cout << "\nNo matches found" << endl;
// Otherwise match found.
else
// Calls the function to display the matches
recursiveDisp(results, numMatches-1);
}// End of main function
Sample Output:
Please enter a string for an anagram: pot
Matching word: opt
Matching word: pot
Matching word: top
words.txt file contents
opt
pot
top
kool
look
Assignment 4 Real Deal: Crier On Us Some word games, like Scrabble, require rearranging a combination of letters to make...
In C++ Please!!!!! Example main: #include <iostream> #include <fstream> #include <istream> #include <cstring> 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...
Assignment 1 In this assignment you will be writing a tool to help you play the word puzzle game AlphaBear. In the game, certain letters must be used at each round or else they will turn into rocks! Therefore, we want to create a tool that you can provide with a list of letters you MUST use and a list of available letters and the program returns a list of all the words that contain required letters and only contain...
may i ask for help with this c++ problem? this is the code i have for assignment 4 question 2: #include<iostream> #include<string> #include<sstream> #include<stack> using namespace std; int main() { string inputStr; stack <int> numberStack; cout<<"Enter your expression::"; getline(cin,inputStr); int len=inputStr.length(); stringstream inputStream(inputStr); string word; int val,num1,num2; while (inputStream >> word) { //cout << word << endl; if(word[0] != '+'&& word[0] != '-' && word[0] != '*') { val=stoi(word); numberStack.push(val); // cout<<"Val:"<<val<<endl; } else if(word[0]=='+') { num1=numberStack.top(); numberStack.pop(); num2=numberStack.top(); numberStack.pop();...
Question 2: Finding the best Scrabble word with Recursion using java Scrabble is a game in which players construct words from random letters, building on words already played. Each letter has an associated point value and the aim is to collect more points than your opponent. Please see https: //en.wikipedia.org/wiki/Scrabble for an overview if you are unfamiliar with the game. You will write a program that allows a user to enter 7 letters (representing the letter tiles they hold), plus...
You will be reading in 3 files in the program. One will contain a list of 1000 words in unsorted order. The second file will contain 1000 words in sorted order. The final file will contain 20 words to be searched for. The main program has been written for you. You will be implementing three functions: bool readWords(string array[], int size, string fileName); int linearSearch(string wordToFind, const string words[], int size); int binarySearch(string wordToFind, const string words[], int size); The...
Vliestion (1) while make testman I will generate an executable called Testman IX to test your program for Question (2). If you just issue make, then both will be generated. (1) In this question, you will re-implement the question in Assignment 1 by using vectors instead dynamic arrays. All the functionalities are the same. Of course, you need to make appropriate changes to the function declarations by using vectors instead of pointers to strings or string arrays). See below. Also...
This lab will combine reading data from a file and searching the array to find a specific value. Assignment Write a program that reads in a file full of strings into an array, and prompts the user for a string to find in the array. The program should loop until a sentinel value (such as -1) is entered. After looping in main() for the input, write a search function, with the following prototype: int findWord(string [], int, string); with arguments...
C++ assignment help! The instructions are below, i included the main driver, i just need help with calling the functions in the main function This assignment will access your skills using C++ strings and dynamic arrays. After completing this assignment you will be able to do the following: (1) allocate memory dynamically, (2) implement a default constructor, (3) insert and remove an item from an unsorted dynamic array of strings, (4) use the string class member functions, (5) implement a...
Goal: Unscramble permuted words by generating all permutations of Jumble string and searching for a word in Unix dictionary. Unix Dictionary: dict.txt Details: Write a method called get_permutations that inputs a string like "dog". Your method should return an array of all permutations of the Jumble string. . For example: s = "dog" perms = get_permutations(a) print(perms) Output: ['dog', 'dgo', 'odg', 'ogd', 'gdo', 'god'] Rewrite the script for obtaining permutations and the end of the Comments, Hints, and Observersions section...
Data Structures and Algorithm Analysis – Cop 3530 Module 3 – Programming Assignment This assignment will access your skills using C++ strings and dynamic arrays. After completing this assignment you will be able to do the following: (1) allocate memory dynamically, (2) implement a default constructor, (3) insert and remove an item from an unsorted dynamic array of strings, (4) use the string class member functions, (5) implement a copy constructor, (6) overload the assignment operator, (7) overload the insertion...