Writing a Word Game in Elixir: Spelling Bee

Wordle might be the best thing to have come out of the pandemic, and my engineering brain latched onto it immediately after playing it. We can tackle an Elixir implementation of that at some point, but first I wanted to demonstrate a couple concepts for any budding Elixir programmers by showcasing a different, but thoroughly enjoyable game: Spelling Bee (available on the New York Times site).

Spelling Bee: an elegant and satisfying word game

Spelling Bee is a game of anagrams, where you are limited to using only the letters displayed and the solutions must contain the letter in the center. There are multiple definitions of “anagram”, but this game does not require strict adherence. In other words, you can re-use letters as much as you’d like. (This is different from a “perfect” anagram, which is a reshuffling of letters with no additional repeats).

Take a moment to think through how you might come up with a list of solutions for a puzzle such as this.

You might reach for some kind of permutation-based solution where all possible combinations are generated and any non-words eliminated, but that would be a headache: there’s no upper-bound on how large the words can get and it would be terribly inefficient because English words represent only a small fraction of all possible permutations. Nope.

You might reach for a regular expression to validate whether or not a candidate word met the criteria of the game. That would work, but it might be tricky to write. There is a more efficient way to do this.

A prerequisite is to have a decent word list — finding a good one could the subject of a separate article, but assuming we have one, one of the simplest ways to pluck out valid solutions for any given puzzle is traverse this list and evaluate whether each word is a possible solution to the puzzle. We should only need to traverse the word list once, and if we are really being diligent, we should be able to bail on evaluating any words as soon as we hit an invalid letter.

Think of this as painting a wall: we only want to paint as much of the wordlist as necessary to solve the problem. We do not want multiple coats of paint here. You can think of it as an O(n) problem: fight hard to keep it as simple as possible without ballooning into anything more complex.

The primary tool I want to introduce for solving this problem is Elixir’s MapSet: it represents a mathematical set of unique unordered items. Too often I see code that improperly uses lists to store sets. Remember: lists are ordered, and there is no guarantee that its members are unique. We’d rather not have to traverse a list to know if a particular thing is a member. So MapSet is the power tool for helping us solve this game.

Consider this code snippet which gives us a set of all the letters available for a given puzzle:

"lobceit" 
|> String.graphemes()
|> MapSet.new()
#MapSet<["b", "c", "e", "i", "l", "o", "t"]>

We’ll have to talk about String.graphemes/1 in an article devoted to strings and encodings, but for now you can think of it as a way of splitting a string into its constituent letters (in a way that’s safe for unicode). Once we have a set, we can easily evaluate whether a letter is a member or not, e.g. MapSet.member?(my_set, "x")

The next trick worth mentioning is how Elixir can deconstruct strings — they act a lot like lists, so we can use pattern matching to grab one letter at a time. The trick here is to use the ::binary-size(1) to restrict the match to a single UTF8 character (i.e. a letter):

word = "beetle"
<<letter::binary-size(1)>> <> tail = word
# letter is "b"
# tail is "eetle"

With these two tools, we can easily parse words one letter at a time and evaluate whether or not they are viable candidates. As soon as MapSet.member?/2 returns false, we know that word is no good and we can move on to the next word.

The final bit of code-finesse I want to talk about is how to deal with a complex chain of conditionals. To find solutions to a Spelling Bee puzzle, we need a word list. A valid word list must exist at a certain path, and it must not be a directory. Although it would work to jam something like File.exists?(wordlist) && !File.dir?(wordlist) together, that does not make for very readable code, and it only gets worse the more conditions you add. One of the most important constructs in Elixir to help with keeping your code elegant and readable is the special form with . With a little prep work, you can use it to chain together multiple conditions and provide a useful error message if any of them are not met.

If we add a couple functions like this:

defp wordlist_exists(wordlist) do
  case File.exists?(wordlist) do
    true -> :ok
    false -> {:error, "Wordlist #{inspect(wordlist)} does not exist"}
  end
end
defp wordlist_not_dir(wordlist) do
  case File.dir?(wordlist) do
    true -> {:error, "The wordlist at #{inspect(wordlist)} is a directory"}
    false -> :ok
  end
end

We can provide meaningful error messages and better describe our code. It can get wrapped up into a with statement like this:

with :ok <- wordlist_exists(wordlist),
     :ok <- wordlist_not_dir(wordlist) do
        # Do something with vetted wordlist
end

This really helps keep the code readable and extensible. When you put this all together, you end up with a simple Elixir module that can solve your Spelling Bee puzzles. Don’t forget the handy trick to set iex so it doesn’t clip the responses by using IEx.configure/1 :

iex> IEx.configure(inspect: [limit: :infinity, printable_limit: :infinity])
iex> SpellingBee.solutions("lobteic", "b", min_length: 4)
{:ok,
  ["tobe", "titbit", "tibi", "tibet", "tebet", "oboe", "obit", "lobe", "libet", "libel", "elbe", "collectible", "cocobolo", "cobol", "coble", "cobble", "ceibo", "bottle", "botte", "bootee", "boot", "boole", "booboo", "boob", "bolti", "bolt", "bolo", "boll", "bolete", "bole", "boil", "bocce", "bobble", "blot", "bloc", "blob", "bleb", "bitt", "bito", "bite", "biotitic", "biotite", "biotic", "biol", "billet", "bill", "bile", "bilbo", "bice", "bibliotic", "bible", "betel", "bete", "belt", "bello", "belli", "belle", "bell", "belittle", "belie", "beetle", "beet"]}

Take a look at the source code on Github. In the future we can examine the other side of this game: how to generate puzzles instead of just solving them.

Until then, happy coding!