Skip to content

Instantly share code, notes, and snippets.

@danielcorin
Last active September 7, 2015 05:22
Show Gist options
  • Save danielcorin/ab458ec544178fb86076 to your computer and use it in GitHub Desktop.
Save danielcorin/ab458ec544178fb86076 to your computer and use it in GitHub Desktop.
Elixir dictionary binary search
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment