Road Trip

• The idea:

  • Preform a preprocessing step that reads all the words from a dictionary, sorts it into a hash table that maps all anagrams that map to their words.

  • {anagram} -> {vector of words that match anagram}

  • Next, read the license-plates.

    • Sort the word in the plate, and map it to the anagram dictionary word. If the word does not appear, continuously add a new alpha character until a word is found in the dictionary.

class wordAnagrams {
public:
    wordAnagrams(string filepath) {
        ifstream infile;
        infile.open(filepath);

        if (!infile.good()) {
            cout << "ERROR:\nBad filename.\n";
        }

        string sorted, unsorted;
        while (infile >> sorted) {
            unsorted = sorted;
            sort(sorted.begin(), sorted.end());

            // find the word
            if (anagrams.find(sorted) == anagrams.end()) {
                // not found
                vector<string> newVec;
                newVec.push_back(unsorted);
                anagrams.insert({ { sorted },{ newVec } });
            }
            // found
            else {
                anagrams.find(sorted)->second.push_back(unsorted);
            }
        }
    }

    vector<string> find(string word) {
        sort(word.begin(), word.end());
        if (anagrams.find(word) == anagrams.end()) {
            vector<string> empty;
            return empty;
        }
        return anagrams.find(word)->second;
    }

    string find_first(string word) {
        sort(word.begin(), word.end());
        if (anagrams.find(word) == anagrams.end()) {
            string empty = "";
            return empty;
        }
        return anagrams.find(word)->second.at(0);
    }

private:
    unordered_map<string, vector<string>> anagrams;
};


string get_next_word(string word, char current_add, wordAnagrams &anag) {
    string new_word = word + current_add;
    sort(new_word.begin(), new_word.end());
    return anag.find_first(new_word);
}

// removing digits from string
string extract_string(string str) {
    for (int i = 0; i < str.length(); i++) {
        if (isdigit(str.at(i)) || str.at(i) == ' ') {
            str.erase(i, 1);
            --i;
        }
        else str.at(i) = tolower(str.at(i));
    }

    return str;
}

vector<string> shortest_lic_word(string lic_filepath) {
    vector<char> alpha = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 
                          'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
    int cur_alpha = 0;
    int global_add = 0;

    string dict_filepath = "C:/Users/Gamer/Desktop/c++ daily/words.txt";
    wordAnagrams anagrams(dict_filepath);

    ifstream infile_lic;
    vector<string> shrt_words;
    infile_lic.open(lic_filepath);

    if (!infile_lic.good()) {
        cout << "ERROR:\nBad filename.\n";
    }
    string license;
    while (getline(infile_lic, license)) {
        // sort word
        license = extract_string(license);
        string shortest = anagrams.find_first(license);
        while (shortest.empty()) {
            shortest = get_next_word(license, alpha[cur_alpha++ % 26], anagrams);
            double current_add = double(cur_alpha) / 26;
            if (current_add == int(current_add)) {
                license += alpha[(cur_alpha + global_add) % 26];
                ++global_add;
                sort(license.begin(), license.end());
            }
        }
        shrt_words.push_back(shortest);
    }
    return shrt_words;
}


int main(int argc, char **argv) {
    //string dict_filepath = "C:/Users/Gamer/Desktop/c++ daily/words.txt";
    //wordAnagrams anagrams(dict_filepath);

    ///* ANAGRAM TEST */
    //string word = "cat";
    //vector<string> test = anagrams.find(word);
    //for (auto i : test) cout << i << " ";
    //cout << endl;
    //pause();

    string lic_filepath = "C:/Users/Gamer/Desktop/c++ daily/licenses.txt";
    vector<string> lic_words = shortest_lic_word(lic_filepath);
    print(lic_words);

}