-
-
Save wstrinz/5486019 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
source "https://rubygems.org" | |
gem 'rspec' |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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