From: Ruby Quiz Date: 2005-09-01T21:55:58+09:00 Subject: [SUMMARY] Word Chains (#44) Gavin Kistner asked that I try timing the quiz solutions this week. I did indeed "try" that very thing and the results shocked me. Let's take a look, shall we: === Timing ./Adam Shelly/wordchain === Wordchain Finder Connecting duck -> ruby nil === ./Adam Shelly/wordchain: 0.950922 seconds === === Timing ./Brian Schroeder/wordchain.rb === Loading database Searching connection between duck and ruby duck dusk rusk ruse rube ruby === ./Brian Schroeder/wordchain.rb: 3.722559 seconds === === Timing ./Daniel Sheppard/word_chain.rb === ./Daniel Sheppard/word_chain.rb:42:in `find_distances': undefined local variable or method `distances' for # (NameError) from ./Daniel Sheppard/word_chain.rb:46:in `shortest_path' from ./Daniel Sheppard/word_chain.rb:135 === ./Daniel Sheppard/word_chain.rb: 0.019652 seconds === === Timing ./David Tran/word_chain.rb === Loading dictionary... Building chain... No solution. === ./David Tran/word_chain.rb: 314.369476 seconds === === Timing ./David Tran/word_chain2.rb === Loading dictionary... Building chain... No solution. === ./David Tran/word_chain2.rb: 1.184791 seconds === === Timing ./Dominik Bathon/word_chain.rb === duck luck luce lube rube ruby === ./Dominik Bathon/word_chain.rb: 1.472335 seconds === === Timing ./Gavin Kistner/word_chain.rb === ./Gavin Kistner/word_chain.rb:65:in `Integer': invalid value for Integer: "duck" (ArgumentError) from ./Gavin Kistner/word_chain.rb:65 === ./Gavin Kistner/word_chain.rb: 0.020758 seconds === === Timing ./horndude77/wordchain.rb === Two words required === ./horndude77/wordchain.rb: 0.014078 seconds === === Timing ./James Edward Gray II/word_chain.rb === duck ruck rusk ruse rube ruby === ./James Edward Gray II/word_chain.rb: 27.577392 seconds === === Timing ./Levin Alexander/word_chains.rb === duck ruck rusk ruse rube ruby === ./Levin Alexander/word_chains.rb: 2.795315 seconds === === Timing ./Paolo Capriotti/chain.rb === no chain could be found === ./Paolo Capriotti/chain.rb: 65.236484 seconds === === Timing ./Simon Kroeger/word_chain.rb === now way! === ./Simon Kroeger/word_chain.rb: 2.981419 seconds === === Timing ./Simon Kroeger/word_chain2.rb === ./Simon Kroeger/word_chain2.rb:2:in `foreach': No such file or directory - duck (Errno::ENOENT) from ./Simon Kroeger/word_chain2.rb:2 === ./Simon Kroeger/word_chain2.rb: 0.017581 seconds === === Timing ./Will Thimbleby/word_chain.rb === duck dunk dune rune rube ruby === ./Will Thimbleby/word_chain.rb: 63.026336 seconds === === Timing ./William James/word_chain.rb === ./William James/word_chain.rb:1:in `read': No such file or directory - dict (Errno::ENOENT) from ./William James/word_chain.rb:1 === ./William James/word_chain.rb: 0.024691 seconds === === Timing ./William James/word_chain2.rb === ./William James/word_chain2.rb:2:in `foreach': No such file or directory - duck (Errno::ENOENT) from ./William James/word_chain2.rb:2 === ./William James/word_chain2.rb: 0.01695 seconds === I just ran sixteen programs there all with exactly the same command, outlined in the quiz. Five of the sixteen programs died with an exception. Six more printed only an error message or couldn't find a chain. That leaves us with five chains out of sixteen attempts, about a 31% accuracy ratio. Yikes! Obviously, the biggest problem are the exceptions and the error messages. These programs refused to try and build a chain. (Yes, I looked into all of them to see why and no, I didn't try to fix any of them.) The main issue here was that people changed my proposed command-line arguments. Some of them moved the dictionary to an optional third argument and others added new options. I think new options are great, but was it really that hard to support the quiz format? Will Thimberly parsed the quiz described arguments in seven lines, so I think it was reasonable. Of course, you are always welcome to submit whatever you like as a Ruby Quiz solution. Along the same lines, I consider myself free to ignore anything that creates more work for me. The one exception is that I do try to resolve external dependancies, especially if you make it easy on me. Paulo Capriotti gave me a link right to the library needed and Brian included a README that showed how to build a required (and included!) C extension. Thank you both. Anyway, if someone would like to resolve all of the above issues and rerun time trials, please be my guest. If you download the solutions from the Ruby Quiz site, my time_trial.rb script is in the root directory and hopefully that will get you started. The minor issue this time around is that some solutions obviously had trouble finding chains, at least with my dictionary. Not much to say here except that unit tests probably could have helped. Several test cases were posted to Ruby Talk. Hope everyone was trying those as they came in. Okay, let's clean up those time trials and have another look at them: === Timing ./Brian Schroeder/wordchain.rb === Loading database Searching connection between duck and ruby duck dusk rusk ruse rube ruby === ./Brian Schroeder/wordchain.rb: 3.722559 seconds === === Timing ./Dominik Bathon/word_chain.rb === duck luck luce lube rube ruby === ./Dominik Bathon/word_chain.rb: 1.472335 seconds === === Timing ./James Edward Gray II/word_chain.rb === duck ruck rusk ruse rube ruby === ./James Edward Gray II/word_chain.rb: 27.577392 seconds === === Timing ./Levin Alexander/word_chains.rb === duck ruck rusk ruse rube ruby === ./Levin Alexander/word_chains.rb: 2.795315 seconds === === Timing ./Will Thimbleby/word_chain.rb === duck dunk dune rune rube ruby === ./Will Thimbleby/word_chain.rb: 63.026336 seconds === I actually expected Brian's to be the fastest, just from what I had read about them as they came in. Under the hood, Brian is using a priority queue written in C. As the saying goes though, the speed is in the algorithm, and Dominik and Levin prove the truth of it. For an interesting comparison, Levin is using a plain Ruby priority queue. Let's take a look at that class: # inefficient implementation of a priority queue # class SimpleQueue def initialize @storage = Hash.new { [] } end def insert(priority, data) @storage[priority] = @storage[priority] << data end def extract_min return nil if @storage.empty? key, val = *@storage.min result = val.shift @storage.delete(key) if val.empty? return result end end If you look at that insert() method, you might find the calls a bit odd. The code does work, but only because of the awkward assignment that shouldn't be needed. This is a gotcha that bit me early in learning Ruby so I'll explain it here in the hope of helping others. Array.new() can take a number and a block. It will invoke the block the indicated number of times to generate an Array, using the return value of the block as each member. Because Hash.new() also takes a block and will call it when a key is first accessed without an assignment, the natural assumption is that it uses the return value, and in truth it does, but it does not set the key to that value! That's why the extra assignment is needed above. The fix is to use the passed in Hash and key String objects to set it yourself. Using that, we can write the above a little more naturally: # inefficient implementation of a priority queue # class SimpleQueue def initialize @storage = Hash.new { |hash, key| hash[key] = [] } end def insert(priority, data) @storage[priority] << data end def extract_min return nil if @storage.empty? key, val = *@storage.min result = val.shift @storage.delete(key) if val.empty? return result end end I just think that's more natural and easy to follow. They work the same. Looking at the code itself, there's nothing too fancy here. It stores items by priority in a Hash. The real work is done in extract_min() which just locates the minimum value, shifts some data off of that Array, and returns it. The comment warns that it's inefficient, but it sure is easy to setup and use. Hard to beat that for just fifteen lines of code. Nice work Levin. Now I want to examine Dominik's lightning fast solution. Here's how it starts: DEFAULT_DICTIONARY = "/usr/share/dict/words" # Data structure that efficiently stores words from a dictionary in a way, # that it is easy to find all words that differ from a given word only at # one letter (words that could be the next step in a word chain). # Example: when adding the word "dog", add_word will register "dog" as # step for "\0og", "d\0g" and "do\0", later each_possible_step("cat") # will yield all words registered for "\0at", "c\0t" or "ca\0". class WordSteps def initialize @steps = Hash.new { |h, k| h[k] = [] } @words = {} end # yields all words (as strings) that were added with add_word def each_word(&block) @words.each_key(&block) end # add all steps for word (a string) to the steps def add_word(word) sym = word.to_sym wdup = word.dup for i in 0...word.length wdup[i] = 0 @steps[wdup] << sym wdup[i] = word[i] end @words[word] = sym # for allow_shorter and each_word end # yields each possible next step for word (a string) as symbol, some # possible steps might be yielded multiple times # if allow_shorter is true, word[0..-2].to_sym will also be yielded # if available # if allow_longer is true, all words that match /#{word}./ will be # yielded def each_possible_step(word, allow_shorter = false, allow_longer = false) wdup = word.dup for i in 0...word.length wdup[i] = 0 if @steps.has_key?(wdup) @steps[wdup].each { |step| yield step } end wdup[i] = word[i] end if allow_shorter && @words.has_key?(tmp = word[0..-2]) yield @words[tmp] end if allow_longer && @steps.has_key?(tmp = word + "\0") @steps[tmp].each { |step| yield step } end end # ... The comments are just great in this code. If you read them, you'll understand how the code moves so darn fast. Here's the mini-summary: When called add_word() maps a word to all possible variations with exactly one letter changed to a null character. Later, each_possible_step() can use the same mapping to quickly look up all possibilities for the current word in question. This can also handle searches where words aren't the same size, though that wasn't part of the quiz. # ... # tries to find a word chain between word1 and word2 (strings) using # all available steps # returns the chain as array of symbols or nil, if no chain is found # shorter/longer determines if shorter or longer words are allowed in # the chain def build_word_chain(word1, word2, shorter = false, longer = false) # build chain with simple breadth first search current = [word1.to_sym] pre = { current[0] => nil } # will contain the predecessors target = word2.to_sym catch(:done) do until current.empty? next_step = [] current.each do |csym| each_possible_step(csym.to_s, shorter, longer) do |ssym| # have we seen this word before? unless pre.has_key? ssym pre[ssym] = csym throw(:done) if ssym == target next_step << ssym end end end current = next_step end return nil # no chain found end # build the chain (in reverse order) chain = [target] chain << target while target = pre[target] chain.reverse end # ... This is the search for a chain. Believe it or not, it's a rather boring unidirectional breadth-first search. Most people implemented much fancier searches, but thanks to Domink's dictionary storage this code doesn't need to be clever. This code just uses each_possible_step() to walk level-by-level of like words, until it finds the end word. The pre Hash is used to keep the code from retracing its steps and to walk the previous word chain to build the final answer at the bottom of the method. This method has a nice use of catch() and throw() to create the equivalent of a labeled goto call in many other languages. There's one more piece to this class: # ... # builds and returns a WordSteps instance "containing" all words with # length in length_range from the file file_name def self.load_from_file(file_name, length_range) word_steps = new IO.foreach(file_name) do |line| # only load words with correct length if length_range === (word = line.strip).length word_steps.add_word(word.downcase) end end word_steps end end # ... Here's the simple dictionary reading method. Note the clever use of a Range argument here, to support word chains of differing sizes. The === check ensures that the current dictionary word is in the Range we care about, before it's added to the memory mappings. Finally, here's the interface code: # ... if $0 == __FILE__ dictionary = DEFAULT_DICTIONARY # parse arguments if ARGV[0] == "-d" ARGV.shift dictionary = ARGV.shift end unless ARGV.size == 2 puts "usage: #$0 [-d path/to/dictionary] word1 word2" exit 1 end word1, word2 = ARGV[0].strip.downcase, ARGV[1].strip.downcase shorter = word1.length > word2.length longer = word1.length < word2.length length_range = if longer word1.length..word2.length else word2.length..word1.length end # read dictionary warn "Loading dictionary..." if $DEBUG word_steps = WordSteps.load_from_file(dictionary, length_range) word_steps.add_word(word2) # if it is not in dictionary # build chain warn "Building chain..." if $DEBUG chain = word_steps.build_word_chain(word1, word2, shorter, longer) # print result puts chain || "No chain found!" end Most of that is just the code to support the arguments from the quiz. Note the clever building of the length Range that allows the program to switch behavior when different sized words are given. All around great code Domink. Thanks for the lesson! My thanks to all who were able to understand my command-line argument instructions this week. ;) Seriously, thanks to all submitters. Many great solutions this week. If you don't know what tomorrow's quiz is yet, you're not reading Redhanded closely enough...