Wordle triple search (C++)

#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";
// const char* GUESS_WORD_FILE = "combined_wordlist_rearranged.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;
}

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

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;
}

char* get_worst_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 = 0;
    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("TEARS");
    }
}

struct pairi {
    int i;
    int j;

    bool operator<(const pairi p) const {
        if (i < p.i)
            return true;
        else if (i > p.i)
            return false;
        else
            return j < p.j;
    }
};

int thread_num;
int num_threads;

void best_first_k() {
    map<hint, int> hint_class_counts;
    int best_worst_count_so_far = 7;
    // int best_worst_count_so_far = 6; // NOLES CRAFT WIMPY
    int best_pair_i = -1, best_pair_j = -1, best_pair_k = -1;

    char buf[300];
    sprintf(buf, "results.small.txt", thread_num);
    ofstream of(buf);
    cout << "thread_num: " << thread_num << endl;
    for (int i=thread_num; i < guess_words.size(); i+= num_threads) {
        cout << "i: " << i << " " << guess_words[i] << endl;
        for (int j=i+1; j < guess_words.size(); j++) {
            if ((j % 1000) == 0) {
                cout << "i: " << i << " " << guess_words[i] << " j: " << j << " " << guess_words[j] << endl;
            }

            hint_class_counts.clear();
            for (int m = 0; m < answer_words.size(); m++) {
                int combined_hint = get_wordle_hints(guess_words[i], answer_words[m]) * num_hint_values +
                    get_wordle_hints(guess_words[j], answer_words[m]);
                int count = hint_class_counts[combined_hint];
                hint_class_counts[combined_hint] = count + 1;
            }

            int guess_rating = 0;
            vector<guess> guesses_so_far;
            for (auto iter = hint_class_counts.begin(); iter != hint_class_counts.end(); iter++) {
                if (iter->second >= guess_rating) {
                    guess_rating = iter->second;
                    guesses_so_far.clear();
                    guesses_so_far.push_back(guess(guess_words[i], iter->first / num_hint_values));
                    guesses_so_far.push_back(guess(guess_words[j], iter->first % num_hint_values));
                }
            }
            vector<char*> valid_words_first_2 = get_valid_words(answer_words, guesses_so_far);

            for (int k = j + 1; k < guess_words.size(); k++) {
                hint_class_counts.clear();

                bool exceeded_count = false;
                for (int m = 0; m < valid_words_first_2.size(); m++) {
                    int combined_hint = get_wordle_hints(guess_words[i], valid_words_first_2[m]) * num_hint_values * num_hint_values +
                        get_wordle_hints(guess_words[j], valid_words_first_2[m]) * num_hint_values +
                        get_wordle_hints(guess_words[k], valid_words_first_2[m]);
                    int count = hint_class_counts[combined_hint];
                    hint_class_counts[combined_hint] = count + 1;
                    if (count + 1 > best_worst_count_so_far) {
                        exceeded_count = true;
                        break;
                    }
                }
                if (exceeded_count) {
                    continue;
                }

                for (int m = 0; m < answer_words.size(); m++) {
                    int combined_hint = get_wordle_hints(guess_words[i], answer_words[m]) * num_hint_values * num_hint_values +
                        get_wordle_hints(guess_words[j], answer_words[m]) * num_hint_values +
                        get_wordle_hints(guess_words[k], answer_words[m]);
                    int count = hint_class_counts[combined_hint];
                    hint_class_counts[combined_hint] = count + 1;
                    if (count + 1 > best_worst_count_so_far) {
                        break;
                    }
                }

                int guess_rating = 0;
                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_worst_count_so_far) {
                    best_worst_count_so_far = guess_rating;
                    best_pair_i = i;
                    best_pair_j = j;
                    best_pair_k = k;
                    cout << guess_words[i] << " " << guess_words[j] << " " << guess_words[k] << " " << best_worst_count_so_far << endl;
                    of << guess_words[i] << " " << guess_words[j] << " " << guess_words[k] << " " << best_worst_count_so_far << endl;
                    of.flush();
                } else if (guess_rating == best_worst_count_so_far) {
                    cout << guess_words[i] << " " << guess_words[j] << " " << guess_words[k] << " " << best_worst_count_so_far << endl;
                    of << guess_words[i] << " " << guess_words[j] << " " << guess_words[k] << " " << best_worst_count_so_far << endl;
                    of.flush();
                }
            }
        }
    }

    cout << guess_words[best_pair_i] << " " << guess_words[best_pair_j] << " " << guess_words[best_pair_k] << " " << best_worst_count_so_far << endl;
    of << guess_words[best_pair_i] << " " << guess_words[best_pair_j] << " " << guess_words[best_pair_k] << " " << best_worst_count_so_far << endl;
    of.flush();
}

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 << "[";
    if (valid_words.size() <= 50) {
        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" << ")";
        }
    } else {
        cout << "(" << valid_words.size() << " words)" << endl;
    }
    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 = 100000.0f;
    char* best_first_word_solve_all = NULL;
    char* best_second_word_solve_all = NULL;
    char* best_third_word_solve_all = NULL;

    ifstream in("solutions6.txt");

    while (true) {
        cout << "Precomputing best first guess..." << endl;
        cache_best_first_guess();
        // char* first_guess = best_first_guess;
        string line;
        getline(in, line);
        if (in.eof()) break;
        if (line.length() < word_length * 3 + 2) {
            continue;
        }
        char* first_guess = _strdup(line.c_str());
        first_guess[word_length] = '\0';
        char* second_guess = _strdup(line.c_str() + word_length + 1);
        second_guess[word_length] = '\0';
        char* third_guess = _strdup(line.c_str() + word_length + 1 + word_length + 1);
        third_guess[word_length] = '\0';
        cout << "First guess: " << first_guess << endl;
        // first_guess = _strdup("TAILS");

#if 0
        {
            vector<guess> guesses_so_far_first;
            char* foo;
            foo = _strdup("-----");
            for (int i = 0; i < word_length; i++) {
                for (int j = i + 1; j < word_length; j++) {
                    foo[0] = first_guess[i];
                    foo[1] = first_guess[j];
                    guesses_so_far_first.clear();
                    guesses_so_far_first.push_back(guess(foo, string_to_hint("yykkk")));
                    cout << " " << first_guess[i] << " " << first_guess[j] << " " << get_valid_words(answer_words, guesses_so_far_first).size() << endl;
                    guesses_so_far_first.clear();
                    guesses_so_far_first.push_back(guess(foo, string_to_hint("ykkkk")));
                    cout << " " << first_guess[i] << "!" << first_guess[j] << " " << get_valid_words(answer_words, guesses_so_far_first).size() << endl;
                    guesses_so_far_first.clear();
                    guesses_so_far_first.push_back(guess(foo, string_to_hint("kykkk")));
                    cout << "!" << first_guess[i] << " " << first_guess[j] << " " << get_valid_words(answer_words, guesses_so_far_first).size() << endl;
                    guesses_so_far_first.clear();
                    guesses_so_far_first.push_back(guess(foo, string_to_hint("kkkkk")));
                    cout << "!" << first_guess[i] << "!" << first_guess[j] << " " << get_valid_words(answer_words, guesses_so_far_first).size() << endl;
                    cout << endl;
                }
            }
        }

        {
            vector<guess> guesses_so_far_first;
            char* foo;
            foo = _strdup("-----");
            char* bar;
            bar = _strdup("kkkkk");
            for (int i = 0; i < word_length; i++) {
                for (int j = 0; j < word_length; j++) {
                    guesses_so_far_first.clear();
                    foo[j] = first_guess[i];
                    bar[j] = 'g';
                    guesses_so_far_first.push_back(guess(foo, string_to_hint(bar)));
                    cout << first_guess[i] << " " << j << " " << get_valid_words(answer_words, guesses_so_far_first).size() << endl;
                    bar[j] = 'k';
                    foo[j] = '-';
                }
            }
        }
#endif

        char** second_guesses = NULL;
        int empty_classes = 0;
#if 0
        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);
                second_guesses[i] = _strdup("DECOR");
#if 0
                cout << hint_to_string(i) << " " << valid_words.size() << " " << (second_guesses[i] == NULL ? "" : second_guesses[i]) << endl;
#endif
                if (valid_words.size() == 0) {
                    empty_classes++;
                }
                // print_words(valid_words);
                // cout << endl;

                // 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;
            cout << "Empty hint classes: " << empty_classes << endl;
        }
#endif

        char*** third_guesses = NULL;
#if 0
        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));
                    guesses_so_far.push_back(guess(second_guess, i));
                    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 0
                    if (valid_words.size() > 10) {
                        cout << hint_to_string(i) << " " << (second_guesses[i] == NULL ? "null" : second_guesses[i]) << " " << hint_to_string(j) << " " << valid_words.size() << endl;
                    }
#endif
                }
                // 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;
        }
#endif

        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);
                }
                current_guess = second_guess;
                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])];
                current_guess = third_guess;
                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;
            }

#if 0
            if (number_of_guesses == 5) {
                cout << "    " << answer_words[i] << ": ";
                for (int i = 0; i < guesses_so_far.size(); i++) {
                    cout << guesses_so_far[i].word << " " << hint_to_string(guesses_so_far[i].hint) << "  ";
                }
                cout << endl;
            }
#endif
        }
        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_second_word_solve_all = second_guess;
            best_third_word_solve_all = third_guess;
            best_average = average;
        }
        cout << "Best triple so far: " << best_first_word_solve_all << " " << best_second_word_solve_all << " " << best_third_word_solve_all << " with average of " << best_average << endl;

        forbid_first_guess(first_guess);
        // break;
    }
}

void show_largest_hint_class() {
    cout << "Enter three words:" << endl;
    vector<char*> words;
    for (int i = 0; i < 3; i++) {
        string word;
        cout << "> ";
        getline(cin, word);
        for (int i = 0; i < guess_words.size(); i++) {
            if (strcmp(guess_words[i], word.c_str()) == 0) {
                words.push_back(guess_words[i]);
            }
        }
    }

    map<hint, int> hint_class_counts;
    // int best_worst_count_so_far = 8;
    int best_worst_count_so_far = 6; // NOLES CRAFT WIMPY
    int best_pair_i = -1, best_pair_j = -1, best_pair_k = -1;

    for (int m = 0; m < answer_words.size(); m++) {
        int combined_hint = 0;
        for (int i = words.size() - 1; i >= 0; i--) {
            combined_hint *= num_hint_values;
            combined_hint += get_wordle_hints(words[i], answer_words[m]);
        }
        hint_class_counts[combined_hint]++;
    }

    int guess_rating = 0;
    vector<guess> guesses_so_far;
    for (auto iter = hint_class_counts.begin(); iter != hint_class_counts.end(); iter++) {
        if (iter->second >= guess_rating) {
            guess_rating = iter->second;
            guesses_so_far.clear();

            hint combined_hint = iter->first;
            for (int i = 0; i < words.size(); i++) {
                guesses_so_far.push_back(guess(words[i], combined_hint % num_hint_values));
                combined_hint /= num_hint_values;
            }
        }
    }
    vector<char*> valid_words = get_valid_words(answer_words, guesses_so_far);

    for (int i = 0; i < guesses_so_far.size(); i++) {
        cout << guesses_so_far[i].word << " " << hint_to_string(guesses_so_far[i].hint) << endl;
    }
    cout << endl;
    print_words(valid_words);
    cout << endl;
}

int main(int argc, char* argv[]) {
#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);
    word_length = 5;
    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];
    }

    // thread_num = atoi(argv[1]);
    // num_threads = atoi(argv[2]);
    // thread_num = 0;
    // num_threads = 1;
    // best_first_k();
    // return 0;

    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. Find best set of 2 words to start out with" << endl;
        cout << " 6. Show largest hint class of a set of words" << endl;
        cout << " 7. 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:
            best_first_k();
        case 6:
            show_largest_hint_class();
            break;
        case 7:
            return 0;
        default:
            cout << "Invalid option selected." << endl;
            break;
        }
    }
}