scrabble solver unsorted_map | C++

ThiccDaddyLOAF

March 5th, 2021 03:52:22 AM

					
/// \file main.cpp /// \brief This is the main code file. /// \mainpage Hash Table Speed Demo /// /// This program demonstrates the speed advantage of a hash table versus a /// plain table using binary search in a Scrabble cheat program. It /// prompts the user to enter a string of letters, then outputs a list of /// words that can be made with those letters using a dictionary of words /// read from a file. Actually, it does it twice, once using a straight table /// and binary search for the dictionary, the other using an open hash table, /// reporting CPU time for each. This code uses functors in order to avoid /// code duplication. #include <string> #include <vector> #include <unordered_map> #include <fstream> #include <iostream> #include <algorithm> #include <time.h> /// Get CPU time in milliseconds. /// \return User CPU time in milliseconds. unsigned CPUTime(){ return unsigned((1000.f*(float)clock())/(float)CLOCKS_PER_SEC); } //CPUTime /// \brief Sort a string void sort(std::string& str){ std::sort(str.begin(), str.end()); } std::unordered_map<std::string, std::vector<std::string>> wordList; //Still a hash map /// Read the dictionary from `words.txt` into both a plain word table and a /// hash table implementation of a dictionary. /// \param wt0 Plain word table. /// \param wt1 Word hash table. /// \return true if successful. bool GetDictionary(){ //Edit with my own implementation std::cerr << "Loading dictionary..." << std::endl; bool bLoaded = false; std::ifstream input; input.open("words.txt"); size_t numberOfWords = 0; size_t maxLength = 0; size_t minLength = 999999; if(input.is_open()){ //success std::string s; //current line of text while(std::getline(input, s)){ //get and process line of text ++numberOfWords; std::string sorted = s; sort(sorted); //Sorts the characters size_t length = s.size(); if(length > maxLength) maxLength = length; if(length < minLength) minLength = length; if(wordList.find(sorted) == wordList.end()) wordList[sorted] = std::vector<std::string>(); wordList[sorted].push_back(s); } //while input.close(); bLoaded = true; } //if //print output statistics if(bLoaded){ std::cerr << numberOfWords << " words loaded. "; std::cerr << "Shortest word length " << minLength << ". "; std::cerr << "Longest word length " << maxLength << ". " << std::endl; } //if else std::cerr << "Dictionary file (words.txt) not found" << std::endl; return bLoaded; } //GetDictionary /// Read a string of letters from the current line of stdin. All upper-case /// letters are made lower-case. All non-letter characters are ignored. /// \param s [out] input string. void GetInput(std::string& s){ std::string temp; //temporary string for unprocessed input, may contain bad chars std::cout << "> "; //prompt std::getline(std::cin, temp); std::transform(temp.begin(), temp.end(), temp.begin(), ::tolower); //make lower case //put only alphabetic characters into s s.clear(); for(char c: temp) if('a' <= c && c <= 'z') s += c; } //GetInput ///https://stackoverflow.com/a/36184405/10141528 A lot of other good ways to do this, but this one is the cleanest /// \brief Makes a power set /// Makes a list of all of the possible subsets, aka combinations of elements //template<typename T> //std::vector<std::vector<T>> makePowerSet(const T* begin, const T* end){ //Really messy, but gets the job done // std::vector<std::vector<T>> powerSet; // for(const T* it = begin; it != end; ++it){ // for(std::vector<T> bruh : powerSet){ // //std::vector<T> bruh = set; // bruh.push_back(*it); //I'm really hoping bruh does not modify the internal data // powerSet.push_back(bruh); // } // powerSet.push_back(std::vector<T>(*it)); // } // return powerSet; //} //Same thing but for a string std::vector<std::string> makePowerSet(const std::string& str){ //Really messy, but gets the job done std::vector<std::string> powerSet; for(std::string::const_iterator it = str.cbegin(); it != str.cend(); ++it){ size_t lastSize = powerSet.size(); for(size_t i = 0; i < lastSize; i++){ std::string bruh = powerSet[i]; bruh += (*it); //I'm really hoping bruh does not modify the internal data powerSet.push_back(bruh); } powerSet.push_back(std::string()+*it); //Hopefully this explicit cast works and this static variable gets copied to the vector } return powerSet; } void print_map(std::unordered_map<std::string,std::vector<std::string>> const &m) { for (auto const& pair: m) { std::cout << "{" << pair.first << ": "; for(auto const& elm : pair.second){ std::cout << elm << " ,"; } std::cout << "}\n"; } } /// Main. Prompt user to enter a string of letters, then output a list of /// words that can be made with those letters using a dictionary of words /// read from a file. Actually, we do it twice, once using a straight table /// and binary search for the dictionary, the other using an open hash table /// so that we can compare the running time for each. /// \return 0. int main(){ std::cerr << "Scrabble cheater by Ian Parberry" << std::endl; std::cerr << "edited by Leif Messinger" << std::endl; if(GetDictionary()){ //print_map(wordList); std::cerr << "Enter a string of alphabetic characters."; std::cerr << " Hit Return to exit." << std::endl; std::string strInput; //input string std::string strWord; //current word. do{ //get the input strInput.clear(); GetInput(strInput); //process the input if(!strInput.empty()){ //do nothing for empty string std::cout << "Results using my implementation." << std::endl; size_t matches = 0; unsigned checkpoint = CPUTime(); //Pre sort time sort(strInput); //If you sort the string before you make the powerSet, then the powerSet will hold sorted strings. Neat. unsigned checkpoint2 = CPUTime(); //Post sort time std::vector<std::string> powerSet = makePowerSet(strInput); unsigned checkpoint3 = CPUTime(); //Map effectiveness for(std::vector<std::string>::iterator it = powerSet.begin(); it != powerSet.end(); ++it){ //std::cout << bruh << std::endl; if(wordList.find(*it) != wordList.end()){ //I'll probably learn how to store that so I don't have to check the map twice //if(wordList[bruh] != std::vector<std::string>()){ for(std::string word : wordList[*it]){ ++matches; std::cout << word << " "; std::cout.flush(); } } } unsigned endTime = CPUTime(); std::cout << std::endl << matches << " words found in " << (endTime-checkpoint) << " miliseconds." << std::endl; std::cout << (endTime-checkpoint3) << " ms just to look through the map." << std::endl; } //if }while(!strInput.empty()); //exit on empty string } //if return 0; } //main

Featured Posts