Gemfile

source "https://rubygems.org"

gem 'rspec'

word-chains.rb

require 'rspec'

class WordNode
  attr_accessor :word
  attr_accessor :neighbors
  attr_accessor :path

  def initialize(word,path=[])
    @neighbors = Dictionary.new.neighbors_for(word)
    @word = word
    @path = path
    @path << word
  end
end

class Dictionary
  attr_accessor :words
  def initialize
    dictionary_file = File.open('/usr/share/dict/words','r')
    @words = dictionary_file.read.split
  end

  def find(word)
    @words.include?(word)
  end

  def diff(word1,word2)
    diff = 0
    word1.length.times do |i|
      diff += 1 if word1[i] != word2[i]
    end
    diff
  end

  def neighbors?(word1, word2)
  # puts word1, word2
    unless word1.length != word2.length
      # split = word1.split(//)
      if diff(word1, word2) == 1
        true
      else
        false
      end
    else
      false
    end
  end

  def neighbors_for(word)
    neighbors = []
    @words.each do |w|
        neighbors << w if neighbors?(w,word)
    end
    return neighbors
  end

end

class Chainer
  attr_accessor :words
  attr_accessor :dictionary

  def initialize
    @dictionary = Dictionary.new
    @words = []
    # words = 0.0
    # dictionary.words.each do |w|
    #   puts (words / dictionary.words.length.to_f)
    #   @words << WordNode.new(w)
    #   words += 1
    # end
  end

  def find_chain(from_word, to_word)
    if (from_word.length != to_word.length)
      nil
    else
      node1 = WordNode.new(from_word)
      node2 = WordNode.new(to_word)
      if(node1.neighbors.length == 0 || node2.neighbors.length == 0)
        nil
      else
        queue = [node1]
        searched = []

        while(!queue.empty?) do
          w = queue.shift
          # puts w.word
          if w.word == to_word
            return w.path
          end
          searched << w.word
          w.neighbors.each do |neighbor|
            unless searched.include?(neighbor)
              queue << WordNode.new(neighbor,w.path)
            end
          end
        end

        false
      end
    end
  end

end

describe  Dictionary do
  before :each do
    @dictionary = Dictionary.new
  end

  it "should read dictionary words" do
    expect(@dictionary.words).to be_kind_of Array
  end

  it "should be able to lookup words" do
    word = "yoke"
    expect(@dictionary.find(word)).to be_true
  end

  it "should not be able to find words that aren't in the dictionary" do
    word = "doesnotexist"
    expect(@dictionary.find(word)).to be_false
  end

  it "can check if two words are neighbors" do
    word1, word2 = "worried", "worrier"
    expect(@dictionary.neighbors?(word1, word2)).to be_true
  end
end

describe WordNode do
  it "should create a word and load its neighbors" do
    n = WordNode.new("yoke")
    expect(n.neighbors.length).to be > 0
    # puts n.neighbors
  end
end

describe Chainer do
  before :all do
    @c = Chainer.new
  end

  it "should have word objects" do
    expect(@c.words).not_to be_nil
  end

  it "should find chain between known words" do
    expect(@c.find_chain("cat","cog")).to be_true
  end
end