Wordle Optimal Solver (C++)

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

using namespace std;
using namespace std::chrono;

#if defined(_MSC_VER) || defined(__INTEL_COMPILER)
#define release_assert(x)  if (!(x)) { __debugbreak(); exit(1); }
#else
#define release_assert(x)  if (!(x)) { throw new exception(); }
#endif

// 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";
const char* ANSWER_WORD_FILE = "shuffled_real_wordles_best_first.txt";
// const char* GUESS_WORD_FILE = "shuffled_real_wordles_best_first.txt";

int word_length;
vector<char*> guess_words;
vector<int> guess_words_letter_masks;
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++;
    }
}

const int MEMORY_POOL_WORDS = 200000; // Enough even for largest dictionary
char* memory_pool = NULL;
char* memory_pool_next;
map<string, char*> tokenized_words;

vector<char*> read_word_file(const char* filename) {
    if (memory_pool == NULL) {
        memory_pool = new char[(word_length + 1) * MEMORY_POOL_WORDS];
        memory_pool_next = memory_pool;
    }
    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 = memory_pool_next;
                strcpy(word, line.c_str());
                memory_pool_next += word_length + 1;
                if (memory_pool_next + word_length + 1 >= memory_pool + (word_length + 1) * MEMORY_POOL_WORDS) {
                    cout << "Memory pool exceeded, increase MEMORY_POOL_WORDS" << endl;
                    exit(1);
                }
                toupper_cstr(word);

                if (tokenized_words.find(word) != tokenized_words.end()) {
                    result.push_back(tokenized_words[word]);
                } else {
                    tokenized_words[word] = 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[5];
    int buf_size = 0;

    for (int i = 0; i < 5; i++) {
        if (guess[i] != answer[i]) {
            buf[buf_size] = answer[i];
            buf_size++;
        }
    }
    for (int i = 0; i < 5; i++) {
        result *= 3;
        if (guess[i] == answer[i]) {
            result += 2; // green
        } else {
            for (int j = 0; j < buf_size; j++) {
                if (guess[i] == buf[j]) {
                    result += 1;
                    buf[j] = ' ';
                    break;
                }
            }

            // Otherwise black/grey 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 = '-';
        }
        result = c + result;
        hint /= 3;
    }
    return result;
}

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

    guess(char* guess_word, char* answer_word) {
        this->word = guess_word;
        this->hint = get_wordle_hints(guess_word, answer_word);
    }

    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_words(const vector<char*>& answer_words, char* guess_word, hint h) {
    vector<char*> result;
    for (int i = 0; i < answer_words.size(); i++) {
        if (get_wordle_hints(guess_word, answer_words[i]) == h) {
            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_perfect_split(const vector<char*>& valid_words, bool& is_valid_word) {
    assert(valid_words.size() > 1);

    if (valid_words.size() > num_hint_values) {
        return NULL;
    }

    vector<int> valid_words_letter_masks;
    valid_words_letter_masks.resize(valid_words.size());
    for (int i = 0; i < valid_words.size(); i++) {
        int letter_mask = 0;
        for (int cidx = 0; cidx < word_length; cidx++) {
            letter_mask |= 1 << (valid_words[i][cidx] - 'A');
        }
        valid_words_letter_masks[i] = letter_mask;
    }

    for (int i = 0; i < valid_words.size(); i++) {
        // Check first for two kkkkk quickly using bitmaps
        int count = 0;
        for (int j = 0; j < valid_words.size(); j++) {
            if ((valid_words_letter_masks[j] & valid_words_letter_masks[i]) == 0) {
                count++;
                if (count >= 2) break;
            }
        }
        if (count >= 2) {
            continue;
        }

        memset(hint_class_counts, 0, sizeof(int) * num_hint_values);
        bool found_perfect_split = true;
        for (int j = 0; j < valid_words.size(); j++) {
            int idx = get_wordle_hints(valid_words[i], valid_words[j]);
            hint_class_counts[idx]++;
            if (hint_class_counts[idx] > 1) {
                found_perfect_split = false;
                break;
            }
        }
        if (found_perfect_split) {
            is_valid_word = true;
            return valid_words[i];
        }
    }

    for (int i = 0; i < guess_words.size(); i++) {
        // Check first for two kkkkk quickly using bitmaps
        int count = 0;
        for (int j = 0; j < valid_words.size(); j++) {
            if ((valid_words_letter_masks[j] & guess_words_letter_masks[i]) == 0) {
                count++;
                if (count >= 2) break;
            }
        }
        if (count >= 2) {
            continue;
        }

        memset(hint_class_counts, 0, sizeof(int) * num_hint_values);
        bool found_perfect_split = true;
        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] > 1) {
                found_perfect_split = false;
                break;
            }
        }
        if (found_perfect_split) {
            is_valid_word = false;
            return guess_words[i];
        }
    }

    is_valid_word = false;
    return NULL;
}

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 = tokenized_words["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;
        }
        if (tokenized_words.find(answer) == tokenized_words.end()) {
            cout << "Word is not in guess list or solutions list." << endl;
            continue;
        }
        answer = tokenized_words[answer];
        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;
}

int sum_sizes(vector<vector<guess>> all_paths) {
    int result = 0;
    for (int i = 0; i < all_paths.size(); i++) {
        result += all_paths[i].size();
    }
    return result;
}

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, vector<vector<guess>>& all_paths, int& path_guesses_count, bool collect_paths);

void hard_mode_process_word(char* guess_word, ofstream& of, vector<char*>& valid_guesses, vector<char*>& valid_answers, vector<guess>& guesses_so_far, int depth_limit_min, int depth_limit_max, int& min_depth, char*& best_guess, char* letters_in_answers, map<string, bool>& guess_classes, vector<vector<guess>>& all_paths, int& path_guesses_count, bool collect_paths) {
    vector<int> hint_class_counts;
    hint_class_counts.resize(num_hint_values);

    bool found_non_answer_letter = false;
    string guess_class_str(guess_word);
    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()) {
            return; // Duplicate on all letters occuring in answers, can skip
        }
        guess_classes[guess_class_str] = true;
    }

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

    vector<vector<guess>> all_paths_this_word;
    int path_guesses_count_this_word = 0;

    if (max_count <= 2) {
        depth_i = 1 + max_count;

        if (collect_paths)
        for (hint h = num_hint_values - 1; h >= 0 && h < num_hint_values; h--) {
            if (hint_class_counts[h] == 0) {
                // do nothing
            } else if (h == num_hint_values - 1 /* all green */) {
                guesses_so_far.push_back(guess(guess_word, num_hint_values - 1));
                all_paths_this_word.push_back(guesses_so_far);
                guesses_so_far.pop_back();
            } else { // (hint_class_counts[h] <= 2)
                guesses_so_far.push_back(guess(guess_word, h));
                vector<guess> guesses_so_far_small;
                guesses_so_far_small.push_back(guess(guess_word, h));
                vector<char*> valid_answers_this_class = get_valid_words(valid_answers, guesses_so_far_small);
                for (int i = 0; i < valid_answers_this_class.size(); i++) {
                    for (int j = 0; j <= i; j++) {
                        guesses_so_far.push_back(guess(valid_answers_this_class[j], get_wordle_hints(valid_answers_this_class[j], valid_answers_this_class[i])));
                    }
                    all_paths_this_word.push_back(guesses_so_far);
                    for (int j = 0; j <= i; j++) {
                        guesses_so_far.pop_back();
                    }
                }
                guesses_so_far.pop_back();
            }
        }

        for (hint h = num_hint_values - 1; h >= 0 && h < num_hint_values; h--) {
            if (hint_class_counts[h] == 0) {
                // do nothing
            } else if (h == num_hint_values - 1 /* all green */) {
                path_guesses_count_this_word += guesses_so_far.size() + 1;
            } else { // (hint_class_counts[h] <= 2)
                for (int i = 1; i <= hint_class_counts[h]; i++) {
                    path_guesses_count_this_word += guesses_so_far.size() + 1 + i;
                }
            }
        }
        if (collect_paths && path_guesses_count_this_word != sum_sizes(all_paths_this_word)) {
            cout << "BAD" << endl;
        }
    } 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
            return;
        }

        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 << guess_word << 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] == 0) {
                continue;
            } else if (h == num_hint_values - 1 /* all green */) {
                if (collect_paths) {
                    guesses_so_far.push_back(guess(guess_word, num_hint_values - 1));
                    all_paths_this_word.push_back(guesses_so_far);
                    guesses_so_far.pop_back();
                }
                path_guesses_count_this_word += guesses_so_far.size() + 1;
                continue;
            } else if (hint_class_counts[h] <= 2) {
                if (collect_paths) {
                    guesses_so_far.push_back(guess(guess_word, h));
                    vector<guess> guesses_so_far_small;
                    guesses_so_far_small.push_back(guess(guess_word, h));
                    vector<char*> valid_answers_this_class = get_valid_words(valid_answers, guesses_so_far_small);
                    for (int i = 0; i < valid_answers_this_class.size(); i++) {
                        for (int j = 0; j <= i; j++) {
                            guesses_so_far.push_back(guess(valid_answers_this_class[j], get_wordle_hints(valid_answers_this_class[j], valid_answers_this_class[i])));
                        }
                        all_paths_this_word.push_back(guesses_so_far);
                        for (int j = 0; j <= i; j++) {
                            guesses_so_far.pop_back();
                        }
                    }
                    guesses_so_far.pop_back();
                }
                for (int i = 1; i <= hint_class_counts[h]; i++) {
                    path_guesses_count_this_word += guesses_so_far.size() + 1 + i;
                }
                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];

                if (collect_paths) {
                    guesses_so_far.push_back(guess(guess_word, h));
                    vector<guess> guesses_so_far_small;
                    guesses_so_far_small.push_back(guess(guess_word, h));
                    vector<char*> valid_answers_this_class = get_valid_words(valid_answers, guesses_so_far_small);
                    for (int i = 0; i < valid_answers_this_class.size(); i++) {
                        for (int j = 0; j <= i; j++) {
                            guesses_so_far.push_back(guess(valid_answers_this_class[j], get_wordle_hints(valid_answers_this_class[j], valid_answers_this_class[i])));
                        }
                        all_paths_this_word.push_back(guesses_so_far);
                        for (int j = 0; j <= i; j++) {
                            guesses_so_far.pop_back();
                        }
                    }
                    guesses_so_far.pop_back();
                }
                for (int i = 0; i < hint_class_counts[h]; i++) {
                    path_guesses_count_this_word += guesses_so_far.size() + (1 + i);
                }
            } else {
                guesses_so_far.push_back(guess(guess_word, h));
                vector<guess> guesses_so_far_small;
                guesses_so_far_small.push_back(guess(guess_word, h));
                // vector<char*> valid_guesses_this_class;
                // if (valid_guesses_sample.size() > 0) {
                //     valid_guesses_this_class = get_valid_guesses(valid_guesses_sample, guesses_so_far_small);
                // } else {
                //     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);
                vector<vector<guess>> all_paths_this_class;
                int path_guess_counts_this_class = INT_MAX;
                depth_h = 1 + hard_mode_get_tree_height(of, /*valid_guesses_this_class*/ valid_guesses, valid_answers_this_class, guesses_so_far,
                    guesses_so_far.size() <= 1 ? 2 : depth_i - 1, depth_limit_max - 1, all_paths_this_class, path_guess_counts_this_class,
                    guesses_so_far.size() == 1 ? true : collect_paths);
                // if (collect_paths && all_paths_this_class.size() > 0 && all_paths_this_class.size() != valid_answers_this_class.size()) {
                    // cout << "MISSING WORDS CLASS" << endl;
                // }
                if (collect_paths) {
                    for (int z = 0; z < all_paths_this_class.size(); z++) {
                        all_paths_this_word.push_back(all_paths_this_class[z]);
                    }
                }
                path_guesses_count_this_word += path_guess_counts_this_class;
                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 || (depth_i == min_depth && path_guesses_count_this_word < path_guesses_count)) {
        if ((best_guess != NULL && strcmp(best_guess, "TRYST") == 0) && strcmp(guess_word, "ARISE") == 0) {
            // cout << "foo" << endl;
        }
        best_guess = guess_word;
        if (collect_paths) {
            all_paths = all_paths_this_word;
            // if (all_paths.size() != valid_answers.size()) {
            //     cout << "MISSING WORDS" << endl;
            // }
            // if (collect_paths && path_guesses_count_this_word != sum_sizes(all_paths)) {
            //     cout << "BAD" << endl;
            // }
        }
        path_guesses_count = path_guesses_count_this_word;

        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 << guess_word << "  " << depth_i << endl;
            of << guess_word << "  " << depth_i << endl;
            of.flush();
        }
    }
}


// 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, vector<vector<guess>>& all_paths, int& path_guesses_count, bool collect_paths) {
    if (depth_limit_max <= 1) {
        path_guesses_count = 1000000;
        return depth_limit_max;
    }
    if (valid_answers.size() <= 2) {
        if (collect_paths) {
            for (int i = 0; i < valid_answers.size(); i++) {
                for (int j = 0; j <= i; j++) {
                    guesses_so_far.push_back(guess(valid_answers[j], get_wordle_hints(valid_answers[j], valid_answers[i])));
                }
                all_paths.push_back(guesses_so_far);
                for (int j = 0; j <= i; j++) {
                    guesses_so_far.pop_back();
                }
            }
        }
        path_guesses_count = 0;
        for (int i = 0; i < valid_answers.size(); i++) {
            path_guesses_count += guesses_so_far.size() + (1 + i);
        }
        return valid_answers.size();
    }
    depth_limit_min = max(2, depth_limit_min);

    int min_depth = depth_limit_max;
    char* best_guess = NULL;

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

    vector<vector<guess>> all_paths_this_guess;

    // Before everything try the optimal entropy word, this will help speed up the rest
    map<string, bool> guess_classes;
    bool result_is_correct_word;
    int rating;
    if (guesses_so_far.size() > 0) {
        best_first_guess = get_best_guess(valid_answers, result_is_correct_word, guesses_so_far, rating);
    } else {
        best_first_guess = tokenized_words["TRACE"];
    }
    hard_mode_process_word(best_first_guess, of, valid_guesses, valid_answers, guesses_so_far, depth_limit_min, depth_limit_max, min_depth, best_guess, letters_in_answers, guess_classes, all_paths_this_guess, path_guesses_count, guesses_so_far.size() == 0 ? true : false);

    // Process valid answers first, this gives us a chance of guessing them prior to having full information,
    // gives a slightly smaller tree. This will also tend to speed up the search by trying good candidates first.
    for (int i = 0; min_depth > depth_limit_min && i < valid_answers.size(); i++) {
        if (strcmp(valid_answers[i], best_first_guess) == 0) continue;
        hard_mode_process_word(valid_answers[i], of, valid_guesses, valid_answers, guesses_so_far, depth_limit_min, depth_limit_max, min_depth, best_guess, letters_in_answers, guess_classes, all_paths_this_guess, path_guesses_count, guesses_so_far.size() == 0 ? true : false);
        // if (min_depth <= 2) {
        //     break;
        // }
        if (min_depth < /*<=*/ depth_limit_min || min_depth <= 2) {
            break;
        }
    }
    for (int i = 0; min_depth > depth_limit_min && i < valid_guesses.size(); i++) {
        if (strcmp(valid_guesses[i], best_first_guess) == 0) continue;
        bool found = false;
        for (int j = 0; j < valid_answers.size(); j++) {
            if (strcmp(valid_guesses[i], valid_answers[j]) == 0) {
                found = true;
                break;
            }
        }
        if (found) {
            continue;
        }

        hard_mode_process_word(valid_guesses[i], of, valid_guesses, valid_answers, guesses_so_far, depth_limit_min, depth_limit_max, min_depth, best_guess, letters_in_answers, guess_classes, all_paths_this_guess, path_guesses_count, guesses_so_far.size() == 0 ? true : false);

        // if (min_depth <= 2) {
        //     break;
        // }
        if (min_depth < /*<=*/ depth_limit_min || min_depth <= 2) {
            break;
        }
    }

    if (collect_paths && best_guess != NULL) {
        // Redo this word with collect_paths turned on
        guess_classes.clear();
        min_depth++;
        hard_mode_process_word(best_guess, of, valid_guesses, valid_answers, guesses_so_far, depth_limit_min, depth_limit_max, min_depth, best_guess, letters_in_answers, guess_classes, all_paths_this_guess, path_guesses_count, true);
        for (int i = 0; i < all_paths_this_guess.size(); i++) {
            all_paths.push_back(all_paths_this_guess[i]);
        }
    }

    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 == NULL ? "(XXX)" : best_guess) << " " << min_depth << " ";
        of << (best_guess == NULL ? "(XXX)" : best_guess) << " " << min_depth;
        if (valid_answers.size() <= 10) {
            print_words(valid_answers);
        }
        cout << endl;
        of << endl;

        if (collect_paths && guesses_so_far.size() == 1) {
            for (int i = 0; i < all_paths_this_guess.size(); i++) {
                cout << "PATH: ";
                of << "PATH: ";
                for (int j = 0; j < all_paths_this_guess[i].size(); j++) {
                    cout << all_paths_this_guess[i][j].word << " " << hint_to_string(all_paths_this_guess[i][j].hint) << " ";
                    of << all_paths_this_guess[i][j].word << " " << hint_to_string(all_paths_this_guess[i][j].hint) << " ";
                }
                cout << endl;
                of << endl;
            }
        }

        of.flush();

        if (guesses_so_far.size() == 1) {
            // print_optimal_solution_tree()
        }
    }
    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("normal_mode_log_sample_with_paths_new.txt");
    // 5 is SCOWL

    vector<vector<guess>> all_paths;
    int path_guesses_count = INT_MAX;
    hard_mode_get_tree_height(of, guess_words, answer_words, guesses_so_far, 2, 6, all_paths, path_guesses_count, true);
}

bool is_duplicate_guess(map<string, bool>& guess_classes, char* letters_in_answers, char* guess_word, bool add_nonoverlap_to_map) {
    string guess_class_str(guess_word);
    bool no_overlap = true;
    for (int cidx = 0; cidx < word_length; cidx++) {
        if (!letters_in_answers[guess_class_str[cidx]]) {
            guess_class_str[cidx] = '-';
            no_overlap = false;
        }
    }
    if (guess_classes.find(guess_class_str) != guess_classes.end()) {
        return true; // Duplicate on all letters occuring in answers, can skip
    }
    if (add_nonoverlap_to_map || !no_overlap) {
        guess_classes[guess_class_str] = true;
    }
    return false;
}

int total_print_guesses_count = 0;
int total_print_guesses_guesses = 0;
vector<int> print_guesses_stats;
map<string, bool> used_guess_prefixes;
map<char*, bool> words_seen;
ofstream print_guess_file("print_guesses.txt");
void reset_print_guesses() {
    total_print_guesses_count = 0;
    total_print_guesses_guesses = 0;
    used_guess_prefixes.clear();
    words_seen.clear();
    print_guesses_stats.clear();
}

void print_guesses(vector<guess> guesses) {
    if (print_guesses_stats.empty()) {
        print_guesses_stats.resize(7);
    }
    print_guesses_stats[guesses.size()]++;

    // Validate while we're at it
    release_assert(guesses.size() <= 5);
    release_assert(guesses[guesses.size() - 1].hint == num_hint_values - 1); // Last hint is all green
    words_seen[guesses[guesses.size() - 1].word] = true;

    // Prefixes must be unique otherwise the next move to take in a situation is ill-defined
    string guess_prefix;
    for (int i = 0; i < guesses.size() - 1; i++) {
        guess_prefix += guesses[i].word + hint_to_string(guesses[i].hint);
    }
    release_assert(used_guess_prefixes.find(guess_prefix) == used_guess_prefixes.end());
    used_guess_prefixes[guess_prefix] = true;

    // If this is zero it means the hints are inconsistent with the final word
    release_assert(get_valid_words(answer_words, guesses).size() == 1);

    // Count them up, make sure we get them all
    total_print_guesses_count++;
    total_print_guesses_guesses += guesses.size();

    for (int i = 0; i < guesses.size(); i++) {
        cout << guesses[i].word << " " << hint_to_string(guesses[i].hint) << " ";
        print_guess_file << guesses[i].word << " " << hint_to_string(guesses[i].hint) << " ";
    }
    cout << endl;
    print_guess_file << endl;
    print_guess_file.flush();
}

int can_solve_in(vector<char*>& valid_answers, int remaining_guesses, char* last_guess, hint h, vector<guess>& guesses_so_far, bool should_print, int max_total_guesses);

int can_solve_with_next_guess(char* current_guess, vector<char*>& valid_answers, int remaining_guesses, char* last_guess, hint h, vector<guess>& guesses_so_far, bool should_print, int max_total_guesses) {
    steady_clock::time_point start, stop;
    double time_sec;
    // if (remaining_guesses == 4) {
    //     start = high_resolution_clock::now();
    // }
    // if (remaining_guesses >= 4) cout << i << " " << current_guess << endl;

    vector<int> hint_class_counts;
    hint_class_counts.resize(num_hint_values);

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

    int total_guess_count = 0;
    bool passed_all_hint_classes = true;
    if (max_count == valid_answers.size()) {
        return INT_MAX; // This guess word gives no information, force skip it
    // } else if (max_count <= 2) {
    //     passed_all_hint_classes = (max_count <= remaining_guesses - 1);
    } else {
        // This lower bound assumes each hint class of size >= 3 will have a perfect split and resolve in two guesses
        int total_guess_count_lower_bound = 0;
        for (hint h = num_hint_values - 1; h >= 0 && h < num_hint_values; h--) {
            // None of these will be the bottleneck otherwise max_count <= 2 above would have caught it
            if (hint_class_counts[h] == 0) {
                ; // Do nothing
            } else if (h == num_hint_values - 1 /* all green */) {
                total_guess_count_lower_bound += guesses_so_far.size() + 1;
            } else if (hint_class_counts[h] == 1) {
                total_guess_count_lower_bound += guesses_so_far.size() + 2;
            } else if (hint_class_counts[h] == 2) {
                total_guess_count_lower_bound += (guesses_so_far.size() + 2) + (guesses_so_far.size() + 3);
            } else {
                total_guess_count_lower_bound += hint_class_counts[h] * ((guesses_so_far.size() + 1) + 2) - 1;
            }
            if (total_guess_count_lower_bound >= max_total_guesses) {
                return INT_MAX;
            }
        }

        for (hint h = num_hint_values - 1; h >= 0 && h < num_hint_values; h--) {
            // None of these will be the bottleneck otherwise max_count <= 2 above would have caught it
            if (hint_class_counts[h] == 0) {
                ; // Do nothing
            } else if (!should_print && h == num_hint_values - 1 /* all green */) {
                total_guess_count += guesses_so_far.size() + 1;
            } else if (!should_print && hint_class_counts[h] == 1) {
                total_guess_count += guesses_so_far.size() + 2;
            } else if (!should_print && hint_class_counts[h] == 2) {
                total_guess_count += (guesses_so_far.size() + 2) + (guesses_so_far.size() + 3);
            } else {

                vector<char*> valid_answers_this_class = get_valid_words(valid_answers, current_guess, h);

                guesses_so_far.push_back(guess(current_guess, h));
                if (remaining_guesses == 5) cout << hint_to_string(h) << " " << valid_answers_this_class.size() << endl;

                int result = can_solve_in(valid_answers_this_class, remaining_guesses - 1, current_guess, h, guesses_so_far, should_print /* should_print */, max_total_guesses - total_guess_count);
                guesses_so_far.pop_back();
                if (result == INT_MAX) {
                    // if (remaining_guesses == 4) {
                    //     stop = high_resolution_clock::now();
                    //     time_sec = duration_cast<microseconds>(stop - start).count() / 1000000.0;
                    // }
                    // if (!should_print && remaining_guesses == 4 && time_sec > 1.0) cout << last_guess << " " << hint_to_string(h) << " " << valid_answers.size() << " " << current_guess << " (XXX)" << endl;
                    return INT_MAX;
                }
                total_guess_count += result;
            }
            if (total_guess_count >= max_total_guesses) {
                return INT_MAX;
            }
        }
    }

    // if (remaining_guesses == 4) {
    //     stop = high_resolution_clock::now();
    //     time_sec = duration_cast<microseconds>(stop - start).count() / 1000000.0;
    // }

    // if (!should_print && remaining_guesses == 4 && time_sec > 1.0) cout << last_guess << " " << hint_to_string(h) << " " << valid_answers.size() << " " << current_guess << endl;

    return total_guess_count;
}

int can_solve_in_forced(vector<char*>& valid_answers, int remaining_guesses, char* force_next_guess, char* last_guess, hint h, vector<guess>& guesses_so_far, bool should_print, int max_total_guesses) {
#if 0
    if (remaining_guesses == 5) {
        vector<int> hint_class_counts;
        hint_class_counts.resize(num_hint_values);
        char* current_guess = force_next_guess;
        int total_guess_count = 0;

        for (hint h = num_hint_values - 1; h >= 0 && h < num_hint_values; h--) {
            vector<char*> valid_answers_this_class = get_valid_words(valid_answers, current_guess, h);
            if (valid_answers_this_class.size() > 0) {
                guesses_so_far.push_back(guess(current_guess, h));
                int result = can_solve_in_forced(valid_answers_this_class, remaining_guesses - 1, tokenized_words["HOTEL"], current_guess, h, guesses_so_far, true /* should_print */);
                guesses_so_far.pop_back();

                if (result == INT_MAX) {
                    return INT_MAX;
                }
                total_guess_count += result;
            }
        }
        return total_guess_count;
    }
#endif

    assert(valid_answers.size() > 0);

    if (remaining_guesses == 0) {
        return INT_MAX;
    }

    char* current_guess = force_next_guess;
    if (valid_answers.size() == 1) { // Special case, the forced guess gives no information so we have to avoid skipping it
        if (print_guesses) {
            guesses_so_far.push_back(guess(current_guess, valid_answers[0]));
            if (current_guess != valid_answers[0]) guesses_so_far.push_back(guess(valid_answers[0], valid_answers[0]));
            print_guesses(guesses_so_far);
            if (current_guess != valid_answers[0]) guesses_so_far.pop_back();
            guesses_so_far.pop_back();
        }
        return guesses_so_far.size() + (current_guess != valid_answers[0] ? 2 : 1);
    } else {
        return can_solve_with_next_guess(force_next_guess, valid_answers, remaining_guesses, last_guess, h, guesses_so_far, should_print, INT_MAX);
    }
}

vector<char*> rearrange_guesses(vector<char*>& valid_answers) {
    // Use letters in answers to optimize: all letters not occurring in answer words are equivalent and
    // will always give black/grey hints.
    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;
        }
    }

    // First filter out all guesses that are redundant because they are the same as another
    // guess except for the letters that are not present in the answer words.
    vector<char*> rearranged_guesses_1;
    {
        map<string, bool> guess_classes;
        for (int i = 0; i < valid_answers.size(); i++) {
            if (!is_duplicate_guess(guess_classes, letters_in_answers, valid_answers[i], true)) {
                rearranged_guesses_1.push_back(valid_answers[i]);
            }
        }
        for (int i = 0; i < guess_words.size(); i++) {
            if (!is_duplicate_guess(guess_classes, letters_in_answers, guess_words[i], false)) {
                rearranged_guesses_1.push_back(guess_words[i]);
            }
        }
    }

    // Now sort the guesses by max hint class size.
    vector<char*> rearranged_guesses_2;
    rearranged_guesses_2.resize(rearranged_guesses_1.size());
    {
        vector<int> max_hint_class_size;
        max_hint_class_size.resize(rearranged_guesses_1.size());
        for (int i = 0; i < rearranged_guesses_1.size(); i++) {
            memset(hint_class_counts, 0, sizeof(int) * num_hint_values);
            int max_count = 0;
            for (int m = 0; m < valid_answers.size(); m++) {
                hint hint = get_wordle_hints(rearranged_guesses_1[i], valid_answers[m]);
                if (++hint_class_counts[hint] > max_count) {
                    max_count = hint_class_counts[hint];
                }
            }
            max_hint_class_size[i] = max_count;
        }

        vector<size_t> idx(max_hint_class_size.size());
        iota(idx.begin(), idx.end(), 0);
        sort(idx.begin(), idx.end(), [&max_hint_class_size](size_t i, size_t j) {
            return max_hint_class_size[i] < max_hint_class_size[j];
        });

        for (int i = 0; i < rearranged_guesses_2.size(); i++) {
            rearranged_guesses_2[i] = rearranged_guesses_1[idx[i]];
        }
    }

    return rearranged_guesses_2;
}

int can_solve_in(vector<char*>& valid_answers, int remaining_guesses, char* last_guess, hint h, vector<guess>& guesses_so_far, bool should_print, int max_total_guesses) {
    assert(valid_answers.size() > 0);

    if (remaining_guesses == 0) {
        return INT_MAX;
    }

    if (remaining_guesses == 1 || valid_answers.size() == 1) {
        if (should_print && valid_answers.size() == 1) {
            if (last_guess == valid_answers[0]) {
                print_guesses(guesses_so_far);
            } else {
                guesses_so_far.push_back(guess(valid_answers[0], num_hint_values - 1 /* all green */));
                print_guesses(guesses_so_far);
                guesses_so_far.pop_back();
            }
        }
        if (valid_answers.size() == 1) {
            return guesses_so_far.size() + (last_guess == valid_answers[0] ? 0 : 1);
        } else {
            return INT_MAX;
        }
    }

    if (valid_answers.size() <= 2 /*remaining_guesses*/) { // Can just guess them all one by one
        if (should_print) for (int i = 0; i < valid_answers.size(); i++) {
            for (int j = 0; j <= i; j++) {
                guesses_so_far.push_back(guess(valid_answers[j], valid_answers[i]));
            }
            print_guesses(guesses_so_far);
            for (int j = 0; j <= i; j++) {
                guesses_so_far.pop_back();
            }
        }

        // sum i=0^(valid_answers.size()-1) (guesses_so_far.size() + i + 1)
        return guesses_so_far.size()*valid_answers.size() + valid_answers.size()*(valid_answers.size() + 1)/2;
    }

    if (valid_answers.size() * (guesses_so_far.size() + 2) - 1 >= max_total_guesses) {
        return INT_MAX;
    }

    bool is_valid_word;
    char* perfect_split_guess = get_perfect_split(valid_answers, is_valid_word);

    if (remaining_guesses == 2 || perfect_split_guess != NULL) {
        if (perfect_split_guess == NULL) {
            return INT_MAX;
        }

        if (should_print) for (int i = 0; i < valid_answers.size(); i++) {
            guesses_so_far.push_back(guess(perfect_split_guess, valid_answers[i]));
            if (perfect_split_guess != valid_answers[i]) {
                guesses_so_far.push_back(guess(valid_answers[i], num_hint_values - 1 /* all green */));
            }
            print_guesses(guesses_so_far);
            if (perfect_split_guess != valid_answers[i]) {
                guesses_so_far.pop_back();
            }
            guesses_so_far.pop_back();
        }

        return valid_answers.size() * (guesses_so_far.size() + 2)  -  (is_valid_word ? 1 : 0);
    }

    // Now things get more interesting. We must have at least 3 guesses left and must need at least 3.
    assert(remaining_guesses >= 3);

    vector<char*> rearranged_guesses = remaining_guesses == 5 ? guess_words : rearrange_guesses(valid_answers);

    // Compute upper bound on total guesses for each next guess, use that to lower max_total_guesses
    for (int i = 0; i < rearranged_guesses.size(); i++) {
        vector<int> hint_class_counts;
        hint_class_counts.resize(num_hint_values);

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

        // This upper bound assumes each hint class of size >= 3 will have a perfect split and resolve in two guesses
        int total_guess_count_upper_bound = 0;
        for (hint h = num_hint_values - 1; h >= 0 && h < num_hint_values; h--) {
            // None of these will be the bottleneck otherwise max_count <= 2 above would have caught it
            if (hint_class_counts[h] == 0) {
                ; // Do nothing
            } else if (h == num_hint_values - 1 /* all green */) {
                total_guess_count_upper_bound += guesses_so_far.size() + 1;
            } else if (hint_class_counts[h] == 1) {
                total_guess_count_upper_bound += guesses_so_far.size() + 2;
            } else if (hint_class_counts[h] == 2) {
                total_guess_count_upper_bound += (guesses_so_far.size() + 2) + (guesses_so_far.size() + 3);
            } else {
                // guess each word one by one: sum i=0^(valid_answers.size()-1) ((guesses_so_far.size()+1) + i + 1)
                total_guess_count_upper_bound += (guesses_so_far.size() + 1)*hint_class_counts[h] + hint_class_counts[h]*(hint_class_counts[h] + 1)/2;
            }
            if (total_guess_count_upper_bound >= max_total_guesses) {
                break;
            }
        }
        total_guess_count_upper_bound++; // Increase by 1 because we skip on equality
        if (total_guess_count_upper_bound < max_total_guesses) {
            max_total_guesses = total_guess_count_upper_bound;
        }
    }

    // if (remaining_guesses == 4) {
    //     cout << "Upper bound: " << max_total_guesses << endl;
    // }

    int best_result = max_total_guesses;
    char* best_guess = NULL;
    char* crate = tokenized_words["CRATE"];
    char* opsin = tokenized_words["OPSIN"];
    for (int i = 0; i < rearranged_guesses.size(); i++) {
        if (remaining_guesses == 4 && guesses_so_far[0].word == crate && h == string_to_hint("-y--y")) {
            if (rearranged_guesses[i] != opsin) {
                continue;
            }
        }
        if (remaining_guesses == 5) {
            cout << i << " " << rearranged_guesses[i] << endl;
            print_guess_file << i << " " << rearranged_guesses[i] << endl;
            reset_print_guesses();
        }
        int result = can_solve_with_next_guess(rearranged_guesses[i], valid_answers, remaining_guesses, last_guess, h, guesses_so_far, remaining_guesses == 5 ? true : false /* should_print */, best_result);
        if (result < best_result) {
            best_result = result;
            best_guess = rearranged_guesses[i];
            if (remaining_guesses == 5) {
                release_assert(total_print_guesses_count == answer_words.size());
                release_assert(best_result == total_print_guesses_guesses);
                cout << "Guess stats:" << endl;
                print_guess_file << "Guess stats:" << endl;
                for (int num_guesses = 1; num_guesses <= 6; num_guesses++) {
                    cout << num_guesses << ": " << print_guesses_stats[num_guesses] << endl;
                    print_guess_file << num_guesses << ": " << print_guesses_stats[num_guesses] << endl;
                }
                cout << "Total guesses: " << best_result << endl;
                print_guess_file << "Total guesses: " << best_result << endl;
            }
            // if (remaining_guesses == 4) {
            //     cout << "Best so far: " << best_guess << " " << best_result << endl;
            // }
        }
    }

    if (should_print && best_guess != NULL) {
        can_solve_with_next_guess(best_guess, valid_answers, remaining_guesses, last_guess, h, guesses_so_far, true /*should_print*/, best_result + 1);
    }

    return best_result;
}

void optimal_scan_normal() {
    vector<guess> guesses_so_far;

    int total_guesses = can_solve_in(answer_words, 5, NULL, 0, guesses_so_far, true /* should_print */, INT_MAX);
    for (int i = 0; i < answer_words.size(); i++) {
        if (words_seen.find(answer_words[i]) == words_seen.end()) {
            cout << "Missing: " << answer_words[i] << endl;
            release_assert(false);
        }
    }
    release_assert(total_print_guesses_count == answer_words.size());
    release_assert(total_guesses == total_print_guesses_guesses);
    cout << "Total guesses: " << total_guesses;
    return;

    ofstream of("depth_5.txt");
    auto start = high_resolution_clock::now();
    for (int i = 0; i < guess_words.size(); i++) {
        if (can_solve_in(answer_words, 5, guess_words[i], 0, guesses_so_far, true /* should_print */, INT_MAX)) {
            cout << guess_words[i] << " : solution of depth 5 exists" << endl;
            of << guess_words[i] << " : solution of depth 5 exists" << endl;
        } else {
            cout << guess_words[i] << " : NO SOLUTION OF DEPTH 5 EXISTS" << endl;
            of << guess_words[i] << " : NO SOLUTION OF DEPTH 5 EXISTS" << endl;
        }
    }
    auto stop = high_resolution_clock::now();
    cout << "Done, time: " << duration_cast<microseconds>(stop - start).count() / 1000000.0 << " s" << 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);

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

    // Precompute letter masks for guess words
    guess_words_letter_masks.resize(guess_words.size());
    for (int i = 0; i < guess_words.size(); i++) {
        int letter_mask = 0;
        for (int cidx = 0; cidx < word_length; cidx++) {
            letter_mask |= 1 << (guess_words[i][cidx] - 'A');
        }
        guess_words_letter_masks[i] = letter_mask;
    }

#if 0
    map<int, bool> letter_masks;
    for (int i = 0; i < guess_words.size(); i++) {
        int letter_mask = 0;
        for (int cidx = 0; cidx < word_length; cidx++) {
            letter_mask |= 1 << (guess_words[i][cidx] - 'A');
        }
        letter_masks[letter_mask] = true;
    }
    cout << letter_masks.size() << endl; // 7632

    map<int, bool> letter_masks_two;
    for (int i = 0; i < guess_words.size(); i++) {
        for (int j = 0; j < guess_words.size(); j++) {
            if (i == j) continue;
            int letter_mask = 0;
            for (int cidx = 0; cidx < word_length; cidx++) {
                letter_mask |= 1 << (guess_words[i][cidx] - 'A');
                letter_mask |= 1 << (guess_words[j][cidx] - 'A');
            }
            letter_masks_two[letter_mask] = true;
        }
    }
    cout << letter_masks_two.size() << endl; // 2086895

    vector<int> letters_two;
    for (auto iter = letter_masks_two.begin(); iter != letter_masks_two.end(); iter++) {
        letters_two.push_back(iter->first);
    }

    int* answer_letter_masks = new int[answer_words.size()];
    for (int i = 0; i < answer_words.size(); i++) {
        int letter_mask = 0;
        for (int cidx = 0; cidx < word_length; cidx++) {
            letter_mask |= 1 << (answer_words[i][cidx] - 'A');
        }
        answer_letter_masks[i] = letter_mask;
    }

    auto start = high_resolution_clock::now();

    for (int i = 0; i < letters_two.size(); i++) {
        int count = 0;
        for (int j = 0; j < answer_words.size(); j++) {
            if ((answer_letter_masks[j] & letters_two[i]) == 0) {
                count++;
                if (count >= 2) break;
            }
        }
        if (count <= 1) {
            cout << "3 guess solution MAY exist" << endl;
        }
    }

    auto stop = high_resolution_clock::now();
    cout << "Done, time: " << duration_cast<microseconds>(stop - start).count() / 1000000.0 << " s" << endl;

#endif

#if 0
    map<string, vector<char*>> answer_words_minus_one_letter;
    for (int i = 0; i < answer_words.size(); i++) {
        for (int cidx = 0; cidx < word_length; cidx++) {
            string word_str = answer_words[i];
            word_str[cidx] = '-';
            answer_words_minus_one_letter[word_str].push_back(answer_words[i]);
        }
    }


    map<string, vector<char*>> answer_words_minus_one_letter;
    for (int i = 0; i < answer_words.size(); i++) {
        for (int cidx = 0; cidx < word_length; cidx++) {
            string word_str = answer_words[i];
            word_str[cidx] = '-';
            answer_words_minus_one_letter[word_str].push_back(answer_words[i]);
        }
    }
    map<string, bool> constraint_map;
    for (int i = 0; i < answer_words.size(); i++) {
        for (int cidx = 0; cidx < word_length; cidx++) {
            string word_str = answer_words[i];
            word_str[cidx] = '-';
            vector<char*> word_list = answer_words_minus_one_letter[word_str];
            if (word_list.size() > 1 && word_list[0] == answer_words[i]) {
                string constraint;
                for (int j = 0; j < word_list.size(); j++) {
                    constraint += word_list[j][cidx];
                }
                constraint_map[constraint] = true;
            }
        }
    }
    vector<string> constraints;
    for (auto iter = constraint_map.begin(); iter != constraint_map.end(); iter++) {
        constraints.push_back(iter->first);
    }
    for (int i = 0; i < constraints.size(); i++) {
        cout << constraints[i] << endl;
    }

    map<string, vector<char*>> answer_words_minus_two_letters;
    for (int i = 0; i < answer_words.size(); i++) {
        for (int c = 0; c < word_length; c++) {
            for (int d = 0; d < word_length; d++) {
                string word_str = answer_words[i];
            word_str[cidx] = '-';
            answer_words_minus_one_letter[word_str].push_back(answer_words[i]);
        }
    }
    map<string, bool> constraint_map;
    for (int i = 0; i < answer_words.size(); i++) {
        for (int cidx = 0; cidx < word_length; cidx++) {
            string word_str = answer_words[i];
            word_str[cidx] = '-';
            vector<char*> word_list = answer_words_minus_one_letter[word_str];
            if (word_list.size() > 1 && word_list[0] == answer_words[i]) {
                string constraint;
                for (int j = 0; j < word_list.size(); j++) {
                    constraint += word_list[j][cidx];
                }
                constraint_map[constraint] = true;
            }
        }
    }
    vector<string> constraints;
    for (auto iter = constraint_map.begin(); iter != constraint_map.end(); iter++) {
        constraints.push_back(iter->first);
    }
    for (int i = 0; i < constraints.size(); i++) {
        cout << constraints[i] << endl;
    }

    int min_cover = -1;
    int min_cover_size = INT_MAX;
    for (int i = 0; i < 67108864 /*2^26*/; i++) {
        bool failed = false;
        for (int j = 0; j < constraints.size(); j++) {
            int satisfied_count = 0;
            for (int cidx = 0; cidx < constraints[j].length(); cidx++) {
                if (i & (1 << constraints[j][cidx] - 'A')) {
                    satisfied_count++;
                }
            }
            if (satisfied_count < constraints[j].length() - 1) { // All but 1 must be satisfied
                failed = true;
                break;
            }
        }
        if (failed) {
            continue;
        }

        int cover_size = 0;
        for (int letter_idx = 0; letter_idx < 26; letter_idx++) {
            if (i & (1 << letter_idx)) {
                cover_size++;
            }
        }
        if (cover_size < min_cover_size) {
            min_cover = i;
            min_cover_size = cover_size;
            cout << "Best cover found so far: ";
            for (int letter_idx = 0; letter_idx < 26; letter_idx++) {
                if (i & (1 << letter_idx)) {
                    cout << ((char)(letter_idx + 'A'));
                }
            }
            cout << " " << min_cover_size << endl;
        } else if (cover_size == min_cover_size) {
            min_cover = i;
            min_cover_size = cover_size;
            cout << "Same quality: ";
            for (int letter_idx = 0; letter_idx < 26; letter_idx++) {
                if (i & (1 << letter_idx)) {
                    cout << ((char)(letter_idx + 'A'));
                }
            }
            cout << " " << min_cover_size << endl;
        }
    }
#endif


    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. Optimal normal mode analysis" << endl;
        cout << "10. 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:
            optimal_scan_normal();
            break;
        case 10:
            return 0;
        default:
            cout << "Invalid option selected." << endl;
            break;
        }
    }
}