#!/usr/local/bin/ruby

# Add some methods to the String class that help us find which
# words are adjacent to each other
class String
  # Iterate through a string by index. Passes both the index and
  # the character at that index to the supplied block
  def each_byte_idx
    i = 0
    while i < self.length
      yield i, self[i]
      i += 1
    end
  end
  
  # Determine if the strings are 'adjacent' to another, that is if 
  # they differ by a single character
  def adjacent_to?(s)
    raise ("Strings not the same length: [%s] [%s]" % [self, s]) if
      self.length != s.length
      
    dif = 0
    self.each_byte_idx do |i, chr|
      dif += 1 if s[i] != chr
      return false if dif > 1
    end
    
    return true
  end
end

# Represents a word in our network of connected words.
class Word
  # adjacent: list of words that differ from this word by one character
  # fwd_path, rev_path: lists of words used by the dictionary to store
  #      shortest paths, either from the start-word in a search or from
  #      the end-word in the search.
  attr_accessor :adjacent, :fwd_path, :rev_path
    
  # Constructor. Takes the string that this word represents
  def initialize(word)
    @word = word
    @adjacent, @fwd_path, @rev_path = [], [], []
  end
  
  # True if this word differs from the provided word by a single character
  def adjacent_to?(word)
    @word.adjacent_to?(word.to_s)
  end
  
  def to_s
    @word
  end
  
  # so irb doesn't barf
  def inspect
    to_s
  end
end

# A dictionary of words of a particular length. Really a graph of 
# connected words not a dictionary in the classic sense, but it's 
# the most logical English word to use.
class Dictionary
  # word_length: the length of the words in this dictionary
  attr_reader :word_length
  
  # Factory: builds a dictionary of words of a particular length
  # from the default wordlist file
  def Dictionary.load(word_length)
    dict = Dictionary.new(word_length)
    
    IO.foreach("wordlist.txt") do |line|
      line.strip!
      dict.add_word(Word.new(line)) if line.length == word_length
    end
    
    return dict
  end
  
  # constructor. Takes the word-length for words in this dictionary
  def initialize(word_length)
    @words = []
    @word_length = word_length
  end
  
  # Find the word in the dictionary corresponding to the string s.
  def find_word(s)
    word = @words.find { |word| word.to_s == s }
    raise ("%s not found" % s) if (word == nil)
    return word
  end
  
  # Iterate through each word in the dictionary
  def each_word(&block)
    @words.each &block
  end
  
  # Nice string rep
  def to_s
    "Dictionary of %d %d-letter words" % [@words.length, @word_length]
  end
  
  # So IRB doesn't barf
  def inspect
    self.to_s
  end
  
  # Calculate _all_ the shortest paths from word to all other reachable
  # words in the dictionary. After the calculation is done, you can find
  # the path from word to word2 in word2.fwd_path. If that path is empty
  # then there is no possible route between the two words.
  def calculate_all_paths(from)
    clean()
    wordlist = [from]
    from.fwd_path = [from]
    
    until wordlist.empty?
      next_words = []
      wordlist.each do |word|
        word.adjacent.each do |adj|
          if adj.fwd_path.length == 0
            adj.fwd_path = word.fwd_path + [adj]
            next_words.push(adj)
          end
        end
      end
      wordlist = next_words
    end
  end
  
  # find the shortest path from 'from' to 'to'. Unlike the calculate_all_paths
  # method, this doesn't leave the words in the dictionary in a useful enough
  # state to find any more information
  def find_path(from, to)
    clean()
    from_words = [from]
    from.fwd_path = [from]
    
    to_words = [to]
    to.rev_path = [to]
    
    until from_words.empty? or to_words.empty?
      next_words = []
      from_words.each do |word|
        word.adjacent.each do |adj|
          if adj.fwd_path.length == 0
            adj.fwd_path = word.fwd_path + [adj]
            next_words.push(adj)
          end
          return join_paths(adj) if adj.rev_path.length != 0
        end      
      end
      from_words = next_words
      
      next_words = []
      to_words.each do |word|
        word.adjacent.each do |adj|
          if adj.rev_path.length == 0
            adj.rev_path = word.rev_path + [adj]
            next_words.push(adj)
          end
          return join_paths(adj) if adj.fwd_path.length != 0
        end        
      end
      to_words = next_words
    end

    return []
  end
  
  # Add a new Word to the dictionary, and create its links to other
  # words. This is, of course, O(N).
  def add_word(new_word)
    @words.each do |word|
      if word.adjacent_to?(new_word)
        word.adjacent.push(new_word)
        new_word.adjacent.push(word)
      end
    end
  
    @words.push(new_word)
  end
  
  private
  
  # Reset all words in the dictionary so they're ready for a new search
  def clean
    @words.each do |word| 
      word.fwd_path = []
      word.rev_path = []
    end
  end
  
  # join fwd and reverse paths of the 'joining word' that fills the
  # shortest path
  def join_paths(word)
    word.fwd_path + (word.rev_path.reverse)[1..-1]
  end
end