From: David Tran <email55555@...>
Date: 2005-08-30T04:55:50+09:00
Subject: Re: [SOLUTION] Word Chains (#44)

Here are my solutions. They are very slow ... 
Not elegant at all, but at least they can find the solution. :-)

(1) simple breadth-first
------------------------------------------------------------------------
def search( start_word, end_word, dictionary )
  # check pre-condition
  raise "invalid argument" if start_word.nil? || 
                              end_word.nil?   ||
                              dictionary.nil? ||
                              start_word.size != end_word.size

  return [strat_word, end_word] if start_word == end_word
  return nil unless dictionary.delete(start_word)
  return nil unless dictionary.delete(end_word)
  
  paths = [[start_word]]
  while !paths.empty?
    new_paths = []
    paths.each do |path|
      word = path.last
      word.size.times do |i|
        ('a'..'z').each do |c|
          new_word = word.dup
          new_word[i] = c
          return (path << new_word) if new_word == end_word
          next if !dictionary.delete(new_word)
          new_paths << (path.dup << new_word)
        end
      end
    end
    paths = new_paths
  end
  nil
end

dictionary = 'words.txt'
if d_index = ARGV.index('-d')
  ARGV.delete_at(d_index)
  dictionary = ARGV.delete_at(d_index)
end
start_word = ARGV[0]
end_word = ARGV[1]

if start_word.nil? || end_word.nil? || dictionary.nil?
  puts "Usage: ruby #$0 [ -d dictionary ] start_word end_word"
  exit
end

puts "Loading dictionary..."
words = []
File.open(dictionary) { |f|
  while word = f.gets
    word.chomp!
    words << word if word.size == start_word.size
  end
}

puts "Building chain..."
result = search(start_word, end_word, words)
puts( result ? result : "No solution." )
------------------------------------------------------------------------


(2) simple bidirectional breadth-first
------------------------------------------------------------------------
def search( start_word, end_word, dictionary )
  # check pre-condition
  raise "invalid argument" if start_word.nil? || 
                              end_word.nil?   ||
                              dictionary.nil? ||
                              start_word.size != end_word.size
                              
  return [strat_word, end_word] if start_word == end_word
  return nil unless dictionary.delete(start_word)
  return nil unless dictionary.delete(end_word)
  word_length = start_word.length
 
  start_paths = [[start_word]]
  end_paths = [[end_word]]
  paths = start_paths
  last_new_words = [end_word]
  loop do
    new_paths = []
    new_words = []
    paths.each do |path|
      word = path.last
      word_length.times do |i|
        ('a'..'z').each do |c|
          new_word = word.dup
          new_word[i] = c
          if index = last_new_words.index(new_word)
            if paths == start_paths
              return path.push(*end_paths[index].reverse)
            else
              return start_paths[index].push(*path.reverse)
            end
          end
          next unless dictionary.delete(new_word)          
          new_paths << (path.dup << new_word)
          new_words << new_word
        end
      end
    end
    
    return nil if new_paths.empty?
    
    if paths == start_paths
      start_paths = new_paths
      paths = end_paths
    else
      end_paths = new_paths
      paths = start_paths
    end
    last_new_words = new_words
  end
end


dictionary = 'words.txt'
if d_index = ARGV.index('-d')
  ARGV.delete_at(d_index)
  dictionary = ARGV.delete_at(d_index)
end
start_word = ARGV[0]
end_word = ARGV[1]

if start_word.nil? || end_word.nil? || dictionary.nil?
  puts "Usage: ruby #$0 [ -d dictionary ] start_word end_word"
  exit
end

puts "Loading dictionary..."
words = []
File.open(dictionary) { |f|
  while word = f.gets
    word.chomp!
    words << word if word.size == start_word.size
  end
}

puts "Building chain..."
result = search(start_word, end_word, words)
puts( result ? result : "No solution." )
------------------------------------------------------------------------