Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Word search
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..")}")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.