Last active
May 4, 2019 05:07
Ruby implementation of a trie to use for a Letterpress/Wordfeud/Scrabble cheater.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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