Creating a WORDLE solver in C++

Wordle is a new exciting and interesting game that was recently developed by some dude (don’t know his name- Alfred Butts created scrabble and nobody cares). Getting back into hammering some C++ in graduate school, I decided to piece together some primitive solver for the Game. Nothing too advanced involving optimization theory or fancy math- Just common sense coding with adherence (not too strict please :)) to C++ standards.

If you’re unfamiliar with the rules of wordle, please refresh your memory here https://www.theverge.com/22892044/wordle-free-game-online-how-to-puzzle.

Now to the dirty work. Before head right on to building the not-so primitive solver, we notice first of all that the damn game is 100% dependent on the english dictionary. The dictionary is needed to validate word guesses, and since the computer is incapable of coming up with word guesses, a dictionary with some form of random selection is useful here also. Now the go-to solution in the holy year of 2022 would be to call some fancy API- but that won’t be too much fun, would it?

First port of call, the dictionary. Finding a dictionary online wasn’t too hard. I found one right here on this github page https://github.com/benjihillard/English-Dictionary-Database. The database here was in csv format, and so i converted it online to to an sqlite database. Now we have an sqlite database of the dictionary, so we can begin some C++.

in order to interact with an sqlite database in C++, you need some library, and I found one that works just fine(thanks to stackoverflow). https://www.sqlite.org. The sqlite library is really lightweight and very straightforward in it’s usage if you’re slightly familiar with the C syntax. The compilation guides are clearly written in the docs so I’ll dive straight into the code.

One of the obvious things from reading the sqlite docs that you notice is the deep dive straight into raw pointers. But I’m trying to write the C++ way, so wrapping the pointer in a concrete class seems like a good choice at this point.

class sqlite3_wrapper
    {
    public:
        sqlite3 *db;
        sqlite3_wrapper() {}
        ~sqlite3_wrapper()
        {
            if (db != nullptr)
                sqlite3_close(db);
        }
    };

The close db command in the destructor is the sole reason for wrapping this c pointer-filled struct. No point worrying about memory leaks as we’re covered by C++ RAII. Covering up the only trace of C- code, we hammer on to the C++ class encapsulating this dictionary bazaar.

I call the class Wordbot, and for now, it’s only job would be to check if a word is valid

class Wordbot final
{
private:
    static int search_callback(void *search_state, int argc, char **argv, char **az_col_name);
public:
    enum class search_result
    {
        NOT_FOUND,
        VALID,
        ERROR
    };
    // C style struct with lack of constructors and destructors require this wrapping
    class sqlite3_wrapper
    {
    public:
        sqlite3 *db;
        sqlite3_wrapper() {}
        ~sqlite3_wrapper()
        {
            if (db != nullptr)
                sqlite3_close(db);
        }
    };

private:
    std::unique_ptr<sqlite3_wrapper> db3{new sqlite3_wrapper}; 
    std::string db_file{"C:/Users/USER/Documents/cpp/dict.db"};
    char *err_msg;

public:
    Wordbot(); //default constructor
    Wordbot(std::string autre_db);
    const char *errmsg();
    search_result check(std::string word);
    Wordbot(const Wordbot &); // Copy Constructor
};

The code above is a nice little concrete class with all the basics and the declaration of the checker function. The definition of the checker function is where some good ole sql comes in. If you’re unfamiliar with some sql it’s fine

Wordbot::Wordbot(std::string autre_db) : db_file{autre_db}
{
    if (sqlite3_open(db_file.c_str(), &db3->db))
        state = db_state::VALID;
}

const char *Wordbot::errmsg()
{
    return err_msg;
}

Wordbot::search_result Wordbot::check(std::string word)
{
    search_result res{search_result::NOT_FOUND};

    std::string query{"SELECT distinct word FROM 'english dictionary' where upper(word) = upper('" + word + "')"};
    if (sqlite3_exec(db3->db, query.c_str(), search_callback, &res, &err_msg) != SQLITE_OK)
        return search_result::ERROR;

    return res;
}

The constructor and search result function are defined, but the call_back function which handles the result isn’t yet given. there’s nothing special about the format of the callback function, as it completely specified by sqlite.

int Wordbot::search_callback(void *search_state, int argc, char **argv, char **az_col_name)
{
    search_result *res = static_cast<search_result *>(search_state);
    if (argc >= 1) //The word was found so one row exists
        *res = search_result::VALID;
    return 0;
}

This might seem like a lot of time on database coding for a wordle game, but it’s worth it, as the rest of the solver relies on simple clever sqlite back-and-forth.

The last part of the database interaction involves the step of the game where you have to come up with possible word after playing a round

In the round shown above. ‘R’ is clearly in the right position and the correct word further contains ‘UE’ . the challenge first of all is to think up a quick sqlite command to fetch words that might be our next guesses.

The most obvious answer would be to search for five letter words starting with ‘R’ and containing ‘UE’ also. The first part is easily done but the second part is next to impossible with Sqlite. So the possible options are to search for words that fit the following

1. RU_ _ E
2. R_U_E
3. R_ _UE
4. RE_ _ U
5. R_E_U
6. R_ _EU

but typing this seems like quite a lot of work, and sqlite has a clever breakdown where we can write

1. R%U%E
2. R%E%U

the ‘%’ tells sqlite that there might be one or more characters in between. and now we have gone from 6 verbose combinations to two seemingly simple things. But before i deviate too much into DB call optimizations, i’ll just set down my first go-to answer

Given the letters contained (both correctly placed and not) we simply find all the possible permutations of the positions and then filter the results based on correct position placements. so for the example above, we would have

1. %R%E%U%
2. %R%U%E%
3. %E%R%U%
4. %E%U%R%
5. %U%R%E%
6. %U%E%R%

And then finally filter out and select only word starting with R. Finally we have a two step process

1. Permuatate the valid letters and sandwich ‘%’ in between
2. filter out the possible words based on correct letters

std::vector<std::string> Wordbot::get_ran_word(std::string letters, std::string corrigeux)
{
    std::vector<std::string> res{};

    std::vector<std::string> perms{};
    permute(letters, 0, letters.size() - 1, perms);

    std::string query = "select lower(word) from (select DISTINCT word from 'english dictionary' where length(word) = 5 and(";
    std::for_each(perms.begin(), perms.end() - 1, [&](std::string &s)
                  {ins_perc(s);
   query +=     " lower(word) like '" +  s + "' or \n "; });
    ins_perc(perms[perms.size() - 1]);
    query += "lower(word) like '" + perms[perms.size() - 1] + "' )) where word like '" + corrigeux + "' ORDER BY RANDOM()";


    if (sqlite3_exec(db3->db, query.c_str(), rand_callback, &res, &err_msg) != SQLITE_OK)
    {
        res = {};
        std::cout << err_msg << std::endl;
    }

    return res;
}

int rand_callback(void *s_res, int argc, char **argv, char **az_col_name)
{
    std::vector<std::string> *res = static_cast<std::vector<std::string> *>(s_res);
    for (int i = 0; i < argc; i++)
    {
        res->push_back(std::string{argv[i]});
    }
    return 0;
}

The inputs to the function are

1. the valid letters
2. The corrected placement (which for our example would be “R _ _ _ _”)

And the result is just a list of valid strings

NB: i used a static cast as this is just a re-validation of a voided pointer. Also, once again, this is probably not the most efficient solution

And that’s it for all DB voodoo, and we can test this code to see some results

std::cout << " ------------- STARTING DEBUG -------------" << std::endl;
    Wordbot bot{};
    switch (bot.check("churlish"))
    {
    case Wordbot::search_result::VALID:
        std::cout << "VALID" << std::endl;
        break;
    case Wordbot::search_result::NOT_FOUND:
        std::cout << "INVALID WORD- NOT FOUND" << std::endl;
        break;
    default:
        break;
    }

    std::vector<std::string> test_rand = bot.get_ran_word("rue", "r____");
    if (!test_rand.empty())
        std::for_each(test_rand.begin(), test_rand.end(), [](std::string &s)
                      { std::cout << s << std::endl; });

------------- STARTING DEBUG -------------
VALID
remue
runer
ruled
ruffe
reume
reule
redub
rogue
rugae
recur
ruler
refut
rouse

Now, finally we jump into some wordle! The wordle class is pretty simple. We have an objective Word and given any guess, we tell the player the correct letters with respect to position, the wrong letters and the misplaced letters.

enum class letter_state
{
    CORRECT,
    WRONG,
    CONTAINED // For misplaced letters
};


class Wordle
{
private:
    std::string answer;
    std::map<char, bool> ans_set;
    Wordle(){};

public:
    int trials;
    Wordle(std::string ans, int tries);
    int word_len() { return answer.length(); }
    std::vector<letter_state> check_guess(std::string guess);
};

The implementations are then given below as

Wordle::Wordle(std::string ans, int tries)
{
    answer = ans;
    trials = tries;
    std::for_each(answer.begin(), answer.end(), [&](char &s)
                  { ans_set[s] = true; });
}

std::vector<letter_state> Wordle::check_guess(std::string guess)
{
    if (guess.length() != answer.length())
    {
        std::cout << "Length Mismatch";
        return std::vector<letter_state>{};
    }

    std::vector<letter_state> res{};
    int i = 0;
    std::for_each(guess.begin(), guess.end(), [&](char &s)
                  {
            if(guess[i] == answer[i])
                res.push_back(letter_state::CORRECT);
            else if (ans_set[s])
                res.push_back(letter_state::CONTAINED);
            else
                res.push_back(letter_state::WRONG);
            i++; });
    return res;
}

NB: I will std::for_each a whole lot

Finally, the wordle solver itself. Having played the game here’s a few things the solver will need to keep track of

1. Wrong letters never to be used in the guessed words
2. wrong positions for contained letters
3. Right and correctly placed letters

A simple map is sufficient to hold the wrong letters, but the wrongly placed letters would require a simple trick of concatenating the letter and position as the keys for a map also. This subsequently means updating these hash maps and filtering out bad guesses from the dictionary

class Player
{
private:
    std::map<char, bool> bad_letters{};
    std::map<std::string, bool> bad_positions{};
    std::vector<letter_state> last_res{};
    int trials;
    Wordle wordle;
    int trys{0};

    bool check_invalids(std::string &s);
    Player() = delete; // No default constructor

public:
    std::string last_guess;
    Wordbot bot;
    Player(Wordbot &mybot, Wordle &wordler) : bot{mybot}, trials{wordler.trials}, wordle{wordler} {}
    void play();
    void update_bad_letters();
    std::string return_first_valid(std::vector<std::string> &word_guesses);
    std::string remake_guess();
    void print_out();
};

The Update bad_letters seems like a fairly straightforward function

void Player::update_bad_letters()
{
    for (int i = 0; i < last_guess.size(); i++)
    {
        if (last_res[i] == letter_state::WRONG)
            bad_letters[last_guess[i]] = true;
        if (last_res[i] == letter_state::CONTAINED)
            bad_positions[make_str(last_guess[i], i)] = true;
    }
}

std::string make_str(char c, int pos){
    return std::string{c} +  std::to_string(pos);
}

Next is the guess validator which checks a given guess and sees if the letters are not in the “bad” box and the placement doesn’t coincide with previously wrong placement

bool Player::check_invalids(std::string &s)
{

    for (int i = 0; i < s.length(); i++)
    {
        if (bad_letters[s[i]] || bad_positions[make_str(s[i], i)])
            return false;
    }
    std::cout << s << std::endl;
    return true;
}

The peultimate part is the guess maker and the filter which uses this checker. Now the filter below just returns the first valid word. As i said, no optimizations, just quick common sense since the DB calls are randomly sorted

std::string Player::return_first_valid(std::vector<std::string> &word_guesses)
{
    for (int j = 0; j < word_guesses.size(); j++)
    {
        if (check_invalids(word_guesses[j]))
            return word_guesses[j];
    }
    return last_guess; // Loop for no solutions
}



std::string Player::remake_guess()
{
    std::map<char, bool> used{}; // words used
    std::string corrigeux{"_____"};
    std::string contained = last_res.size() == 0 ? std::string{"aie"} : ""; // use aie at the start of play
    for (int i = 0; i < last_res.size(); i++)
    {
        switch (last_res[i])
        {
        case letter_state::CORRECT:
            corrigeux[i] = last_guess[i];
            if (!used[last_guess[i]])
                contained += last_guess[i];
            break;
        case letter_state::CONTAINED:
            if (!used[last_guess[i]])
                contained += last_guess[i];
            break;
        default:
            break;
        }
        used[last_guess[i]] = true;
    }

    std::cout << contained << " | " << corrigeux << std::endl;
    std::vector<std::string> word_guesses = bot.get_ran_word(contained, corrigeux);
    return return_first_valid(word_guesses);
}

finally the play function just calls these other auxilliary functions in good order to make a guess, filter and get the best guess and then send to to the Wordle class to grade

void Player::play()
{
    if (trys >= trials)
        return;
    if (trys <= trials)
    {
        ++trys;
        last_guess = remake_guess();
        last_res = wordle.check_guess(last_guess);
        update_bad_letters();
        print_out();
    }
}

Testing all the code together with the simple test below gives

int main()
{
    std::cout << " ------------- STARTING DEBUG -------------" << std::endl;
    Wordbot bot{};

    Wordle w{Wordle("aloft", 5)};

    Player daniel = Player(bot,w);
    daniel.play();
    daniel.play();
    daniel.play();
    daniel.play();
    daniel.play();


 

}

------------- STARTING DEBUG -------------
aie | _____
alike
 <========== Trial 1
a -> correct
l -> correct
i -> wrong
k -> wrong
e -> wrong
al | al___
allay
 <========== Trial 2
a -> correct
l -> correct
l -> Contained
a -> Contained
y -> wrong
al | al___
algor
 <========== Trial 3
a -> correct
l -> correct
g -> wrong
o -> Contained
r -> wrong
alo | al___
aloud
 <========== Trial 4
a -> correct
l -> correct
o -> correct
u -> wrong
d -> wrong
alo | alo__
aloft
 <========== Trial 5
a -> correct
l -> correct
o -> correct
f -> correct
t -> correct

Yay, it works! here’s the git link ttps://github.com/igbokwedaniel/wordle_solver.git

PS: Forgive all typos