From: Dominik Bathon <dbatml@...>
Date: 2005-08-29T07:51:59+09:00
Subject: Re: [SOLUTION] Word Chains (#44)

Here is my solution.

It uses breadth first search (unidirectional) and is quite fast.
I use a trick to find all possible steps fast: While reading the words I  
store them in a hash of arrays, e.g. when adding the word "dog", I  
register "dog" as step for "\0og", "d\0g" and "do\0", later while look for  
a step for "dot" I will use all words registered for "\0ot", "d\0t" or  
"do\0". So reading the dictionary takes some time (and memory), but  
afterwards finding the shortest chains is really fast. I also use symbols  
instead of strings in some places for faster hash-lookup.

Of course I have also implemented my extra bonus challenge, to find a  
longest shortest chain and Simon's suggestion to allow words with  
different length.

Some examples:

$ time ruby word_chain.rb duck ruby
duck
luck
luce
lube
rube
ruby

real    0m1.414s
user    0m1.326s
sys     0m0.028s
$ time ruby word_chain.rb ape human
ape
are
arm
aum
hum
huma
human

real    0m2.604s
user    0m2.484s
sys     0m0.052s
$ time ruby word_chain.rb computer a
computer
compute
compote
compose
compos
compo
campo
camp
cam
aam
aa
a

real    0m12.550s
user    0m11.890s
sys     0m0.232s

The examples with words of different length take longer because much more  
words from the dictionary have to be added to the hash.

$ time ruby longest_shortest.rb 3
edh
edo
ado
aho
pho
phi
poi
poa
pya
mya

real    0m4.840s
user    0m4.615s
sys     0m0.055s
$ time ruby longest_shortest.rb 6
zounds
wounds
woundy
[49 lines]
pantry
paltry
peltry

real    1m12.614s
user    1m10.113s
sys     0m0.655s
$ time ruby longest_shortest.rb 9
unpausing
unpassing
unpasting
unwasting
unwaiting
unwailing
unfailing
unfalling
unfilling
untilling
untelling
unselling
unsealing
unhealing
unhearing
unwearing
unweaving
unreaving
unreeving
unreeling
unfeeling
unfeeding
unheeding

real    0m9.252s
user    0m8.836s
sys     0m0.158s
$ time ruby longest_shortest.rb 12
modification
codification
conification
sonification
sinification
vinification
vilification
bilification

real    0m7.492s
user    0m7.127s
sys     0m0.138s

Dominik


The code:

# word_chain.rb
####################

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

     # 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

     # 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


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


# longest_shortest.rb
####################

require "word_chain"

class WordSteps
     # builds a longest shortest chain starting with word and returns it as
     # array of symbols
     # if the found chain is shorter than old_max, then it is possible to
     # determine other words, whose longest shortest chain will also be not
     # longer than old_max, those words will be added to not_longer, that  
way
     # the caller can avoid searching a longest chain for them
     def longest_word_chain(word, not_longer = {}, old_max = 0)
         # build chain with simple breadth first search until no more steps  
are
         # possible, one of the last steps is then a longest shortest chain
         current = [word.to_sym]
         pre = { current[0] => nil } # will contain the predecessors
         target = nil
         iterations = []
         loop do
             next_step = []
             iterations << current
             current.each do |csym|
                 each_possible_step(csym.to_s) do |ssym|
                     unless pre.has_key? ssym
                         pre[ssym] = csym
                         next_step << ssym
                     end
                 end
             end
             if next_step.empty?
                 target = current[0]
                 break
             else
                 current = next_step
             end
         end

         # build the chain (in reverse order)
         chain = [target]
         chain << target while target = pre[target]

         # add words to not_longer if possible (see above)
         if chain.size < old_max
             (0...([old_max+1-chain.size, iterations.size].min)).each do |i|
                 iterations[i].each { |w| not_longer[w] = true }
             end
         end
         chain.reverse
     end
end



if $0 == __FILE__
     dictionary = DEFAULT_DICTIONARY

     # parse arguments
     if ARGV[0] == "-d"
         ARGV.shift
         dictionary = ARGV.shift
     end
     word_length = [ARGV.shift.to_i, 1].max

     # read dictionary
     warn "Loading dictionary..." if $DEBUG
     word_steps = WordSteps.load_from_file(dictionary, word_length)

     # search chain
     warn "Searching longest chain..." if $DEBUG
     max = 0
     chain = nil
     not_longer = {}
     word_steps.each_word { |w|
         next if not_longer[w.to_sym]
         cur = word_steps.longest_word_chain(w, not_longer, max)
         if cur.size > max
             chain = cur
             max = cur.size
             warn chain.inspect if $DEBUG
         end
     }

     # print result
     puts chain || "No chain found!"
end