Heya dear quizers,

here is my solution.
This is a breadth-first algorithm from both sides.

It may be interesting that it doesn't search the dictinary
for words simmilar do the given ones (or the reachables) but
generates them (rotating each character of the word from a to
z) and looks up the result in a big Set of words (the $dict).

Because the lookup in a hashtable (what Set uses) is constant
the algorithm doesn't slow down with bigger dictinaries. It
does slow down with longer words, but thats quite normal.

Half of the lines are for option handling, search_words and
find_chain are the only interresting methods.

I would realy like to see some speed comparisons (on a large
dict :) ).

One more thing, this doesn't use recursion, so doing realy
long chains shoudn't be a problem (except for runtime of
course)

cheers

Simon

-----------------------------------------------------------

require 'set'
require 'getoptlong'

def search_words words, known
   hash= Hash.new
   words.each do |word|
     (s = word.dup).size.times do |i|
       26.times do |c| s[i] = ?a + (s[i] + 1 - ?a) % 26
         hash[s] = word if $dict.include?(s) && !known[s]
       end
     end
   end
   hash
end

def find_chain word_a, word_b
   reachable_a = (temp_a = {word_a => 0}).dup
   reachable_b = (temp_b = {word_b => 0}).dup
   found = nil

   loop do
     reachable_a.merge!(temp_a = search_words(temp_a.keys, reachable_a))
     break if found=temp_a.inject(nil){|r, w|reachable_b[w[0]]? w[0]:r}
     warn "reachable a: #{reachable_a.size}" if $verbose

     reachable_b.merge!(temp_b = search_words(temp_b.keys, reachable_b))
     break if found=temp_b.inject(nil){|r, w|reachable_a[w[0]]? w[0]:r}
     warn "reachable b: #{reachable_b.size}" if $verbose

     if temp_a.size == 0 || temp_b.size == 0
       puts "now way!";
       exit 0
     end
   end

   word, list = found, [found]
   while (word = reachable_a[word]) && word != 0
     list.insert(0, word)
   end
   word = found
   while (word = reachable_b[word]) && word != 0
     list.push(word)
   end
   list
end

def usage
   puts "#{$PROGRAM_NAME} [-v|--verbose] [-h|--help]"+
     "[-d|--dictionary] {word1} {word2}"
   exit
end

opts = GetoptLong.new(
   [ "--dictionary", "-d", GetoptLong::REQUIRED_ARGUMENT ],
   [ "--verbose", "-v", GetoptLong::NO_ARGUMENT ],
   [ "--help", "-h", GetoptLong::NO_ARGUMENT ])

$verbose, dictfile = nil, 'words.txt'
opts.each do |opt, arg|
   usage if opt == "--help"
   $verbose = true if opt == "--verbose"
   if opt == "--dictionary"
     dictfile = arg
     usage if dictfile.empty?
   end
end
usage if ARGV.size != 2

$dict = Set.new
open(dictfile){|f| f.each{|w|$dict << w.chomp}}

puts find_chain(ARGV[0], ARGV[1])

-----------------------------------------------------------