26 July 2013

Algorithmathon

This entry starts a period of string manipulation. Today’s goal will be to return the first non-repeated character in a string. Ruby provides us with a String class that will be easy to subclass. If we have string "ABABCAB" we want to find the letter "C". One way to approach this is to compare every letter in the string to every other letter in the string. This however would have a n2 cost. If we shortened the string by one character on each pass we could reduce that to n * (n-1). Faster but still effectively n2. If however we use a hash to track and count the letters we can reduce this to n + 26. In this case we are assuming the use of only A through Z. Let’s jump right into the initial RSpec tests.

algorithm_string_spec.rb
require 'spec_helper'

describe AlgorithmString do

describe "Class" do
it "should have method 'first_nonrepeated'" do
AlgorithmString.method_defined?(:first_nonrepeated).should be_true
end
end

describe "Instance" do

before(:each) do
@string = AlgorithmString.new()
end

it "should not be nil" do
@string.should_not be_nil
end

end

end

A very basic class will satisfy these tests.

algorithm_string.rb
class AlgorithmString < String
def first_nonrepeated()

end
end

Now we need something with more substance so lets build some additional tests and the code to satisfy them.

algorithm_string_spec.rb (excerpt)
#code omitted here
it "should return nil when 'first_nonrepeated()' method is called" do
@string.first_nonrepeated().should_not be_nil
end

it "should return nil when 'first_nonrepeated()' method is called" do
@string.first_nonrepeated().should == 'C'
end
#code omitted here
algorithm_string.rb
class AlgorithmString < String
def first_nonrepeated()
string_array=self.to_s.split(//)
character_count=Hash.new()
return_value=nil
string_array.each_with_index { | character_outer, index |
if character_count[character_outer].nil?
character_count[character_outer] = 1
else
character_count[character_outer] = character_count[character_outer] + 1
end
}
character_count.each { | key, value |
if value < 2
return_value=key
end
}
return_value
end
end

We now have a working method that gives us a solution. Next time we will be adding a method which removes characters from a string.

Less Is More ~ Older posts are available in the archive.