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.

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
    filename
    |> File.read!()
    |> String.split()
  end

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

  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}")
        word
    end
  end
end

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

# Entry point

# Set the random seed
Random.init
# 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"
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 log₂(N).

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

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

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

✎ Edit
Raw

Recommended Posts