/// \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