Algorithmathon Day 14: String Manipulations

Created: 2 August 2013  Modified:

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')
      @string.new_reverse!().should == 'CBACBADCBACBA'
    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.

tags: Algorithm - Algorithmathon - RSpec - Ruby
   Less Is More