Wordle Solver (C++ optimized)

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <chrono>
#include <cstdint>

using namespace std;
using namespace std::chrono;

// From https://www-cs-faculty.stanford.edu/~knuth/sgb-words.txt
// const char* ANSWER_WORD_FILE = "sgb-words.txt";
// const char* GUESS_WORD_FILE = "sgb-words.txt";
// From https://boardgames.stackexchange.com/a/38386/3054
// const char* ANSWER_WORD_FILE = "Collins Scrabble Words (2019).txt";
// const char* GUESS_WORD_FILE = "Collins Scrabble Words (2019).txt";
// From http://www.mieliestronk.com/corncob_caps.txt
// const char* ANSWER_WORD_FILE = "corncob_caps.txt";
// const char* GUESS_WORD_FILE = "corncob_caps.txt";
// From https://github.com/first20hours/google-10000-english/blob/master/google-10000-english.txt
// const char* ANSWER_WORD_FILE = "google-10000-english.txt";
// const char* GUESS_WORD_FILE = "google-10000-english.txt";
// From https://github.com/dwyl/english-words
// const char* ANSWER_WORD_FILE = "words.txt";
// const char* GUESS_WORD_FILE = "words.txt";
// From https://github.com/Kinkelin/WordleCompetition/blob/main/data/official/combined_wordlist.txt
// const char* ANSWER_WORD_FILE = "combined_wordlist.txt";
const char* GUESS_WORD_FILE = "combined_wordlist.txt";
// From https://github.com/Kinkelin/WordleCompetition/blob/main/data/official/shuffled_real_wordles.txt
const char* ANSWER_WORD_FILE = "shuffled_real_wordles.txt";
// const char* GUESS_WORD_FILE = "shuffled_real_wordles.txt";

int word_length;
vector<char*> guess_words;
vector<char*> answer_words;
char* best_first_guess = NULL;

bool all_alpha(string s) {
    for (unsigned int i = 0; i < s.length(); i++) {
        if (!isalpha(s[i])) {
            return false;
        }
    }
    return true;
}

void toupper_cstr(char* s) {
    while (*s != '\0') {
        *s = toupper(*s);
        s++;
    }
}

vector<char*> read_word_file(const char* filename) {
    vector<char*> result;
    string line;
    ifstream infile(filename);
    int max_length = 0;
    while (getline(infile, line)) {
        if (all_alpha(line)) {
            if (line.length() == word_length) {
                char* word = new char[word_length + 1];
                strcpy(word, line.c_str());
                toupper_cstr(word);
                result.push_back(word);
            }
        }
    }
    return result;
}

// Hints are packed into unsigned integers, one ternary digit per bit, least-significant digit is last character
// This is more space-efficient than using two bits per hint, which is important for cache efficiency.
// typedef uint64_t hint; // Use for number of words >= 21
typedef uint32_t hint; // Use for number of words <= 20
hint num_hint_values; // max hint value plus one

hint get_wordle_hints(const char* guess, const char* answer) {
    hint result = 0;
    char buf[80];
    strcpy(buf, answer);

    for (int i = 0; i < word_length; i++) {
        if (guess[i] == answer[i]) {
            buf[i] = ' ';
        }
    }
    for (int i = 0; i < word_length; i++) {
        result *= 3;
        if (guess[i] == answer[i]) {
            result += 2; // green
        } else {
            char* char_pos = strchr(buf, guess[i]);
            if (char_pos != NULL) {
                result += 1; // yellow
                *char_pos = ' ';
            }
            // Otherwise black which is zero, do nothing
        }
    }
    return result;
}

hint string_to_hint(string hint_str) {
    hint result = 0;
    for (int i = 0; i < hint_str.length(); i++) {
        result *= 3;
        if (hint_str[i] == 'g') {
            result += 2;
        } else if (hint_str[i] == 'y') {
            result += 1;
        }
    }
    return result;
}

string hint_to_string(hint hint) {
    string result;
    for (int i = 0; i < word_length; i++) {
        char c;
        if ((hint % 3) == 2) {
            c = 'g';
        } else if ((hint % 3) == 1) {
            c = 'y';
        } else {
            c = 'k';
        }
        result = c + result;
        hint /= 3;
    }
    return result;
}

struct guess {
    guess(char* word, hint hint) {
        this->word = word;
        this->hint = hint;
    }

    char* word;
    hint hint;
};

bool matches_hints(const char* answer, const vector<guess>& guesses_so_far) {
    for (int i = 0; i < guesses_so_far.size(); i++) {
        if (get_wordle_hints(guesses_so_far[i].word, answer) != guesses_so_far[i].hint) {
            return false;
        }
    }
    return true;
}

vector<char*> get_valid_words(const vector<char*>& answer_words, const vector<guess>& guesses_so_far) {
    vector<char*> result;
    for (int i = 0; i < answer_words.size(); i++) {
        if (matches_hints(answer_words[i], guesses_so_far)) {
            result.push_back(answer_words[i]);
        }
    }
    return result;
}

inline bool should_prefer_dense(int num_words) {
     return (num_hint_values / num_words) < 250;  // Experimentally determined constant
}

bool is_among_guesses(char* word, const vector<guess>& guesses_so_far) {
    for (int i = 0; i < guesses_so_far.size(); i++) {
        if (strcmp(word, guesses_so_far[i].word) == 0) {
            return true;
        }
    }
    return false;
}

map<char*, bool> forbidden_first_guesses;

void forbid_first_guess(char* word) {
    forbidden_first_guesses[word] = true;
    best_first_guess = NULL;
}

int* hint_class_counts = NULL;
char* get_best_guess(const vector<char*>& valid_words, bool& result_is_correct_word, const vector<guess>& guesses_so_far, int& rating) {
    if (valid_words.size() == 0) {
        rating = 0;
        return NULL;
    } else if (valid_words.size() == 1) {
        result_is_correct_word = true;
        rating = 0;
        return valid_words[0];
    }

    map<string, bool> valid_words_map;
    for (int i = 0; i < valid_words.size(); i++) {
        valid_words_map[valid_words[i]] = true;
    }

    char* best_guess = NULL;
    int best_guess_rating = INT_MAX;
    bool best_matches_hints = false;

    if (should_prefer_dense(valid_words.size())) {
        // Dense case - use direct array indexing
        for (int i = 0; i < guess_words.size(); i++) {
            if (guess_words[i][0] == '\0') {
                continue; // Word was removed from dictionary during guessing
            }
            memset(hint_class_counts, 0, sizeof(int) * num_hint_values);
            bool skip_to_next_word = false;
            for (int j = 0; j < valid_words.size(); j++) {
                int idx = get_wordle_hints(guess_words[i], valid_words[j]);
                hint_class_counts[idx]++;
                if (hint_class_counts[idx] > best_guess_rating) {
                    skip_to_next_word = true;
                    break;
                }
            }
            if (skip_to_next_word) {
                continue;
            }

            int guess_rating = 0;
            // Rating for this guess is max of all hint class counts
            for (int j = 0; j < num_hint_values; j++) {
                if (hint_class_counts[j] >= guess_rating) {
                    guess_rating = hint_class_counts[j];
                }
            }
            if (guess_rating < best_guess_rating && !is_among_guesses(guess_words[i], guesses_so_far) && !(guesses_so_far.size() == 0 && forbidden_first_guesses.find(guess_words[i]) != forbidden_first_guesses.end())) {
                best_guess = guess_words[i];
                best_guess_rating = guess_rating;
                best_matches_hints = matches_hints(guess_words[i], guesses_so_far);
            } else if (!best_matches_hints && guess_rating == best_guess_rating && valid_words_map.find(guess_words[i]) != valid_words_map.end() && !is_among_guesses(guess_words[i], guesses_so_far) && !(guesses_so_far.size() == 0 && forbidden_first_guesses.find(guess_words[i]) != forbidden_first_guesses.end())) {
                // Among the best candidates, prioritize those that are valid words satisfying all the hints
                // so far, so that we have a chance to guess the word.
                best_guess = guess_words[i];
                best_guess_rating = guess_rating;
                best_matches_hints = true;
            }
        }
    } else {
        // Sparse case - use map
        map<hint, int> hint_class_counts;
        for (int i = 0; i < guess_words.size(); i++) {
            hint_class_counts.clear();
            bool skip_to_next_word = false;
            for (int j = 0; j < valid_words.size(); j++) {
                int idx = get_wordle_hints(guess_words[i], valid_words[j]);
                hint_class_counts[idx]++;
                if (hint_class_counts[idx] > best_guess_rating) {
                    skip_to_next_word = true;
                    break;
                }
            }
            if (skip_to_next_word) {
                continue;
            }

            int guess_rating = 0;
            // Rating for this guess is max of all hint class counts
            for (auto iter = hint_class_counts.begin(); iter != hint_class_counts.end(); iter++) {
                if (iter->second >= guess_rating) {
                    guess_rating = iter->second;
                }
            }

            if (guess_rating < best_guess_rating && !is_among_guesses(guess_words[i], guesses_so_far) && !(guesses_so_far.size() == 0 && forbidden_first_guesses.find(guess_words[i]) != forbidden_first_guesses.end())) {
                best_guess = guess_words[i];
                best_guess_rating = guess_rating;
                best_matches_hints = matches_hints(guess_words[i], guesses_so_far);
            } else if (!best_matches_hints && guess_rating == best_guess_rating && valid_words_map.find(guess_words[i]) != valid_words_map.end() && !is_among_guesses(guess_words[i], guesses_so_far) && !(guesses_so_far.size() == 0 && forbidden_first_guesses.find(guess_words[i]) != forbidden_first_guesses.end())) {
                // Among the best candidates, prioritize those that are valid words satisfying all the hints
                // so far, so that we have a chance to guess the word.
                best_guess = guess_words[i];
                best_guess_rating = guess_rating;
                best_matches_hints = true;
            }
        }
    }

    result_is_correct_word = false;
    rating = best_guess_rating;
    return best_guess;
}

bool can_guess_word_max_depth(const vector<char*>& valid_words, char* word, const vector<guess>& guesses_so_far, int max_depth) {
    if (valid_words.size() <= 1) {
        return true;
    }
    if (max_depth == 0) {
        return false;
    }

    for (int i = 0; i < guess_words.size(); i++) {
        if (is_among_guesses(guess_words[i], guesses_so_far)) {
            continue;
        }
        vector<guess> guesses_so_far2 = guesses_so_far;
        guesses_so_far2.push_back(guess(guess_words[i], get_wordle_hints(guess_words[i], word)));
        vector<char*> valid_words2 = get_valid_words(valid_words, guesses_so_far2);
        if (valid_words2.size() == valid_words.size()) {
            continue; // No new information
        }

        if (!can_guess_word_max_depth(valid_words2, word, guesses_so_far2, max_depth - 1)) {
            return false;
        }
    }

    return true;
}

void cache_best_first_guess() {
    if (best_first_guess == NULL) {
        vector<guess> guesses_so_far;
        bool result_is_correct_word;
        int rating;
        cout << "Computing and caching best first guess..." << endl;
        auto start = high_resolution_clock::now();
        best_first_guess = get_best_guess(answer_words, result_is_correct_word, guesses_so_far, rating);
        auto stop = high_resolution_clock::now();
        cout << "Done, time: " << duration_cast<microseconds>(stop - start).count() / 1000000.0 << " s" << endl;
        // best_first_guess = _strdup("RAILE");
    }
}

void find_best_first_guess() {
    cache_best_first_guess();
    cout << "Best first guess: " << best_first_guess << endl;
}

void print_words(const vector<char*>& valid_words) {
    cout << "[";
    int limit = valid_words.size() <= 50 ? valid_words.size() : 20;
    for (int i = 0; i < limit; i++) {
        cout << valid_words[i] << (i < valid_words.size() - 1 ? ", " : "");
    }
    if (limit < valid_words.size()) {
        cout << "(" << (valid_words.size() - limit) << " other words" << ")";
    }
    cout << "]";
}

void guess_unknown_word() {
    vector<guess> guesses_so_far;
    bool result_is_correct_word;
    int rating;

    string hint_string;
    char* current_guess;
    do {
        cache_best_first_guess();
        current_guess = best_first_guess;
        cout << "Next guess: " << current_guess << endl;
        cout << "Enter result (k for black, y for yellow, g for green, or ENTER if word is not accepted): ";
        getline(cin, hint_string);
        if (hint_string.length() == 0) {
            strcpy(best_first_guess, ""); // Remove from dictionary
            best_first_guess = NULL;
        }
    } while (hint_string.length() == 0);
    guesses_so_far.push_back(guess(current_guess, string_to_hint(hint_string)));
    vector<char*> valid_words = get_valid_words(answer_words, guesses_so_far);
    print_words(valid_words);
    cout << endl << endl;

    while (true) {
        char* current_guess = get_best_guess(valid_words, result_is_correct_word, guesses_so_far, rating);
        if (current_guess == NULL) {
            cout << "Word is not in dictionary." << endl;
            break;
        } else if (result_is_correct_word) {
            cout << "The word is: " << current_guess << endl;
            break;
        }
        cout << "Next guess: " << current_guess << endl;
        cout << "Enter result (k for black, y for yellow, g for green, or ENTER if word is not accepted): ";
        getline(cin, hint_string);
        if (hint_string.length() == 0) {
            strcpy(current_guess, ""); // Remove from dictionary
            continue;
        }
        guesses_so_far.push_back(guess(current_guess, string_to_hint(hint_string)));
        valid_words = get_valid_words(valid_words, guesses_so_far);
        print_words(valid_words);
        cout << endl << endl;
    }
}

void solve_single_word_helper(char* answer) {
    vector<guess> guesses_so_far;
    bool result_is_correct_word;
    int rating;

    auto start = high_resolution_clock::now();
    cache_best_first_guess();
    char* current_guess = best_first_guess;
    hint hint = get_wordle_hints(current_guess, answer);
    guesses_so_far.push_back(guess(current_guess, hint));
    vector<char*> valid_words = get_valid_words(answer_words, guesses_so_far);
    cout << current_guess << " " << hint_to_string(hint) << " ";
    print_words(valid_words);
    cout << endl << endl;

    while (strcmp(current_guess, answer) != 0) {
        current_guess = get_best_guess(valid_words, result_is_correct_word, guesses_so_far, rating);
        if (current_guess == NULL) {
            cout << "Word is not in dictionary. You may have typed it incorrectly." << endl;
            break;
        }
        hint = get_wordle_hints(current_guess, answer);
        guesses_so_far.push_back(guess(current_guess, hint));
        valid_words = get_valid_words(valid_words, guesses_so_far);
        cout << current_guess << " " << hint_to_string(hint) << " ";
        print_words(valid_words);
        cout << endl << endl;
    }
    auto stop = high_resolution_clock::now();
    cout << "Done, time: " << duration_cast<microseconds>(stop - start).count() / 1000000.0 << " s" << endl;
    cout << "Number of guesses: " << guesses_so_far.size() << endl;
}

void solve_single_word() {
    char* answer = NULL;
    do {
        cout << "Enter solution word: ";
        string answer_str;
        getline(cin, answer_str);
        answer = _strdup(answer_str.c_str());
        toupper_cstr(answer);
        if (strlen(answer) != word_length) {
            cout << "Word is wrong length, must be " << word_length << " letters." << endl;
            continue;
        }
        break;
    } while (true);

    solve_single_word_helper(answer);
}

void solve_all_words_in_dictionary() {
    vector<guess> guesses_so_far;
    bool result_is_correct_word;
    int rating;

    auto overall_start = high_resolution_clock::now();

    double best_average = 10000.0f;
    char* best_first_word_solve_all = NULL;

    while (true) {
        cout << "Precomputing best first guess..." << endl;
        cache_best_first_guess();
        char* first_guess = best_first_guess;
        cout << "First guess: " << first_guess << endl;

        char** second_guesses = NULL;
        if (answer_words.size() * 1000 > num_hint_values) {
            cout << "Precomputing best second guesses..." << endl;
            auto start = high_resolution_clock::now();
            second_guesses = new char* [num_hint_values];
            for (int i = 0; i < num_hint_values; i++) {
                vector<guess> guesses_so_far;
                guesses_so_far.push_back(guess(first_guess, i));
                vector<char*> valid_words = get_valid_words(answer_words, guesses_so_far);
                second_guesses[i] = get_best_guess(valid_words, result_is_correct_word, guesses_so_far, rating);

                // if ((i % 1000) == 0) {
                //     auto stop = high_resolution_clock::now();
                //     cout << "Projected time: " << duration_cast<microseconds>(stop - start).count() / 1000000.0 / i * num_hint_values << " s" << endl;
                // }
            }
            auto stop = high_resolution_clock::now();
            cout << "Done, time: " << duration_cast<microseconds>(stop - start).count() / 1000000.0 << " s" << endl;
        }

        char*** third_guesses = NULL;
        if (sqrt(answer_words.size() * 1000) > num_hint_values) {
            cout << "Precomputing third guesses..." << endl;
            auto start = high_resolution_clock::now();
            third_guesses = new char** [num_hint_values * num_hint_values];
            for (int i = 0; i < num_hint_values; i++) {
                vector<guess> guesses_so_far_first;
                guesses_so_far_first.push_back(guess(first_guess, i));
                vector<char*> valid_words_first = get_valid_words(answer_words, guesses_so_far_first);

                third_guesses[i] = new char* [num_hint_values];
                for (int j = 0; j < num_hint_values; j++) {
                    vector<guess> guesses_so_far;
                    guesses_so_far.push_back(guess(first_guess, i));
                    guesses_so_far.push_back(guess(second_guesses[i], j));
                    vector<char*> valid_words = get_valid_words(valid_words_first, guesses_so_far);
                    third_guesses[i][j] = get_best_guess(valid_words, result_is_correct_word, guesses_so_far, rating);
                }
                // if ((i % 1000) == 0) {
                //     auto stop = high_resolution_clock::now();
                //     cout << "Projected time: " << duration_cast<microseconds>(stop - start).count() / 1000000.0 / i * num_hint_values << " s" << endl;
                // }
            }
            auto stop = high_resolution_clock::now();
            cout << "Done, time: " << duration_cast<microseconds>(stop - start).count() / 1000000.0 << " s" << endl;
        }

        int max_guesses = 0;
        char* worst_word = NULL;

        cout << "Solving all words in dictionary..." << endl;
        auto start = high_resolution_clock::now();
        int histogram[50] = { 0 };
        for (int i = 0; i < answer_words.size(); i++) {
            if ((i % 1000) == 0) {
                cout << i << endl;
                // auto stop = high_resolution_clock::now();
                // cout << "Projected time: " << duration_cast<microseconds>(stop - start).count() / 1000000.0 / i * answer_words.size() << " s" << endl;
            }
            vector<guess> guesses_so_far;
            char* current_guess = first_guess;

            guesses_so_far.push_back(guess(current_guess, get_wordle_hints(current_guess, answer_words[i])));

            int number_of_guesses = 1;
            hint first_hint;
            vector<char*> valid_words;

            if (strcmp(current_guess, answer_words[i]) != 0) {
                first_hint = get_wordle_hints(current_guess, answer_words[i]);
                if (second_guesses != NULL) {
                    current_guess = second_guesses[first_hint];
                } else {
                    current_guess = get_best_guess(answer_words, result_is_correct_word, guesses_so_far, rating);
                }
                number_of_guesses++;
                guesses_so_far.push_back(guess(current_guess, get_wordle_hints(current_guess, answer_words[i])));
                valid_words = get_valid_words(answer_words, guesses_so_far);
            }

            if (third_guesses != NULL && strcmp(current_guess, answer_words[i]) != 0) {
                current_guess = third_guesses[first_hint][get_wordle_hints(current_guess, answer_words[i])];
                number_of_guesses++;
                guesses_so_far.push_back(guess(current_guess, get_wordle_hints(current_guess, answer_words[i])));
                valid_words = get_valid_words(valid_words, guesses_so_far);
            }

            while (strcmp(current_guess, answer_words[i]) != 0) {
                current_guess = get_best_guess(valid_words, result_is_correct_word, guesses_so_far, rating);
                number_of_guesses++;
                guesses_so_far.push_back(guess(current_guess, get_wordle_hints(current_guess, answer_words[i])));
                valid_words = get_valid_words(valid_words, guesses_so_far);
            }

            histogram[number_of_guesses]++;
            if (number_of_guesses > max_guesses) {
                worst_word = answer_words[i];
                max_guesses = number_of_guesses;
            }
        }
        auto stop = high_resolution_clock::now();
        cout << "Done, time: " << duration_cast<microseconds>(stop - start).count() / 1000000.0 << " s" << endl;

        auto overall_stop = high_resolution_clock::now();
        cout << "Total time: " << duration_cast<microseconds>(overall_stop - overall_start).count() / 1000000.0 << " s" << endl;
        cout << "Time per word: " << duration_cast<microseconds>(overall_stop - overall_start).count() / 1000.0 / answer_words.size() << " ms" << endl;

        int total_count = 0, total_guesses = 0;
        for (int i = 0; i < sizeof(histogram) / sizeof(histogram[0]); i++) {
            if (histogram[i] != 0) {
                cout << i << ": " << histogram[i] << endl;
                total_count += histogram[i];
                total_guesses += i * histogram[i];
            }
        }
        double average = double(total_guesses) / total_count;
        cout << "Average: " << average << " guesses" << endl;
        cout << "Worst word was " << worst_word << ":" << endl;
        // solve_single_word_helper(worst_word);

        if (average < best_average) {
            best_first_word_solve_all = first_guess;
            best_average = average;
        }
        cout << "Best first word so far: " << best_first_word_solve_all << " with average of " << best_average << endl;

        // forbid_first_guess(first_guess);
        break;
    }
}

int main() {
#if 0
    for (word_length = 1; word_length <= 500; word_length++) {
        num_hint_values = 1;
        for (int i = 0; i < word_length; i++) {
            num_hint_values *= 3;
        }

        guess_words = read_word_file(GUESS_WORD_FILE);
        if (guess_words.size() > 0) {
            cout << "Valid guesses : " << guess_words.size() << " words of length " << word_length << " in " << GUESS_WORD_FILE << endl;
        }
        if (strcmp(GUESS_WORD_FILE, ANSWER_WORD_FILE) == 0) {
            answer_words = guess_words;
        } else {
            answer_words = read_word_file(ANSWER_WORD_FILE);
        }
        if (answer_words.size() > 0) {
            cout << "Valid answers : " << answer_words.size() << " words of length " << word_length << " in " << ANSWER_WORD_FILE << endl;
        }
        if (answer_words.size() == 0 || guess_words.size() == 0) {
            continue;
        }

        if (should_prefer_dense(answer_words.size())) {
            hint_class_counts = new int[num_hint_values];
        }

        best_first_guess = NULL;
        find_best_first_guess();

        delete[] hint_class_counts;
        hint_class_counts = NULL;
    }
    return 0;
#endif

    string newline;
    cout << "Enter word length: ";
    cin >> word_length;
    getline(cin, newline);
    num_hint_values = 1;
    for (int i = 0; i < word_length; i++) {
        num_hint_values *= 3;
    }

    guess_words = read_word_file(GUESS_WORD_FILE);
    cout << "Valid guesses : " << guess_words.size() << " words of length " << word_length << " in " << GUESS_WORD_FILE << endl;
    if (strcmp(GUESS_WORD_FILE, ANSWER_WORD_FILE) == 0) {
        answer_words = guess_words;
    } else {
        answer_words = read_word_file(ANSWER_WORD_FILE);
    }
    cout << "Valid answers : " << answer_words.size() << " words of length " << word_length << " in " << ANSWER_WORD_FILE << endl;

    if (answer_words.size() == 0 || guess_words.size() == 0) {
        cout << "No words of length " << word_length << " in wordlists, exiting." << endl;
        return 1;
    }

    if (should_prefer_dense(answer_words.size())) {
        hint_class_counts = new int[num_hint_values];
    }

    while (true) {
        cout << "Select one:" << endl;
        cout << " 1. Find best first guess" << endl;
        cout << " 2. Guess unknown word (solve puzzle)" << endl;
        cout << " 3. Show solution for a single given word" << endl;
        cout << " 4. Solve all words in dictionary and show statistics" << endl;
        cout << " 5. Quit" << endl;
        cout << "Enter your choice: ";
        int choice;
        cin >> choice;
        getline(cin, newline);

        switch (choice) {
        case 1:
            find_best_first_guess();
            break;
        case 2:
            guess_unknown_word();
            break;
        case 3:
            solve_single_word();
            break;
        case 4:
            solve_all_words_in_dictionary();
            break;
        case 5:
            return 0;
        default:
            cout << "Invalid option selected." << endl;
            break;
        }
    }
}