Created
December 4, 2015 15:44
-
-
Save halogenandtoast/118ab9186fe837fd5a14 to your computer and use it in GitHub Desktop.
This file contains hidden or 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 TrieBuilder | |
| def from_words(words) | |
| TrieNode.new("").tap do |trie| | |
| words.each { |word| trie.push_word(word) } | |
| end | |
| end | |
| end | |
| class TrieNode | |
| include Enumerable | |
| attr_reader :label, :children | |
| def initialize(label) | |
| @label = label | |
| @children = {} | |
| end | |
| def push_word(word) | |
| word.downcase.each_char.inject(self) do |branch, char| | |
| branch.push char | |
| end | |
| end | |
| def words(&block) | |
| traverse @children | |
| end | |
| protected | |
| def push(letter) | |
| @children[letter] ||= TrieNode.new(@label + letter) | |
| end | |
| private | |
| def traverse(hash) | |
| hash.values.map { |node| traverse_node node }.flatten | |
| end | |
| def traverse_node(node) | |
| if node.children.empty? | |
| [node.label] | |
| else | |
| traverse node.children | |
| end | |
| end | |
| end | |
| class SquareSolver | |
| def initialize(size, dictionary = "/usr/share/dict/words") | |
| words = File.open(dictionary).readlines.map(&:chomp) | |
| @size = size | |
| @words = words.select { |word| word.length == @size }.shuffle | |
| @trie = TrieBuilder.new.from_words(@words) | |
| end | |
| def solve | |
| recurse([], 0) | |
| end | |
| private | |
| def recurse(square, depth) | |
| if depth == @size | |
| square | |
| else | |
| find_next_word(square, depth) | |
| end | |
| end | |
| def find_next_word(square, depth) | |
| words = words_for_depth(square, depth) | |
| find_word_that_fits_square(words, square, depth) | |
| end | |
| def find_word_that_fits_square(words, square, depth) | |
| words.lazy.map { |word| recurse(square + [word], depth + 1) }. | |
| find { |step| step } | |
| end | |
| def words_for_depth(square, depth) | |
| prefix = get_prefix(square, depth) | |
| find_branch(prefix).words | |
| end | |
| def find_branch(prefix) | |
| prefix.each_char.inject(@trie) do |branch, char| | |
| branch.children[char] || TrieNode.new("") | |
| end | |
| end | |
| def get_prefix(square, depth) | |
| square.map { |word| word[depth] }.join | |
| end | |
| end | |
| puts Benchmark.measure { | |
| puts *SquareSolver.new(ARGV[0].to_i).solve | |
| } |
This file contains hidden or 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
| class SquareSolver | |
| def initialize size, dictionary = "/usr/share/dict/words" | |
| @size = size | |
| @words = File.open(dictionary).readlines.map(&:chomp) | |
| @suspects = @words.select { |word| word.length == @size }.map(&:downcase).shuffle | |
| end | |
| def solve | |
| solve_recursive([], 0) | |
| end | |
| def solve_recursive square, depth | |
| if depth == @size | |
| square | |
| else | |
| find_next_word square, depth | |
| end | |
| end | |
| def find_next_word square, depth | |
| next_suspects = words_for_depth(square, depth) | |
| find_next_step(next_suspects, square, depth) | |
| end | |
| def find_next_step(next_suspects, square, depth) | |
| next_suspects.lazy.map do |suspect| | |
| solve_recursive(square + [suspect], depth + 1) | |
| end.find { |step| step } | |
| end | |
| def words_for_depth(square, depth) | |
| words_matching_prefix get_prefix(square, depth) | |
| end | |
| def words_matching_prefix prefix | |
| @suspects.select { |word| word.start_with?(prefix) } | |
| end | |
| def get_prefix square, depth | |
| square.map { |word| word[depth] }.join | |
| end | |
| end | |
| puts *SquareSolver.new(ARGV[0].to_i).solve |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment