Shortest path between strings only substitutions

shortest-string-path-substitutions.rb

Words = Set.new
File.open('/usr/share/dict/words') do |file|
  file.each do |line|
    Words.add(line.strip)
  end
end

Alphabet = 'abcdefghijklmnopqrstuvwxyz'.split('')

def path(input, output)
  input, output = input.downcase, output.downcase
  path_recursive(input, output, [input], Hash.new)
end

def path_recursive(input, output, progress, memory)
  return progress if input == output
  similar_words = []
  return memory[[input, output]] if memory[[input, output]]
  (0..(input.length-1)).each do |i|
    next if input[i] == output[i]
    replacements = Alphabet - [input[i]]
    replacements.each do |r|
      modified = input.clone; modified[i] = r
      next unless Words.include?(modified)
      similar_words << modified
    end
  end
  paths = []
  (similar_words - progress).each do |word|
    if (p = path_recursive(word, output, progress + [word], memory))
      paths << p
    end
  end
  paths.sort_by(&:length).first.tap {|r| memory[[input, output]] = r }
end