```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]? w: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]? w: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, ARGV)

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

```