02 August 2013

Algorithmathon

Today’s goal will be to write algorithms for a few different types of string manipulations. Our first goal will be to remove all characters, in an array, from a string. The second will be to reverse all of the characters in a string. Third will be to convert a string to an integer. Finally we will end with converting an integer to a string. The Ruby String class already has some methods that cover this functionality. We will pretend that the do not exist and write our own.

To solve our first problem we will use a straight linear approach which will have a cost at worst of the length of the string times the length of the array. Depending on how Array#include is implemented it might be as low as just the length of the array. Though this would incur additional storage costs.

To reverse all of the characters in a string we will utilize recursion. By counting down from the outside in we will have a cost of log(n).

Our third goal can be achieved by converting each character in the string to its ordinal value. These values start with 48 for "0" on up to "9". Thus if we subtract 48 we have the numeric value represented by the character. Then we just have to multiply it by 10 raised to the power of the character position starting from the right.

The final method is the reverse of our third goal. We will use division and modulus to break apart our number. When we add 48 to it we will have the ordinal value of our characters. Then we simply need to concatenate the characters together.

Of course we must have our RSpec tests done first.

algorithm_string_spec.rb
``````require 'spec_helper'

describe AlgorithmString do

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

it "should have method 'string_to_integer'" do
AlgorithmString.method_defined?(:string_to_integer).should be_true
end
it "should have method 'integer_to_string'" do
AlgorithmString.method_defined?(:integer_to_string).should be_true
end
end

describe "Instance" do

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

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

it "should return nil when 'new_remove()' is called" do
@string.new_remove(nil).should be_nil
end

it "should return 'AAAA' when 'new_remove([B,C,D])' is called" do
@string.new_remove(['B','C','D']).should == 'AAAA'
end

it "should return 'CBACBACBACBA' when 'new_reverse!()' is called" do
@string.new_reverse!().should == 'CBACBACBACBA'
end

it "should return 'ABCABCDABCABC' when 'new_reverse!()' is called" do
@string = AlgorithmString.new('ABCABCDABCABC')
end

it "should return -245 when 'string_to_integer()' is called" do
@string = AlgorithmString.new('-245')
@string.string_to_integer.should == -245
end

it "should return '-245' when 'integer_to_string(-245)' is called" do
@string = AlgorithmString.new('test')
@string.integer_to_string(-245).should == '-245'
end
end

end``````

The code to satisfy our tests.

algorithm_string.rb
``````class AlgorithmString < String

#Remove all characters from string
#
#+character_array+:: An array of characters to be removed from the string.
def new_remove(character_array)
unless character_array.nil? || !character_array.class.name.eql?('Array')
return_io=StringIO.new()
self.each_char { | char |
unless character_array.include?(char)
return_io.putc char
end
}
return_value = return_io.string
end
return_value
end

#Reverse the order of the characters in the string
def new_reverse!()
unless self.length < 1
reverse_by_recursion(0)
end
end

#this method will return the integer value of the current
#string or throw and "Invalid integer format" exception
def string_to_integer
power_counter = self.length - 1
return_value=0
is_negative=false
self.each_char { | character_number |
if character_number == "-"
is_negative=true
else
character_value = character_number.chr.ord
character_value = character_value - 48
if character_value > -1 && character_value < 10
return_value = return_value + (character_value * (10 ** power_counter))
else
raise "Invalid integer format"
end
end
power_counter = power_counter - 1
}
if is_negative
return_value = return_value * -1
end
return_value
end

#Converts and integer to a string
#
#+integer_value+:: An integer
def integer_to_string(integer_value)
return_value=""
prefix = ''
if integer_value < 0
prefix="-"
integer_value = integer_value * -1
end
while integer_value > 0
return_value = ((integer_value % 10) + 48).chr + return_value
integer_value = integer_value / 10
end
prefix + return_value
end

private

#helper method to new_reverse!() counts the number of
#recursions.  Switches characters from the end to the front
#working from the ends to the middle.
#
#+counter+:: Tracks the distance from the ends.
def reverse_by_recursion(counter)
unless counter >= (self.length / 2)
holder=self[counter]
self[counter]=self[self.length - 1 - counter]
self[self.length - (1 + counter)]=holder
counter = counter + 1
reverse_by_recursion(counter)
end
self
end

end``````

If you want to earn bonus points convert the fourth method to utilize StringIO. This would lessen the overhead of string concatenation.

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