#!/usr/local/bin/ruby # Add some methods to the String class that help us find which # words are adjacent to each other class String # Iterate through a string by index. Passes both the index and # the character at that index to the supplied block def each_byte_idx i = 0 while i < self.length yield i, self[i] i += 1 end end # Determine if the strings are 'adjacent' to another, that is if # they differ by a single character def adjacent_to?(s) raise ("Strings not the same length: [%s] [%s]" % [self, s]) if self.length != s.length dif = 0 self.each_byte_idx do |i, chr| dif += 1 if s[i] != chr return false if dif > 1 end return true end end # Represents a word in our network of connected words. class Word # adjacent: list of words that differ from this word by one character # fwd_path, rev_path: lists of words used by the dictionary to store # shortest paths, either from the start-word in a search or from # the end-word in the search. attr_accessor :adjacent, :fwd_path, :rev_path # Constructor. Takes the string that this word represents def initialize(word) @word = word @adjacent, @fwd_path, @rev_path = [], [], [] end # True if this word differs from the provided word by a single character def adjacent_to?(word) @word.adjacent_to?(word.to_s) end def to_s @word end # so irb doesn't barf def inspect to_s end end # A dictionary of words of a particular length. Really a graph of # connected words not a dictionary in the classic sense, but it's # the most logical English word to use. class Dictionary # word_length: the length of the words in this dictionary attr_reader :word_length # Factory: builds a dictionary of words of a particular length # from the default wordlist file def Dictionary.load(word_length) dict = Dictionary.new(word_length) IO.foreach("wordlist.txt") do |line| line.strip! dict.add_word(Word.new(line)) if line.length == word_length end return dict end # constructor. Takes the word-length for words in this dictionary def initialize(word_length) @words = [] @word_length = word_length end # Find the word in the dictionary corresponding to the string s. def find_word(s) word = @words.find { |word| word.to_s == s } raise ("%s not found" % s) if (word == nil) return word end # Iterate through each word in the dictionary def each_word(&block) @words.each &block end # Nice string rep def to_s "Dictionary of %d %d-letter words" % [@words.length, @word_length] end # So IRB doesn't barf def inspect self.to_s end # Calculate _all_ the shortest paths from word to all other reachable # words in the dictionary. After the calculation is done, you can find # the path from word to word2 in word2.fwd_path. If that path is empty # then there is no possible route between the two words. def calculate_all_paths(from) clean() wordlist = [from] from.fwd_path = [from] until wordlist.empty? next_words = [] wordlist.each do |word| word.adjacent.each do |adj| if adj.fwd_path.length == 0 adj.fwd_path = word.fwd_path + [adj] next_words.push(adj) end end end wordlist = next_words end end # find the shortest path from 'from' to 'to'. Unlike the calculate_all_paths # method, this doesn't leave the words in the dictionary in a useful enough # state to find any more information def find_path(from, to) clean() from_words = [from] from.fwd_path = [from] to_words = [to] to.rev_path = [to] until from_words.empty? or to_words.empty? next_words = [] from_words.each do |word| word.adjacent.each do |adj| if adj.fwd_path.length == 0 adj.fwd_path = word.fwd_path + [adj] next_words.push(adj) end return join_paths(adj) if adj.rev_path.length != 0 end end from_words = next_words next_words = [] to_words.each do |word| word.adjacent.each do |adj| if adj.rev_path.length == 0 adj.rev_path = word.rev_path + [adj] next_words.push(adj) end return join_paths(adj) if adj.fwd_path.length != 0 end end to_words = next_words end return [] end # Add a new Word to the dictionary, and create its links to other # words. This is, of course, O(N). def add_word(new_word) @words.each do |word| if word.adjacent_to?(new_word) word.adjacent.push(new_word) new_word.adjacent.push(word) end end @words.push(new_word) end private # Reset all words in the dictionary so they're ready for a new search def clean @words.each do |word| word.fwd_path = [] word.rev_path = [] end end # join fwd and reverse paths of the 'joining word' that fills the # shortest path def join_paths(word) word.fwd_path + (word.rev_path.reverse)[1..-1] end end