Wordle Solver (hard mode tree walk C++)

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

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

// In Wordle hard mode, black/grey hints do *not* have to be used, only yellow and green
bool matches_hints_guess(const char* guess_word, const vector<guess>& guesses_so_far) {
    for (int i = 0; i < guesses_so_far.size(); i++) {
        hint h1 = guesses_so_far[i].hint;
        hint h2 = get_wordle_hints(guesses_so_far[i].word, guess_word);

        for (int i = 0; i < word_length; i++) {
            int color1 = h1 % 3;
            int color2 = h2 % 3;
            if (color1 != 0 && color1 != color2) {
                return false;
            }
            h1 /= 3;
            h2 /= 3;
        }
    }
    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;
}

vector<char*> get_valid_guesses(const vector<char*>& guess_words, const vector<guess>& guesses_so_far) {
    vector<char*> result;
    for (int i = 0; i < guess_words.size(); i++) {
        if (matches_hints_guess(guess_words[i], guesses_so_far)) {
            result.push_back(guess_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("SNARE");
    }
}

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 print_words(const vector<char*>& valid_words);

void best_4th() {
    ifstream in("solutions6_minus.txt");
    ofstream of("results.4th.txt");

    while (true) {
        map<hint, int> hint_class_counts;
        // int best_worst_count_so_far = 2;
        // int best_worst_count_so_far = 6; // NOLES CRAFT WIMPY
        int best_pair_i, best_pair_j = -1;

        cout << "Precomputing best first guess..." << endl;
        cache_best_first_guess();
        char* first_guess = best_first_guess;
#if 1
        string line;
        getline(in, line);
        if (in.eof()) break;
        if (line.length() < word_length * 3 + 2) {
            continue;
        }
        char* first_word = _strdup(line.c_str());
        first_word[word_length] = '\0';
        char* second_word = _strdup(line.c_str() + word_length + 1);
        second_word[word_length] = '\0';
        char* third_word = _strdup(line.c_str() + word_length + 1 + word_length + 1);
        third_word[word_length] = '\0';
        // cout << "First guess: " << first_guess << endl;
        // first_guess = _strdup("TAILS");
#else
        char* first_word = _strdup("CHANT");
        char* second_word = _strdup("SORED");
        char* third_word = _strdup("BLIMP");
        // char* forth_word = _strdup("FUGLY");
        // EVOKE
#endif
        cout << "First three guesses: " << first_word << " " << second_word << " " << third_word << endl;

        hint_class_counts.clear();
        for (int m = 0; m < answer_words.size(); m++) {
            hint combined_hint = get_wordle_hints(first_word, answer_words[m]) * num_hint_values * num_hint_values +
                get_wordle_hints(second_word, answer_words[m]) * num_hint_values +
                get_wordle_hints(third_word, answer_words[m]);
            int count = hint_class_counts[combined_hint];
            hint_class_counts[combined_hint] = count + 1;
        }

        // We want the word list sorted with largest classes first, this will give us the fastest break out
        std::vector<std::pair<hint, int>> pairs;
        for (auto iter = hint_class_counts.begin(); iter != hint_class_counts.end(); ++iter) {
            pairs.push_back(*iter);
        }
        sort(pairs.begin(), pairs.end(), [=](std::pair<hint, int>& a, std::pair<hint, int>& b) {
            return a.second > b.second;
        });

        int guess_rating = 0;
        vector<char*> valid_words_worst_class;
        vector<char*> answer_words_minus_singletons;
        vector<guess> guesses_so_far;
        vector<guess> guesses_so_far_worst;
        for (auto iter = pairs.begin(); iter != pairs.end(); iter++) {
            cout << iter->second << " ";
            if (iter->second <= 1) {
                break;
            }
            guesses_so_far.clear();
            guesses_so_far.push_back(guess(first_word, iter->first / num_hint_values / num_hint_values));
            guesses_so_far.push_back(guess(second_word, (iter->first / num_hint_values) % num_hint_values));
            guesses_so_far.push_back(guess(third_word, iter->first % num_hint_values));
            vector<char*> valid_words_this_class = get_valid_words(answer_words, guesses_so_far);
            for (int m = 0; m < valid_words_this_class.size(); m++) {
                answer_words_minus_singletons.push_back(valid_words_this_class[m]);
            }
        }
        cout << endl;
        cout << "Singletons removed: " << (answer_words.size() - answer_words_minus_singletons.size()) << endl;

        for (int i = 0; i < guess_words.size(); i++) {
            for (int j = i + 1; j < guess_words.size(); j++) {
                hint_class_counts.clear();
                bool skip = false;
                for (int m = 0; m < answer_words_minus_singletons.size(); m++) {
                    hint combined_hint = get_wordle_hints(guess_words[i], answer_words_minus_singletons[m]) * num_hint_values * num_hint_values * num_hint_values * num_hint_values +
                        get_wordle_hints(guess_words[j], answer_words_minus_singletons[m]) * num_hint_values * num_hint_values * num_hint_values +
                        get_wordle_hints(first_word, answer_words_minus_singletons[m]) * num_hint_values * num_hint_values +
                        get_wordle_hints(second_word, answer_words_minus_singletons[m]) * num_hint_values +
                        get_wordle_hints(third_word, answer_words_minus_singletons[m]);
                    int count = hint_class_counts[combined_hint];
                    hint_class_counts[combined_hint] = count + 1;
                    if (count + 1 > 2) {
                        skip = true;
                        break;
                    }
                }
                if (skip) {
                    continue;
                }

                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 <= 2) {
                    cout << first_word << " " << second_word << " " << third_word << " " << guess_words[i] << " " << guess_words[j] << " " << guess_rating << endl;
                    of << first_word << " " << second_word << " " << third_word << " " << guess_words[i] << " " << guess_words[j] << " " << guess_rating << endl;

                    std::vector<std::pair<hint, int>> pairs;
                    for (auto iter = hint_class_counts.begin(); iter != hint_class_counts.end(); ++iter) {
                        pairs.push_back(*iter);
                    }
                    sort(pairs.begin(), pairs.end(), [=](std::pair<hint, int>& a, std::pair<hint, int>& b) {
                        return a.second > b.second;
                    });

                    for (auto iter = pairs.begin(); iter != pairs.end(); iter++) {
                        cout << iter->second << " ";
                        if (iter->second <= 1) {
                            break;
                        }
                        guesses_so_far.clear();
                        hint combined_hint = iter->first;
                        guesses_so_far.push_back(guess(third_word, combined_hint % num_hint_values));
                        combined_hint /= num_hint_values;
                        guesses_so_far.push_back(guess(second_word, combined_hint % num_hint_values));
                        combined_hint /= num_hint_values;
                        guesses_so_far.push_back(guess(first_word, combined_hint % num_hint_values));
                        combined_hint /= num_hint_values;
                        guesses_so_far.push_back(guess(guess_words[j], combined_hint % num_hint_values));
                        combined_hint /= num_hint_values;
                        guesses_so_far.push_back(guess(guess_words[i], combined_hint % num_hint_values));
                        vector<char*> valid_words_this_class = get_valid_words(answer_words, guesses_so_far);
                        cout << "[";
                        for (int m = 0; m < valid_words_this_class.size(); m++) {
                            cout << valid_words_this_class[m];
                            if (m != valid_words_this_class.size() - 1) {
                                cout << ",";
                            }
                        }
                        cout << "] ";
                    }
                    cout << endl;
                }
            }
        }
    }
}

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;
    double best_average = 100000.0f;

    auto overall_start = high_resolution_clock::now();

    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;
#if false
        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("CHANT");
        second_guess = _strdup("SORED");
        third_guess = _strdup("BLIMP");
        cout << "First three guesses: " << first_guess << " " << second_guess << " " << third_guess << endl;
        // first_guess = _strdup("TAILS");
#endif

#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 1
        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 1
        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) {
                // if (guesses_so_far.size() == 3) {
                //     current_guess = forth_word;
                // } else {
                    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_forth_word = forth_word;
            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;
        // cout << "Best fourth word so far: " << best_forth_word << " 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 hint_count_greens(hint h) {
    int num_greens = 0;
    for (int i = 0; i < word_length; i++) {
        if ((h % 3) == 2) {
            num_greens++;
        }
        h /= 3;
    }
    return num_greens;
}

// If depth is >= depth_limit_max, just return depth_limit_max
int hard_mode_get_tree_height(ofstream& of, vector<char*> valid_guesses, vector<char*> valid_answers, vector<guess>& guesses_so_far, int depth_limit_min, int depth_limit_max) {
    if (depth_limit_max <= 1) {
        return depth_limit_max;
    }
    if (valid_answers.size() <= 2) {
        return valid_answers.size();
    }
    depth_limit_min = max(2, depth_limit_min);

    int min_depth = depth_limit_max;
    int best_guess = -1;
    vector<int> hint_class_counts;
    hint_class_counts.resize(num_hint_values);

    char letters_in_answers[(int)'Z' + 1] = { 0 };
    for (int i = 0; i < valid_answers.size(); i++) {
        for (int cidx = 0; cidx < word_length; cidx++) {
            letters_in_answers[valid_answers[i][cidx]] = 1;
        }
    }

    map<string, bool> guess_classes;
    for (int i = 0; i < valid_guesses.size(); i++) {
        bool found_non_answer_letter = false;
        string guess_class_str(valid_guesses[i]);
        for (int cidx = 0; cidx < word_length; cidx++) {
            if (!letters_in_answers[guess_class_str[cidx]]) {
                guess_class_str[cidx] = '-';
                found_non_answer_letter = true;
            }
        }
        if (found_non_answer_letter) {
            if (guess_classes.find(guess_class_str) != guess_classes.end()) {
                continue; // Duplicate on all letters occuring in answers, can skip
            }
            guess_classes[guess_class_str] = true;
        }

        for (int j = 0; j < num_hint_values; j++) {
            hint_class_counts[j] = 0;
        }

        int depth_i = 0;
        int max_count = 0;
        for (int m = 0; m < valid_answers.size(); m++) {
            hint hint = get_wordle_hints(valid_guesses[i], valid_answers[m]);
            if (++hint_class_counts[hint] > max_count) {
                max_count = hint_class_counts[hint];
            }
        }

        if (max_count <= 2) {
            depth_i = 1 + max_count;
        } else {
            int non_empty_classes = 0;
            for (hint h = 0; h < num_hint_values; h++) {
                if (hint_class_counts[h] > 0) {
                    non_empty_classes++;
                }
            }
            if (non_empty_classes == 1) {
                // This hint gives no new information, don't bother guessing this word
                continue;
            }

            if (guesses_so_far.size() <= 0) {
                cout << "Starting L" << guesses_so_far.size() << ": ";
                for (int g = 0; g < guesses_so_far.size(); g++) {
                    cout << guesses_so_far[g].word << " " << hint_to_string(guesses_so_far[g].hint) << " ";
                }
                cout << valid_guesses[i] << endl;
            }

            // Count backwards to encounter most constraining classes first, watch out for unsigned overflow
            for (hint h = num_hint_values - 1; h >= 0 && h < num_hint_values; h--) {
                if (hint_class_counts[h] <= 2) {
                    continue;
                }

                int depth_h;
                if (hint_count_greens(h) == word_length - 1) {
                    // Trivial case, all but one are green, we must guess all the remaining words one-by-one
                    depth_h = 1 + hint_class_counts[h];
                } else {
                    guesses_so_far.push_back(guess(valid_guesses[i], h));
                    vector<guess> guesses_so_far_small;
                    guesses_so_far_small.push_back(guess(valid_guesses[i], h));
                    vector<char*> valid_guesses_this_class = get_valid_guesses(valid_guesses, guesses_so_far_small);
                    vector<char*> valid_answers_this_class = get_valid_words(valid_answers, guesses_so_far_small);
                    depth_h = 1 + hard_mode_get_tree_height(of, valid_guesses_this_class, valid_answers_this_class, guesses_so_far,
                        guesses_so_far.size() <= 1 ? 2 : depth_i - 1, depth_limit_max - 1);
                    guesses_so_far.pop_back();
                }

                if (depth_h > depth_i) {
                    depth_i = depth_h;
                    if (depth_i >= min_depth) {
                        break;
                    }
                }
            }
        }

        if (depth_i < min_depth) {
            best_guess = i;
            if (guesses_so_far.size() > 0) {
                min_depth = depth_i;
            }
            if (guesses_so_far.size() <= 0) {
                cout << "Best so far: ";
                of << "Best so far: ";
                cout << "L" << guesses_so_far.size() << ": ";
                of << "L" << guesses_so_far.size() << ": ";
                for (int g = 0; g < guesses_so_far.size(); g++) {
                    cout << guesses_so_far[g].word << " " << hint_to_string(guesses_so_far[g].hint) << " ";
                    of << guesses_so_far[g].word << " " << hint_to_string(guesses_so_far[g].hint) << " ";
                }
                cout << valid_guesses[i] << "  " << depth_i << endl;
                of << valid_guesses[i] << "  " << depth_i << endl;
                of.flush();
            }
        }
        if (min_depth <= depth_limit_min) {
            break;
        }
    }
    if (guesses_so_far.size() <= 1) {
        cout << "L" << guesses_so_far.size() << ": ";
        of << "L" << guesses_so_far.size() << ": ";
        for (int g = 0; g < guesses_so_far.size(); g++) {
            cout << guesses_so_far[g].word << " " << hint_to_string(guesses_so_far[g].hint) << " ";
            of << guesses_so_far[g].word << " " << hint_to_string(guesses_so_far[g].hint) << " ";
        }
        cout << (best_guess == -1 ? "(XXX)" : valid_guesses[best_guess]) << "  " << min_depth << endl;
        of << (best_guess == -1 ? "(XXX)" : valid_guesses[best_guess]) << "  " << min_depth << endl;
        of.flush();
    }
    return min_depth;
}

void hard_mode_analysis() {
    // I just realized that the correct strategy to optimize hard mode in Wordle is blindingly simple.
    // Because the guess pool size is reduced so much with each move, that means the move tree is very small.
    // That means it's totally computationally possible to branch-and-bound to exhaustively try every possible move tree.
    // And if I can heuristically find the longest paths first, I can do the bounding part even faster.
    // at kind of longest path search is more or less exactly what Absurdle is already doing
    vector<guess> guesses_so_far;
    ofstream of("hard_mode_log_small.txt");
    // 5 is SCOWL
    hard_mode_get_tree_height(of, guess_words, answer_words, guesses_so_far, 2, 6);
}

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

    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. Find best set of 3 words to start out with" << endl;
        cout << " 6. Show largest hint class of a set of words" << endl;
        cout << " 7. Get best 4th and 5th words" << endl;
        cout << " 8. Hard mode analysis" << endl;
        cout << " 9. 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:
            if (argc >= 3) {
                thread_num = atoi(argv[1]);
                num_threads = atoi(argv[2]);
            } else {
                thread_num = 0;
                num_threads = 1;
            }
            best_first_k();
            break;
        case 6:
            show_largest_hint_class();
            break;
        case 7:
            best_4th();
            break;
        case 8:
            hard_mode_analysis();
            break;
        case 9:
            return 0;
        default:
            cout << "Invalid option selected." << endl;
            break;
        }
    }
}