Word search

word_search.exs

defmodule Dictionary do
  @moduledoc """
  A Trie based approach to the dictionary.

  https://en.wikipedia.org/wiki/Trie
  """
  defstruct words: %{}

  @terminatior "."

  def new(), do: %Dictionary{}

  @spec add_word(Dictionary.t(), String.t()) :: Dictionary.t()
  def add_word(%Dictionary{words: words}, word) do
    %Dictionary{words: map_add(words, word)}
  end

  # Base case for add handler. If the word we're adding is only one letter long.
  # We add it, and a terminator as one of its children.
  defp map_add(words, <<letter::bytes-size(1)>>) do
    children = words |> Map.get(letter, %{}) |> Map.put(@terminatior, %{})
    Map.put(words, letter, children)
  end

  # Peel off the first letter of the word we're adding.
  # Add it to the map, then recursively add the rest of the letters as its children.
  defp map_add(words, <<letter::bytes-size(1)>> <> rest) do
    children = words |> Map.get(letter, %{}) |> map_add(rest)
    Map.put(words, letter, children)
  end

  @spec search(Dictionary.t(), String.t()) :: boolean()
  def search(%Dictionary{words: words}, word), do: map_search(words, word)

  # Base handler, we can't find anything if there are no words in the dictionary.
  defp map_search(letters, _word) when map_size(letters) == 0, do: false

  # If we're searching for an empty string, check if there's a terminator in the
  # current layer.
  defp map_search(letters, "") do
    Map.has_key?(letters, @terminatior)
  end

  # If the letter we're checking for is a wildcard, we have to check the children
  # of all the nodes in the current layer.
  defp map_search(letters, "." <> rest) do
    Enum.reduce_while(letters, false, fn {_letter, children}, _acc ->
      case map_search(children, rest) do
        true -> {:halt, true}
        _ -> {:cont, false}
      end
    end)
  end

  # Finallly, we sure the letter we're looking for exists in the current layer.
  defp map_search(letters, <<letter::bytes-size(1)>> <> rest) do
    children = Map.get(letters, letter, nil)

    case children do
      nil -> false
      _ -> map_search(children, rest)
    end
  end
end

IO.puts("Searching 'hello' -> #{Dictionary.search(Dictionary.new(), "hello")}")

dict =
  Dictionary.new()
  |> Dictionary.add_word("bad")
  |> Dictionary.add_word("mad")
  |> Dictionary.add_word("dad")

IO.puts("Searching 'pad' -> #{Dictionary.search(dict, "pad")}")
IO.puts("Searching 'bad' -> #{Dictionary.search(dict, "bad")}")
IO.puts("Searching '.ad' -> #{Dictionary.search(dict, ".ad")}")
IO.puts("Searching 'b..' -> #{Dictionary.search(dict, "b..")}")