This is the story of a bug I never saw coming, which manifested in a code path I never imagined or planned for. Certainly, good testing would have shown this earlier, but I don’t have test coverage of this module. I wanted to but I still have more to learn, and that’s a lesson for a future time.
Unexpectedly
In my Wordle clone Subtle, I have a module Possibles that takes the current state of the game and generates a list of words that could possibly be correct answers. Passing :simple creates a very simple regex to filter the dictionary, while :intermediate is much smarter – essentially a cheat mode.
@spec possible_words(Game, :simple | :intermediate) :: list
def possible_words(game, guidance \\ :simple) do
The bug manifested itself with the following guesses and resulted in an empty list returned from possible_words/2.
While playing, there is an option to give up, and the game will tell you the answer. In this case the answer to the game was omega. I quit the game, hopped into IEx, and set out to determine what was going on. (I’ve removed longer output that isn’t important.)
iex> g = Game.new(answer: "omega")
%Subtle.Game{
verify_guesses: true,
puzzle: %Subtle.Puzzle{
state: :playing,
word_length: 5,
max_guesses: 6,
answer: "omega",
guesses: []
},
message: "Guess a word."
}
iex> {:ok, party} = Game.make_guess(g, "party")
...
iex> Possibles.possible_words(party, :intermediate)
["aback", "abase", "abide", "abled", "abode", "above", "abuse", "adage",
"admin", "adobe", "affix", "afoul", "again", "agile", "aging", "aglow",
"ahead", "aisle", "album", "algae", "alibi", "alien", "align", "alike",
"alive", "allow", "alone", "along", "aloof", "aloud", "amass", "amaze",
"amble", "amend", "amiss", "among", "amuse", "angel", "angle", "anime",
"ankle", "annex", "annul", "anode", "anvil", "ashen", "aside", "askew",
"audio", "avail", ...]
iex> {:ok, clans} = Game.make_guess(party, "clans")
...
iex> Possibles.possible_words(clans, :intermediate)
["abide", "abode", "above", "adobe", "affix", "ahead", "audio", "avoid",
"awoke", "axiom", "dogma", "kebab", "media", "omega", "vodka"]
iex> {:ok, again} = Game.make_guess(clans, "again")
...
iex> Possibles.possible_words(again, :intermediate)
[]
Everything worked until we guessed again. Looking at the generated regex, I immediately noticed the problem.
iex)> Possibles.guess_regex(again, :intermediate)
~r/(?=.*a)(?=.*g)[^acilnprsty][^acgilnprsty][^acilnprsty][^acilnprsty][^acilnprsty]/
The answer to our game is omega and this regex excludes the letter a in all letter slots. At this point in the game a should only be excluded from the first three letter slots.
Well, How Did We Get Here?
Looking further into the data we can see the map generated to summarize the results of the guesses. In this case we can see that a should not appear in the first three letter slots, but it is also being marked as a bad letter, which means it shouldn’t appear in any answer. This is the source of the problem.
iex> again_map = Possibles.process_guesses(again)
%{
bad: ["a", "c", "i", "l", "n", "p", "r", "s", "t", "y"],
good: %{},
not_here: %{1 => ["a"], 2 => ["a", "g"], 3 => ["a"]}
}
The Fix is In
The previous version of process_guesses/1 looked like this below. I assumed it worked – I know, scary – because I made sure good letters aren’t in the bad letter list.
def process_guesses(game) do
Enum.reduce(
game.puzzle.guesses,
%{bad: [], good: %{}, not_here: %{}},
fn guess, map ->
Map.merge(map, process_guess(guess), &merge_guess/3)
end)
end
The solution is to remove any letters contained in the :not_here map from the :bad list. It’s super simple and it works.
def process_guesses(game) do
guess_map =
Enum.reduce(
game.puzzle.guesses,
%{bad: [], good: %{}, not_here: %{}},
fn guess, map ->
Map.merge(map, process_guess(guess), &merge_guess/3)
end)
# Remove every letter in :not_here map from :bad list.
remove_not_here_from_bad(guess_map)
end
defp remove_not_here_from_bad(guess_map) do
not_heres =
guess_map.not_here
|> Map.values()
|> List.flatten()
|> Enum.uniq()
filtered_bad = Enum.reject(guess_map.bad, & &1 in not_heres)
%{guess_map | bad: filtered_bad}
end
How About Now?
iex> r Possibles
{:reloaded, [Subtle.Possibles]}
iex> Possibles.guess_regex(again, :intermediate)
~r/(?=.*a)(?=.*g)[^acilnprsty][^acgilnprsty][^acilnprsty][^cilnprsty][^cilnprsty]/
iex> Possibles.possible_words(again, :intermediate)
["dogma", "omega"]
Now we see that a is allowed in the last two letter slots and that dogma and omega are possible answers. Perfect!
The Future
I mentioned at the beginning of this post that testing would have revealed this bug to me earlier. I also mentioned that I don’t have testing for this module because I need to learn more.
Currently an Agent holds the dictionary for the game so that it only needs to load and process once.
defmodule Subtle.PuzzleDictionary do
use Agent
# Fire up the Agent and store the dictionary map in it
@doc false
def start_link(_opts) do
Agent.start_link(
fn -> dictionary_map_from_disk() end,
name: __MODULE__)
end
...
I currently don’t know how to test this module (and really the Possibles module) because of the interaction of testing with the start_link. My attempt to write some tests kept resulting in errors and, after several different versions of the tests, I decided to shelve them so I could continue. This is on my list of things to learn and rectify.
Conclusions
- I’m getting much more comfortable using IEx to spelunk into code and data.
- I need to learn ExUnit beyond the beginner stage so I can test all my modules.
- This bug would most likely have been caught with better testing. When writing the code I thought I’d covered all the possibile paths but clearly missed an important case.
- This is fun!