trie.rb

# usage:
# ruby trie.rb chatter

word = ARGV.first || ["chatter", "helio", "wonder", "gosli"].sample

class Node
  def add(chars)
    return if chars.empty?

    char = chars.shift
    children[char] ||= Node.new
    children[char].add(chars)
  end

  def autocomplete(start)
    start.
      chars.
      inject(self) { |node, char| node[char] }.
      flatten.
      map { |finish| start + finish }
  end

  protected

  def [](k)
    @children[k] or raise "doesn't seem to be a word :/"
  end

  def flatten
    children.flat_map do |char, child_node|
      fafa = child_node.flatten.map { |thingy| char + thingy }
      if fafa.any?
        fafa
      else
        [char]
      end
    end
  end

  private

  def children
    @children ||= {}
  end
end

require "benchmark"

root = nil

bm1 =
  Benchmark.realtime do
    words = File.read("/usr/share/dict/words").lines
    root = Node.new
    words.each do |word|
      root.add(word.chomp.split(""))
    end
  end

bm2 = Benchmark.realtime { puts root.autocomplete(word) }

puts "Building trie: #{bm1}s"
puts "Autocomplete: #{bm2}s"