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.
$ 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.