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