Created
February 22, 2012 18:15
-
-
Save alexschwartz/1886436 to your computer and use it in GitHub Desktop.
AnagramPairFinder
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' | |
describe 'AnagramPairFinder' do | |
let(:dictionary) { %w{ hot dog cat } } | |
let(:splitter) { AnagramPairFinder.new(dictionary) } | |
describe "#lookup" do | |
it "should split 'hotdog' into 'hot' & 'dog'" do | |
splitter.lookup('hotdog').should eq(%w{ dog hot }) | |
end | |
it "should not split 'hotdogs' "do | |
splitter.lookup('hotdogs').should be_nil | |
end | |
end | |
describe "#normalize" do | |
it { splitter.normalize('a').should eq(%w{ a }) } | |
it { splitter.normalize('hot').should eq(%w{ h o t }) } | |
it { splitter.normalize('dog').should eq(%w{ d g o }) } | |
it { splitter.normalize('hotdog').should eq(%w{ d g h o o t }) } | |
end | |
describe "#substractFrom " do | |
context "when no multiple characters are in the input string" do | |
it { splitter.substractFrom(%w{ a b c d}, %w{ a b c }).should eq(%w{ d }) } | |
end | |
context "when multiple characters are included" do | |
let(:input) { splitter.normalize('hotdog') } | |
let(:word1) { splitter.normalize('hot') } | |
let(:word2) { splitter.normalize('dog') } | |
it { splitter.substractFrom(%w{ a b c d}, %w{ a b c }).should_not be_nil } | |
it { splitter.substractFrom(%w{ a b c d}, %w{ a b c z }).should be_nil } | |
subject { splitter.substractFrom(input, word1) } | |
it "should calculate 'hotdog' - 'hot' = 'dog'" do | |
should eq(word2) | |
end | |
it "should say 'documenting' includes 'tuning'" do | |
splitter.substractFrom(splitter.normalize("documenting"), splitter.normalize("tuning")).should_not be_nil | |
end | |
end | |
end | |
end | |
class AnagramPairFinder | |
def initialize(dict) | |
@dict = {} | |
dict.each { |word| @dict[normalize(word)] = word } | |
@dict.freeze | |
end | |
def normalize(word) | |
word.split(//).sort | |
end | |
def lookup(word) | |
word_normalized = normalize(word) | |
@dict.each_pair do |key, value| | |
remaining = substractFrom(word_normalized, key) | |
if !remaining.nil? ## yes, key was contained in word_normalized | |
return [value, @dict[remaining]].sort if @dict.key? remaining | |
end | |
end | |
nil | |
end | |
def substractFrom(charArrayLong, charArrayShort) | |
result = charArrayLong.clone | |
charArrayShort.each do |char| | |
index = result.index(char) | |
return nil if index.nil? | |
result.delete_at(index) | |
end | |
result | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment