Ruby implementation of a trie to use for a Letterpress/Wordfeud/Scrabble cheater.

gistfile1.rb

require 'benchmark'

class SlowTrie
  attr_accessor :word, :nodes

  def initialize
    @word, @nodes = false, {}
  end

  def <<(word)
    node = word.each_char.inject(self) { |node, char| node.nodes[char] ||= SlowTrie.new }
    node.word = true
  end

  def find(letters)
    recursive_find frequency_map(letters), ""
  end

  def recursive_find(used, word)
    words = nodes.reject { |c, v| used[c] == 0 }.map { |char, node|
      node.recursive_find(used.merge(char => used[char] - 1), word + char)
    }.flatten

    words << word if self.word
    words
  end

  def frequency_map(letters)
    letters.each_char.inject(Hash.new(0)) { |map, char| (map[char] += 1) && map }
  end
end

class Trie
  attr_accessor :word, :nodes, :used, :all

  def initialize
    @word, @nodes = false, {}
  end

  def <<(word)
    node = word.each_char.inject(self) { |node, char| node.nodes[char] ||= Trie.new }
    node.word = true
  end

  def find(letters)
    @all = []
    @used = frequency_map(letters)
    recursive_find self, ""
    @all
  end

  def recursive_find(root, word)
    nodes.reject { |c, v| root.used[c] == 0 }.each { |char, node|
      root.used[char] -= 1
      node.recursive_find(root, word + char)
      root.used[char] += 1
    }

    root.all << word if self.word
  end

  def frequency_map(letters)
    letters.each_char.inject(Hash.new(0)) { |map, char| (map[char] += 1) && map }
  end
end

def naive(letters, words)
  letters = Trie.new.frequency_map(letters)

  words.select { |word|
    word.each_char.inject(letters.clone) { |freq, char| 
      (freq[char] -= 1) < 0 ? break : freq
    } && word
  }.uniq
end

def group(letters, words)
  letters = Trie.new.frequency_map(letters)

  groups = words.group_by { |s| s[0] }

  groups.map { |char, group|
    next if letters[char] == 0

    group.select { |word|
      word.each_char.inject(letters.clone) { |freq, char| 
        (freq[char] -= 1) < 0 ? break : freq
      } && word
    }
  }.flatten.uniq
end

words = File.read("/usr/share/dict/words").split("\n").map(&:downcase)
trie = Trie.new

words.each do |word|
  trie << word
end

slowtrie = SlowTrie.new

words.each do |word|
 slowtrie << word
end


Benchmark.bm do |b|
  [
    "ovrkqlwislrecrtgmvpfprzey",
    "abcdefghifghijklmnopqrstuvxyz",
    "odidwocswkbafvydehsbiviez",
    "rtlyifebuzkxndovzyzodelap"
  ].each do |letters|
    puts "Benchmarking '#{letters}'"
    b.report("faster trie") { trie.find(letters).size }
    b.report("blog trie") { slowtrie.find(letters).size }
    b.report("naive") { naive(letters, words).size }
    b.report("group") { group(letters, words).size }
    puts
  end
end