My solution uses the same method of others here: bi-directional breadth-first-search. This is usually the first thought when looking for a shortest path in a non-weighted graph. The only difference is that after I load the dictionary and set up all of the graph edges (My algorithm right now is pretty slow for doing this), I use Marshal to save it off to disk. So I only have to load the dictionary and set up the graph once. When I do the actual graph search it works pretty quick. I haven't found an instance where it takes more than half a second. Since I'm doing this I also had it check for the word lengths and then decide which dictionary to use instead of the -d option. dictionary.rb ========== class Dictionary # This takes in a straight array of words. (It is assumed that they # are all the same length, but I should add better error checking # on this at some point.) def initialize(words) @words = Hash.new words.each do |word| wordmaskarr = [] word.length.times { |i| wordmaskarr << "#{word[0...i]}.#{word[i+1...word.length]}"} #puts "#{word}:\t/#{wordmaskarr.join('|')}/" wordmask = Regexp.new(wordmaskarr.join('|')) @words[word] ||= [] words.each do |otherword| if(otherword =~ wordmask && otherword != word) then @words[otherword] ||= [] #puts "\t\tfound match: #{otherword}" @words[word] |= [otherword] @words[otherword] |= [word] end end end end def chain(from, to) if(!@words[from]) then puts "#{from} not in dictionary" return [] elsif(!@words[to]) then puts "#{to} not in dictionary" return [] elsif(from==to) return [from] end linknode = nil #these hashes are used to keep links back to where they came from fromedges = {from => ""} toedges = {to => ""} #these are queues used for the breadth first search fromqueue = [from] toqueue = [to] while(toqueue.length>0 && fromqueue.length>0) fromnode = fromqueue.shift tonode = toqueue.shift if(toedges[fromnode] || fromnode==to) then linknode = fromnode break elsif(fromedges[tonode] || tonode==from) then linknode = tonode break end @words[fromnode].each do |i| if(!fromedges[i]) then fromedges[i] = fromnode fromqueue.push(i) end end @words[tonode].each do |i| if(!toedges[i]) then toedges[i] = tonode toqueue.push(i) end end end if(linknode == nil) then return nil end chain = [] currnode = linknode while(fromedges[currnode] != "") chain.unshift(currnode) currnode = fromedges[currnode] end currnode = toedges[linknode] while(toedges[currnode] != "") chain.push(currnode) currnode = toedges[currnode] end return [from]+chain+[to] end end makedicts.rb ========== require 'dictionary' dicts = Hash.new File.open("WORD.LST") do |file| file.each_line do |line| line.chomp!.downcase! (dicts[line.length] ||= []) << line end end dicts.each do |len,dict| dict.sort! File.open("dict#{0 if len<10}#{len}.txt", "w") do |file| file.write(dict.join("\n")) end end dicts.each do |len, dict| if len<50 then puts "Making dictionary graph for #{len} letter words" currdict = Dictionary.new(dict) File.open("dict#{0 if len<10}#{len}.dump", "w") do |file| Marshal.dump(currdict, file) end end end wordchain.rb ========== require 'dictionary' if(ARGV.length != 2) then puts "Two words required"; exit(1) end from = ARGV[0] to = ARGV[1] if(from.length != to.length) then puts "Word are different lengths"; exit(1) end dict = nil File.open("dict#{0 if from.length<10}#{from.length}.dump") do |file| dict = Marshal.load(file) chain = dict.chain(from, to) if(chain) then puts chain.join("\n") else puts "No link found" end end Example runs: $ time ruby wordchain.rb duck ruby duck duce luce lube rube ruby real 0m0.196s user 0m0.186s sys 0m0.030s $ time ruby wordchain.rb kitten rabies kitten kitted kilted killed gilled galled gabled gables gabies rabies real 0m0.347s user 0m0.343s sys 0m0.030s