Kenny Dewhirst

I recently got a chance to work with Ruby for the first time. I’m pretty pleased with the result, and I thought it would make a pretty good post here.

What follows is what’s called a code kata, and comes from this website. Code katas are a kind of practice problem, and the word comes from a Japanese word for a kind of ‘practicing the motions’ martial art exercise. The problems are much simpler than most business problems, but are complicated enough to be interesting. There’s a full description of the idea here.

What this kata asks is to make a program that transforms one word into another by changing one letter at a time, without making any invalid words. This kind of problem was invented by Lewis Carrol, who called them ‘word ladders‘. This kind of logic problem is a good fit for katas because it gives us a chance to be clever; I have written this so that it always finds the shortest path between two words.

The code uses a word list of ‘real’ or ‘valid’ words named words.txt which must be in the same folder as the Ruby script for it to run.

# Checks to see if you can move from the first string to the second in a single
# move
def connected?(first, second)
  if first.length != second.length
    return false
  end

# Count how many letters in the first string are different from in the second
# string
  count = 0
  for index in 0..first.length
    if first[index] != second[index]
      count = count + 1
    end
  end
  count == 1
end

# Gets the set of words in a list that are connected to a given word by a
# single move
def get_connected_words(word, list)
  connected_words = []
  list.each{|word_to_check|
    if connected?(word, word_to_check)
      connected_words << word_to_check
    end
  }

  return connected_words
end

# Does the work of finding the chain by doing a breadth-first search of the
# dictionary
def find_chain(first, target)
  if first.length != target.length
    puts "There is no chain between '" + first + "' and '" + target + " because they are different lengths."
    return
  end

  # Build an array of unvisited words of the right length from our dictionary
  unvisited_words = []
  File.open('words.txt').each_line{ |line|
    if line.strip.length == first.length
      unvisited_words << line.strip
    end
  }

  # Now that we have a list of words of the right length in memory, we might as
  # well check our arguments for validity
  if !unvisited_words.include?(first)
    puts "There is no chain between '" + first + "' and '" + target + "' because '" + first + "' is not in my dictionary."
    return
  elsif !unvisited_words.include?(target)
    puts "There is no chain between '" + first + "' and '" + target + "' because '" + target + "' is not in my dictionary."
    return
  end

  puts "Please wait..."

  # Build a queue to hold the chains that we're going to try
  queue_of_chains = []

  # Add our degenerate chain (the start link) to the queue
  start_chain = Array.new()
  start_chain << first # Array with the single word in it
  queue_of_chains << start_chain

  # Remove our starting point from our list of nodes; we know it's a dead end
  unvisited_words.delete(first)

  success = false
  # Visit each chain in the queue, checking if the last link in the chain is
  # our target. Work finishes when we find a chain ending in our target
  # (success!) or we run out of queue (failure!)
  while !queue_of_chains.empty?
    chain_to_visit = queue_of_chains.shift()

    if chain_to_visit.last == target
      puts "Chain found!"
      success = true
      puts chain_to_visit
      break
    else
      # The chain we're looking at isn't a match, so try to add more things to
	  # our queue. We're adding copies of our chain, plus an unvisited word
	  # that will connect to the last link
      words_to_visit = get_connected_words(chain_to_visit.last, unvisited_words)
      words_to_visit.each{ |word|
        links_of_new_chain = Array.new(chain_to_visit)
        links_of_new_chain << word
        queue_of_chains << links_of_new_chain
      }

      # Don't let the words we just enqueued be added a second time
      unvisited_words = unvisited_words - words_to_visit
    end
  end

  if !success
    puts "Sorry, there is no chain connecting '" + first + "' and '" + target + "'."
  end
end

puts "This program tries to find a word chain between two words. Please enter a first word."
# All of the words in our dictionary are lowercase, so let's transform input
# rather than comparing case-insensitive everywhere else.
first = gets.chomp.downcase

puts "Okay; and your second word?"
target = gets.chomp.downcase

find_chain(first, target)