// css

Elixir binary search

A few days ago, I saw a 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"

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

Given that the UNIX dictionary has 235,886 words

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

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

O(log₂(235886)) ≈ O(17.85)

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