Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- The MIT License (MIT)
- Copyright (c) 2013 Krishna Bharadwaj <krishna@krishnabharadwaj.info>
- Permission is hereby granted, free of charge, to any person obtaining a copy
- of this software and associated documentation files (the "Software"), to deal
- in the Software without restriction, including without limitation the rights
- to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
- copies of the Software, and to permit persons to whom the Software is
- furnished to do so, subject to the following conditions:
- The above copyright notice and this permission notice shall be included in
- all copies or substantial portions of the Software.
- THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
- IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
- FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
- AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
- LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
- OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
- THE SOFTWARE.
- */
- #include <iostream>
- #include <fstream>
- #include <map>
- #include <vector>
- #include <string>
- using namespace std;
- vector <string> words;
- bool match(string path, string word){
- int pl = path.length(), wl = word.length(), j = 0;
- for(int i = 0; i < pl; i++){
- if(path[i] == word[j])
- j++;
- }
- if(j < wl)
- return false;
- return true;
- }
- int get_keyboard_row(char c){
- const char* args[] = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
- vector <string> keyboard(args, args + 3);
- for(int i = 0; i < keyboard.size(); i++){
- int n = keyboard[i].length();
- for(int j = 0; j < n; j++){
- if(keyboard[i][j] == c)
- return i;
- }
- }
- }
- vector <int> compress(vector <int> s){
- int i = 0, j = 0, n = s.size();
- while(i < n){
- if(s[i] != s[j])
- s[++j] = s[i];
- i++;
- }
- return vector <int>(s.begin(), s.begin() + j + 1);
- }
- int get_minimum_wordlength(string path){
- int n = path.length();
- vector <int> row_numbers(n);
- for(int i = 0; i < n; i++){
- row_numbers[i] = get_keyboard_row(path[i]);
- }
- int min_length = (compress(row_numbers)).size() - 3;
- if(min_length < 0)
- min_length = 0;
- return min_length;
- }
- vector<string> get_suggestions(string path){
- vector <string> suggestions_v1, suggestions_v2, suggestions_v3;
- int n = words.size(), pathlen = path.length();
- for(int i = 0; i < n; i++){
- int len = words[i].length();
- if(path[0] == words[i][0] && path[pathlen-1] == words[i][len-1]){
- suggestions_v1.push_back(words[i]);
- }
- }
- n = suggestions_v1.size();
- for(int i = 0; i < n ; i++){
- if(match(path, suggestions_v1[i])){
- suggestions_v2.push_back(suggestions_v1[i]);
- }
- }
- int min_length = get_minimum_wordlength(path);
- n = suggestions_v2.size();
- for(int i = 0; i < n; i++)
- if(suggestions_v2[i].length() > min_length)
- suggestions_v3.push_back(suggestions_v2[i]);
- return suggestions_v3;
- }
- void readfile(){
- words.clear();
- ifstream wordlist_file("wordlist.txt");
- string word;
- while(wordlist_file >> word)
- words.push_back(word);
- wordlist_file.close();
- }
- int main(){
- const char* args[] = {
- "heqerqllo", // hello
- "qwertyuihgfcvbnjk", // quick
- "wertyuioiuytrtghjklkjhgfd", // world
- "dfghjioijhgvcftyuioiuytr", // doctor
- "aserfcvghjiuytedcftyuytre", // architecture
- "asdfgrtyuijhvcvghuiklkjuytyuytre", // agriculture
- "mjuytfdsdftyuiuhgvc", // music
- "vghjioiuhgvcxsasdvbhuiklkjhgfdsaserty", // vocabulary
- };
- vector<std::string> paths(args, args + 8);
- readfile();
- for(int i = 0; i < paths.size(); i++){
- vector <string> suggestions = get_suggestions(paths[i]);
- cout << "[";
- for(int j = 0; j < suggestions.size(); j++){
- cout << "'" << suggestions[j] << "'";
- if(j != suggestions.size() - 1)
- cout << ", ";
- }
- cout << "]" << endl;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment