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.

defmodule Words do
  @doc """
  Module for read a list of words from a text file.
  Contains functions for `split`ting the list and `find`ing a word
  def read(filename) do
    |> File.read!()
    |> String.split()

  def split(list) do
    mid = div(length(list), 2)
    Enum.split(list, mid)

  def find(word, words) do
    {first_half, second_half} = split(words)

    guess = (List.last(first_half) || List.first(second_half))
    |> String.downcase

    cond do
      word < guess ->
        IO.puts("Less than: #{guess}")
        find(word, first_half)
      word > guess ->
        IO.puts("Greater than: #{guess}")
        find(word, second_half)
      :else ->
        IO.puts("Found word: #{guess}")

defmodule Random do
  @doc """
  Module for choosing a psudo-random element from a list
  def init do
  def random_element(list) do
    Enum.at(list, :random.uniform(length(list)) - 1)

# Entry point

# Set the random seed
# Choose a random word
word = Random.random_element(words)
# Read the UNIX words dictionary
words = Words.read("/usr/share/dict/words")
IO.puts("Word is: #{word}")
# Perform the binary search to "guess" the word
Words.find(word, words)

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.