A few days ago, I saw the Guess my word game on the front page of Hacker News. Before spoiling the fun for myself by checking out the comments, I decided to try my hand at writing a solution in Elixir. Afterwards, I generalized the code to choose its own word from the UNIX dictionary and then “guess” it, applying a binary search based on the feedback of whether each guess was alphabetically greater or less than the word itself.

Example output:

$ iex words.exs 

Word is: barruly
Less than: modificatory
Less than: eagerness
Less than: canari
Greater than: asthenosphere
Less than: bifoliolate
Greater than: barad
Less than: beguilement
Less than: batzen
Less than: basaltic
Greater than: barmbrack
Greater than: barreler
Less than: bartholomew
Greater than: barrio
Found word: barruly

Something I encountered worth mentioning is how Elixir compares strings that have different capitalization. Capital letters are “less than” their lower case versions:

iex> "B" < "b"
    true

Knowing this, we use String.downcase in our implementation to avoid comparison issues in the binary search. Binary search has a time complexity of:

Given that the UNIX dictionary has 235,886 words

$ cat /usr/share/dict/words | wc -l
235886

the fact the our algorithm took 14 steps to “guess” the word is plausible given

which is the number of steps we would expect it to take to guess our word.