Skip to content

Instantly share code, notes, and snippets.

@wstrinz
Forked from mathias/Gemfile
Last active December 16, 2015 19:30
Show Gist options
  • Save wstrinz/5486019 to your computer and use it in GitHub Desktop.
Save wstrinz/5486019 to your computer and use it in GitHub Desktop.
source "https://rubygems.org"
gem 'rspec'
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment