Introduction

A close friend of mine streams games to me occasionally over Discord. Recently, she's been into a game called Birdigo. It's a roguelike word game where you spell words to score points. There's deckbuilding involved, as well as powerups that kind of remind me of Balatro. It's fun to watch. And I bought the game just because I like it too.

See, the thing about a game is that I want to win. And as a Computer Scientist, I can utilise specific algorithms and data structures to do just that. I'll try to make this post educational too. So, let's win at a game.

Extracting the word list

First, we need the word list straight from the game. This is as simple as getting AssetStudio and opening up defaultlocalgroup_scenes_main.bundle. Look for words_alpha as follows:

Here is the following file: words_alpha.txt. Do note I did convert the file. Originally, it was a DOS text file. I converted it to UNIX format. This will make it easier for my program later on.

Trie: The data structure for success

The best way to deal with games like Birdigo is to use a Trie data structure. To put it simply, it's a tree data structure where each letter is a node. As you traverse the tree, you will spell words. It's a compact way to store a dictionary of words and traverse it with Depth-first search (DFS). So construct a Trie with words from a dictionary and it will store every single word inside for easy lookup.

A visual explanation

Let's say I have a dictionary file that contains the following "words":

abc
abd
ba
bd
bdc

We can build a Trie out of this as follows:

In this diagram, I labelled the nodes that are endings to words as red. You can traverse the tree from the top to spell the words.

C++ Implementation

This data structure can be implemented in C++ rather easily by utilising nested std::maps. A class, trie, will store the map as a std::map<char, trie>. Here is the source code of a very basic Trie implementation:

• trie.hpp
• trie.cpp

To use this Trie implementation, here is an example program:

#include <iostream>
#include <string>
#include <stdio.h>

#include "trie.hpp"

using namespace std;

int main(int argc, char **argv) {
	if (argc < 2) {
		printf("usage: %s dict.txt\n", argv[0]);
		return 1;
	}

	trie dict;
	string line;
	bool result;
	dict.open(argv[1]);

	// Prompt the user to get words
	while (cout << "STR> " && getline(cin, line)) {
		result = dict.is_valid(line.c_str());

		if (result == true)
			cout << "is valid word" << endl;
		else
			cout << "not valid word" << endl;
	}

	return 0;
}

To use it, simply grab a dictionary of words (one word per line) as a text file. And use it as the first and only argument of the program. Then input your words and it will tell you whether they are valid or not.

UNIX> ./test words_alpha.txt
STR> bird
is valid word
STR> birj
not valid word

Do note that my Trie implementation auto-lowercases all words. This is irrelevant for the Birdigo word list since all letters are lowercase in that file anyway.

The way the Trie works is recursion. A Depth-first search that iterates the tree as well as the string characters simultaneously. When it hits the end of the string, it checks if that node has been marked as the end of a valid word. If so, it returns true. If not, or if the node doesn't exist, it returns false. I think it's elegant.

Solving Birdigo

Checking a valid word is not enough to solve Birdigo. We need an algorithm that, given a hand of words, will give us all possible words. Additionally, Birdigo has a wildcard character which can represent any letter. So we got our work cut out for us. Thankfully, we are working in C++ and have an efficient data structure. We can simply search through every possible permutation of a given hand and see if it exists in the Trie.

To start, I will make a few assumptions:

• Assume a function num_chars(str, target), which tells the number of chars target inside of string str.
• Assume when a letter is used, it is replaced with a space. Assume spaces are skipped in recursive checks.
• Assume that, along with letters, the wildcard * is a valid input and can be any of the 26 lowercase letters.

And now we are ready to start the algorithm. It has an initial step and a recursive step.

C++ Implementation

For some people, reading the code directly is much easier than reading things like it's a research paper. So here's the source to the recursion, as well as how to call it in main():

// ----------------------------------------------------------------------------
// Recursion                                                               {{{1
// ----------------------------------------------------------------------------

void process_hand(trie dict, string hand, set &words, string word) {
	unsigned int i, sz;
	char c, cc;
	map<char, trie> &letters = dict.get_letters();
	map<char, trie>::iterator ii;

	sz = hand.length();

	if (dict.is_word())
		words.insert(word);

	// If we have no more letters in our hand, we are done
	if (num_chars(hand.c_str(), ' ') == sz) {
		return;
	}

	// Go through every letter in the hand
	for (i = 0; i < sz; i++) {
		// Skip blanks
		if (hand[i] == ' ')
			continue;

		// Blank out the current letter
		c = hand[i];
		hand[i] = ' ';

		if (c == '*') {
			// Wildcards get special treatment
			for (cc = 'a'; cc <= 'z'; cc++) {
				ii = letters.find(cc);
				if (ii != letters.end()) {
					// NOTE: Could add "cc", but add wildcard to string instead
					process_hand(letters[cc], hand, words, word + c);
				}
			}
		}
		else {
			// Go to the next letter, if possible
			ii = letters.find(c);
			if (ii != letters.end()) {
				process_hand(letters[c], hand, words, word + c);
			}
		}

		// Revert
		hand[i] = c;
	}
}

void process_hand(trie dict, string hand, int limit = 0) {
	set<string> words;
	set<string>::iterator ii;

	// Unleash recursion like hell
	process_hand(dict, hand, words, "");

	/*
	 * If limit is 0, print all words. Otherwise, print words equal to "limit"
	 * in size.
	 */

	for (ii = words.begin(); ii != words.end(); ii++)
		if (limit == 0 || (*ii).length() == limit)
			cout << *ii << endl;
}

// ----------------------------------------------------------------------------
// Main Function                                                           {{{1
// ----------------------------------------------------------------------------

int main(...) {
	/* initialisation */

	/* set up trie as "dict" */
	/* read word as "line" and word limit as "limit" */

	process_hand(dict, line, limit);
}

As you can see, the wildcard adds significantly more complexity to the algorithm. This is especially true when you have 2 or 3 wildcards in a word at once. Thankfully, we are running this in C++, so we can easily go through millions of permutations in a reasonable time.

Website implementation

Now for something special. I wanted to port over the C++ version into JavaScript just so it can be accessible on any platform out there. So here you go. It'll be a bit slower but at least it'll run on anything, including your phone.

Make sure JavaScript is enabled in your browser. Additionally, the dictionary is loading in the background. By the time you hit this part of the blog post, the dictionary should have fully loaded. The apps will tell you if it hasn't been fully loaded just yet. Finally, note that Birdigo may update its dictionary at any time without me knowing. Check the build date of the game alongside the date of this blog post. I might update the word list occasionally.

App 1: Word Validity Checker

Let's say you don't want to cheat too badly. Instead, you just want to check if a word is valid or not. If so, this one is for you. Punch a word into the text box and hit the "Check!" button. It will tell you whether the word was valid or not. This does not account for wildcards.

App 2: Hand Solver

Now for the big one. Let's say you are looking at your hand and have no idea what words or combinations you have at your disposal. Well, if you give this tool your hand, it'll tell you every single possible word you can spell with it. You can even punch in wildcards. It will show the possible spots a wildcard can be applied correctly. If you want to target words of a specific size, set the Word Size parameter. Otherwise leave it blank or set it to 0 to display words of any length.

Source Code

Well, this is a really simple program but I decided to make a Git repository for it anyway. So here you go:

• birdigo-cheat Git Repo

It is only the C++ version. If you want the JavaScript implementation, simply look at the source of this webpage. The C++ version is CLI only. Clone the repo. Type make. And run either test or cheat. The former tests if a word is in the game's dictionary. The latter solves your hand by telling you all possible combinations.

Conclusion

One of my more technical blog posts. Unlike "Breaking Bongo Cat with Game Maker 8", where I explained a bit more of what's going on, I decided this time to just throw C++ code in the blog post and call it a day. I feel bad for that. Maybe I'll revisit this blog post and add in a better explanation in English on what is going on in the recursion step. In fact, if you look at the source code of this web page, you'll see comments of my attempt to do so.

At the very least, I like being able to use data structures and algorithms to solve problems. And now I'll consider Birdigo "solved". I guess I should add the disclaimer in here that it isn't really my intention to cheat, contrary to the dramatic opening of this blog post saying I want to win. I just wanted to write up a tool for the game. To me, that's fun. And my close friend has fun just playing the game. I encourage you to have fun in whatever way you feel is correct.