Skip to content

Instantly share code, notes, and snippets.

@ziyadm
Created January 13, 2016 04:56
Show Gist options
  • Save ziyadm/406d6747e0e7a26ad829 to your computer and use it in GitHub Desktop.
Save ziyadm/406d6747e0e7a26ad829 to your computer and use it in GitHub Desktop.
stupid python thing but in c++ this time
#include <iostream>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <vector>
#include <fstream>
#include <ctime>
#include <tuple>
#include <chrono>
#include <functional>
using namespace std;
vector <string> lines_in_file(string path_to_file) {
vector<string> result;
ifstream file(path_to_file);
string line;
while(getline(file, line)) result.push_back(line);
return result;
}
bool compare_length(std::string const& lhs, std::string const& rhs) {
return lhs.size() < rhs.size();
}
set <string> find_matching_words_indexed(map < tuple<char, int, int>, set <string> >& words, string& format) {
tuple <char, int, int> first_key = make_tuple(char(format[0]), 0, format.size());
set <string> partial_words = words[first_key];
for(int i = 1; i < format.size(); i++) {
set <string> buffer;
set <string> temp = words[make_tuple(char(format[i]), i, format.size())];
set_intersection(partial_words.begin(), partial_words.end(),
temp.begin(), temp.end(),
inserter(buffer, buffer.end()));
partial_words = buffer;
}
return partial_words;
}
map < tuple<char, int, int>, set <string> > preprocess_words(vector <string>& words, string& format) {
map < tuple<char, int, int>, set <string> > preprocessed_words;
for(int i = 0; i < words.size(); i++) {
if(format.size() != words[i].size()) continue;
for(int j = 0; j < words[i].size(); j++) {
preprocessed_words[make_tuple(char(words[i][j]), j, words[i].size())].insert(words[i]);
preprocessed_words[make_tuple('.', j, words[i].size())].insert(words[i]);
}
}
return preprocessed_words;
}
int main() {
string path = "/usr/share/dict/words";
vector<string> words = lines_in_file(path);
string format = ".is..d";
// preprocess the bs
map< tuple<char, int, int>, set <string> > preprocessed = preprocess_words(words, format);
// start time
std::chrono::time_point<std::chrono::system_clock> start, end;
start = std::chrono::system_clock::now();
// make the call
set <string> matching_words_indexed = find_matching_words_indexed(preprocessed, format);
// end the time
end = std::chrono::system_clock::now();
std::chrono::duration<double> elapsed_seconds = end-start;
std::time_t end_time = std::chrono::system_clock::to_time_t(end);
std::cout << "finished computation at " << std::ctime(&end_time)
<< "elapsed time: " << elapsed_seconds.count() << "s\n";
cout << "indexed" << endl;
set <string>::iterator zit = matching_words_indexed.begin();
while(zit != matching_words_indexed.end()) {
cout << *zit << endl;
zit++;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment