[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 #<Word:0x1c70ac> (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...