Starting with a word, change one letter at a time to get to the target word.

word_search.rb

$words_attempted = { } # global list of words already attempted
$word_dictionary = { } # global dictionary of valid words


# Returns the indicies for current_word as an array.  Setting
# optimized to true will place non-matching characters between
# the current and target words at the beginning of the array.
def get_letter_indicies(optimized, current_word, target_word)
  [].tap do |letter_indicies|

    (0...current_word.length).each do |i|
      if optimized && (current_word[i] != target_word[i])
        # If optimizations are enabled, work on the non-matching letter indicies first
        # by placing them at the beginning of the array
        letter_indicies.insert(0, i)
      else
        # Otherwise append it
        letter_indicies << i
      end
    end

  end
end


# Returns the possible letter replacements for the current_word in the
# letter_index position as an array.  Setting optimized to true will
# place direct match letters (i.e. matching target_word) at the start
# of the array.
def get_letters(optimized, current_word, target_word, letter_index)
  [].tap do |letters|

    ('a'..'z').each do |new_letter|
      # Skip this letter if it is already present at the current index (i.e. changing
      # the letter would result in the same word)
      next if new_letter == current_word[letter_index]

      # Build the resulting word by replacing the letter
      new_word = current_word.dup
      new_word[letter_index] = new_letter

      # Only attempt valid words
      next unless valid_word?(new_word)

      # Don't evaluate the same word more than once
      next if word_already_attempted?(new_word)

      if optimized && (target_word[letter_index] == new_letter)
        # If optimizations are enabled then try the letter that matches
        # the target first by placing at the beginning of the array
        letters.insert(0, new_letter)
      else
        # Otherwise append it
        letters << new_letter
      end
    end

  end
end


# Searches for a solution starting with current_word and attempting to change
# one letter at-a-time in order to match target_word.  Each step of the way
# must result in a valid word.  This function is written recursively so that
# if any particular path results in a dead-end, we can back out to the previous
# iteration and carry on with the search.  Setting optimized to true will attempt
# to find a shorter solution but may also result in dead-ends.
def search_for_word_solution(optimized, current_word, target_word, solution=[])
  solution << current_word
  $words_attempted[current_word] ||= true

  puts "Current iteration: #{ solution.join(' => ') }"

  if (current_word == target_word)
    # We've found a solution!
    return solution
  elsif solution.length > 100
    # Place a limit on our recursion depth
    return []
  else
    get_letter_indicies(optimized, current_word, target_word).each do |letter_index|
      # Skip this letter index if optimizations are enabled and the
      # current letter matches the target letter
      next if optimized && (current_word[letter_index] == target_word[letter_index])

      get_letters(optimized, current_word, target_word, letter_index).each do |new_letter|
        new_word = current_word.dup
        new_word[letter_index] = new_letter

        new_solution = search_for_word_solution(optimized, new_word, target_word, solution)

        return new_solution unless new_solution.empty?
      end
    end

    return []
  end

end

# Returns true if the word is in our dictionary
def valid_word?(word)
  $word_dictionary.has_key?(word)
end

# Returns true if we have already attempted this word
def word_already_attempted?(word)
  $words_attempted.has_key?(word)
end



# Read in our dictionary of valid words
# Tested with this dictionary: https://raw.githubusercontent.com/atebits/Words/master/Words/en.txt
File.open('en.txt').each_line do |line|
  $word_dictionary[line.chomp] = true
end



start_word = 'code'
target_word = 'ruby'

puts "Attempting to find a solution for '#{ start_word }' => '#{ target_word }'\n"

# First try finding a solution with optimizations enabled
solution = search_for_word_solution(true, start_word, target_word)

# If we failed to find a solution using optimizations, then try the
# brute force approach
if solution.empty?
  puts "\nFailed to find a solution using optimizations.  Falling back to brute force...\n"
  $words_attempted = { }
  solution = search_for_word_solution(false, start_word, target_word)
end

if solution.empty?
  puts "\nCould not find a solution!\n"
else
  puts "\nSolution has been found! #{ solution.join(' => ') }\n"
end


# Attempting to find a solution for 'code' => 'ruby'
# Current iteration: code
# Current iteration: code => coda
# Current iteration: code => coda => cods
# Current iteration: code => coda => cods => cobs
# Current iteration: code => coda => cods => cobs => cobb
# Current iteration: code => coda => cods => cobs => cobb => cubs
# Current iteration: code => coda => cods => cobs => cobb => cubs => cube
# Current iteration: code => coda => cods => cobs => cobb => cubs => cube => rube
# Current iteration: code => coda => cods => cobs => cobb => cubs => cube => rube => ruby
#
# Solution has been found! code => coda => cods => cobs => cobb => cubs => cube => rube => ruby