Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Ruby implementation of a trie to use for a Letterpress/Wordfeud/Scrabble cheater.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment