Book Notes: Practical Object Oriented Design in Ruby

I recently read Practical Object-Oriented Design in Ruby by Sandi Metz. A fantastic book to help bridge the gap between theory and implementation of design. I highly recommend this book even for non Rubyists. Below are bullet points to help remember key points in the book.

    • General
      • Make design decisions based on what you know now.
      • Design behavior not data.
      • Checking types or classes indicates an opportunity for inheritance or interfaces.
      • Inject dependencies.
      • Use factories to centralize design that otherwise would be spread throughout multiple classes. Such as instantiating classes to be injected.
      • Use shallow inheritance hierarchies
      • Favor composition over inheritance when in doubt.
      • When dependencies cannot be eliminated then they should be isolated from the rest of the code.
      • Dependency has a direction and should be pointed toward the code least likely to change.
      • Abstractions are less likely to change than concretions.
      • A diagram of object interaction should look like a tree not a mesh.
      • Use sequence diagrams to determine the classes you need.
    • Methods
      • Should have single responsibility
      • Large methods indicate the need to be reduced to multiple smaller methods
      • Many private methods indicate the possible need for a new class.
      • Method parameter order is a dependency.
    • Interfaceshttp://www.chrislynch.info/cgi-sys/suspendedpage.cgi
      • The messages sent between objects are how they interface.
      • Interfaces are roles shared by otherwise unrelated objects.
    • Classes
      • Should have a single responsibility
      • Use inheritance when classes are “is a”
      • Use composition when classes “has a”
      • May have roles which translate to interfaces. These roles may be implicit rather than explicit.
      • Use dependency injection rather than explicitly using classes in other classes.
      • Use Hashes for parameters. This helps prevent dependencies on method parameter order.
      • Use template design pattern when using inheritance.
      • Template design pattern should use hooks instead of using “super”. User of super creates dependency.
    • Testing
      • Test from the general to the specific.
      • Test only the public interface of a class.
      • Use modules/mixins in test to verify interfaces (modules/mixins) in the code. Then include in all classes implementing interface.
      • Use modules/mixins in test to verify super classes. These then can be included in subclasses.
      • Use a singular module/mixin to verify subclasses act correctly in relation to super class. Then include in all subclasses.
    • SOLID
      • Single Responsibility
      • Open for extension, but Closed for modification
      • Liskov Substitution:  Subclasses stand in for parent classes
      • Interface Segregation:  Clients should only know the methods they use.   (Adapter pattern?)
      • Dependency Inversion

Ruby Magick: Include and Extend

While wandering lost through the strange land of Rails code I stumbled upon some many bits of code. One particular bit that crossed my path was the /railties/lib/rails/generators/migration.rb code.

migration.rb

require 'active_support/concern'
require 'rails/generators/actions/create_migration'
module Rails
  module Generators
    # Holds common methods for migrations. It assumes that migrations has the
    # [0-9]*_name format and can be used by another frameworks (like Sequel)
    # just by implementing the next migration version method.
    module Migration
      extend ActiveSupport::Concern
      attr_reader :migration_number, :migration_file_name, :migration_class_name
      module ClassMethods
        def migration_lookup_at(dirname) #:nodoc:
          Dir.glob("#{dirname}/[0-9]*_*.rb")
        end
        def migration_exists?(dirname, file_name) #:nodoc:
          migration_lookup_at(dirname).grep(/d+_#{file_name}.rb$/).first
        end
##########code omitted here#################

    end
  end
end

Having never seen “ClassMethods” module in use, I decided to investigate. It turns out that this is a design pattern prevalent in Rails. Confused I decided to investigate using code examples. First we need to understand Class and Instance methods. Class methods are methods that belong to the class and are not available to an object instantiated from the class. Instance methods are just the opposite. They are methods that belong to an instantiated object but not to the class. The following code will illustrate this point.

ruby/language/include-extend$ ruby expected.rb

language/include-extend/expected.rb

class  Expected
  #Putting self in front of the method name makes it a class method
  def self.class_method
    puts "Expected.class_method succeeded!"
  end

  def instance_method
    puts "expected.instance_method succeeded!"
  end

end

puts ""
puts "Expected Code"
puts "Begin using class"
puts "--------------------------------------"
begin
  puts Expected.class_method
  puts Expected.instance_method
rescue
  puts "Expected.instance_method failed!"
  puts ""
end

puts "Begin using instantiated object"
puts "--------------------------------------"
expected = Expected.new

begin
  puts expected.instance_method
  puts expected.class_method
rescue
  puts "expected.class_method failed!"
end

Which when run gives us the following results

run expected.rb in command line

bash-4.2$ ruby expected.rb 

Expected Code
Begin using class
--------------------------------------
Expected.class_method succeeded!

Expected.instance_method failed!

Begin using instantiated object
--------------------------------------
expected.instance_method succeeded!

expected.class_method failed!

Having the basics under our belt let us take another step and talk about include and extend. Include and extend are used to include Modules into classes and other modules. Include “includes” instance methods and extends “includes” class methods. It can actually get quite a bit more complicated than this simple explanation. We will come back to this at the end.

Using include and extend we can write the following:

language/include-extend/using-module.rb

module UsingModule
  module InstanceMethods
    def instance_method
      puts "using_class.instance_method worked!"
    end
  end

  module ClassMethods
    def class_method
      puts "UsingClass.class_method worked!"
    end
  end
end


class UsingClass
  include UsingModule::InstanceMethods
  extend UsingModule::ClassMethods

end

puts ""
puts "Using Module Code"
puts "Begin using class instance"
puts "-------------------------------"
using_class = UsingClass.new()

begin
  puts using_class.instance_method
  puts using_class.class_method
rescue
  puts "using_class.class_method failed!"
end

puts ""
puts "Begin using class"
puts "-------------------------------"

begin
  puts UsingClass.class_method
  puts UsingClass.instance_method
rescue
  puts "UsingClass.instance_method failed!"
end

Which gives us similar results as expected.rb.

run using-module.rb in command line


bash-4.2$ ruby using-module.rb 

Using Module Code
Begin using class instance
-------------------------------
using_class.instance_method worked!

using_class.class_method failed!

Begin using class
-------------------------------
UsingClass.class_method worked!

UsingClass.instance_method failed!

Using-module.rb while an interesting experiment isn’t what you will likely see. You are more likely to see the use of only a ClassMethods sub module along with included class method as shown next.

language/include-extend/confusing-code.rb

module ConfusingModule
  def self.included(base)
#    This commented out code is also seen.
#    The results are the same as the line below it.
#    base.send :extend, ClassMethods
    base.extend(ClassMethods)
  end

  def instance_method
    puts "using_class.instance_method worked!"
  end

  module ClassMethods
    def class_method
      puts "ConfusingClass.class_method worked!"
    end
  end
end


class ConfusingClass
  include ConfusingModule

end

puts ""
puts "Confusing Code"
puts "Begin using class instance"
puts "-------------------------------"
confusing_class = ConfusingClass.new()

begin
  puts confusing_class.instance_method
  puts confusing_class.class_method
rescue
  puts "confusing_class.class_method failed!"
end

puts ""
puts "Begin using class"
puts "-------------------------------"

begin
  puts ConfusingClass.class_method
  puts ConfusingClass.instance_method
rescue
  puts "ConfusingClass.instance_method failed!"
end

Which once again will produce similar results.

Terminal window in mysecurity directory


bash-4.2$ ruby confusing-code.rb 

Confusing Code
Begin using class instance
-------------------------------
using_class.instance_method worked!

confusing_class.class_method failed!

Begin using class
-------------------------------
ConfusingClass.class_method worked!

ConfusingClass.instance_method failed!

Clear as mud? Good! I highly recommend playing with this code to get a more intuitive grasp of how it works. We now proceed to how Rails does all of this with hidden magic. It does this with ActiveSupport::Concern. This next code example requires you to have the ActiveSupport gem installed.

language/include-extend/concerned-code.rb

require 'active_support'

module ConcernedModule
  extend ActiveSupport::Concern

  def instance_method
    puts "concerned_class.instance_method worked!"
  end

  module ClassMethods
    def class_method
      puts "ConcernedClass.class_method worked!"
    end
  end
end


class ConcernedClass
  include ConcernedModule

end

puts ""
puts "Concerned Code"
puts "Begin concerned class instance"
puts "-------------------------------"
concerned_class = ConcernedClass.new()

begin
  puts concerned_class.instance_method
  puts concerned_class.class_method
rescue
  puts "concerned_class.class_method failed!"
end

puts ""
puts "Begin concerned class"
puts "-------------------------------"

begin
  puts ConcernedClass.class_method
  puts ConcernedClass.instance_method
rescue
  puts "ConcernedClass.instance_method failed!"
end

Code which once again produces similar results.

Terminal window in mysecurity directory


bash-4.2$ ruby concerned-code.rb 

Concerned Code
Begin concerned class instance
-------------------------------
concerned_class.instance_method worked!

concerned_class.class_method failed!

Begin concerned class
-------------------------------
ConcernedClass.class_method worked!

ConcernedClass.instance_method failed!

ActiveSupport::Concern, among other things, searches for a ClassMethods sub module and extends it. This brings us to where we can understand a bit more of Rails code and the Ruby magick it employs. Finally lets look at one last piece of code that can confuse the use of extend. What happens if we call extend on an object?

language/include-extend/extend-confusion.rbb

module MoreConfusionModule

  def instance_method
    puts "more_confusion_class.instance_method worked!"
  end

  module ClassMethods
    def class_method
      puts "MoreConfusionClass.class_method worked!"
    end
  end
end

module Diabolical
  module ClassMethods
    def confuse
      puts "Haha i am not a class method!"
    end
  end
end



class MoreConfusionClass
  include MoreConfusionModule

end

puts ""
puts "MoreConfusion Code"
puts "Begin more_confusion class instance"
puts "-------------------------------"
more_confusion_class = MoreConfusionClass.new()

more_confusion_class.extend(Diabolical::ClassMethods)


begin
  puts more_confusion_class.instance_method
  puts more_confusion_class.class_method
rescue
  puts "more_confusion_class.class_method failed!"
end

puts ""
puts "Begin more_confusion class"
puts "-------------------------------"

begin
  puts MoreConfusionClass.class_method
  puts MoreConfusionClass.instance_method
rescue
  puts "MoreConfusionClass.instance_method failed!"
end


puts "-------------------------------"
puts more_confusion_class.confuse

The results of running this class may be somewhat suprising.

Terminal window in mysecurity directory


bash-4.2$ ruby extend-confusion.rb 

MoreConfusion Code
Begin more_confusion class instance
-------------------------------
more_confusion_class.instance_method worked!

more_confusion_class.class_method failed!

Begin more_confusion class
-------------------------------
MoreConfusionClass.instance_method failed!
-------------------------------
Haha i am not a class method!

The confuse method defined in Diabolical::ClassMethods mocks us! Extend assigns the methods to the object which is calling it. You do remember that in Ruby classes are also objects? So if you call extend from an object it will assign the methods to the object not the class.

Below are links to sources the first of which I found to be a fantastic resource.

Algorithmathon Day 19: Combinations

The challenge for us today is to find all the possible combinations of a set of numbers. When determining combinations the order is not important. This means that 123 is the equivalent of 321. The solution of this problem reminds me of the old adage about taking one step back for every two steps forward. Which in effect is what we do to determine the possible combinations. The solution is very similar to the Permutations of a String solution. The difference being that we start in position that is equal to the combination length desired. We work our way backwards from this position to the beginning of the array/string. Every step we make backwards we find the permutations from that location forwards. When it is all done you have your combinations.

We first prepare our RSpec tests.
algorithm_array_spec.rb

require 'spec_helper'

describe AlgorithmArray do

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

  describe "Instance" do
    before(:each) do
    end

    it "should return 3 when '[].combinations(2).length' is called" do
      @array = AlgorithmArray.[](1,2,3)
      @array.combinations(2).length.should == 3
    end

    it "should return 10 when '[].combinations(3).length' is called" do
      @array = AlgorithmArray.[](1,2,3,4,5)
      @array.combinations(3).length.should == 10
    end

    it "should return 20 when '[].combinations(3).length' is called" do
      @array = AlgorithmArray.[](1,2,3,4,5,6)
      @array.combinations(3).length.should == 20
    end

    it "should return 15 when '[1,2,3,4,5,6].combinations(4).length' is called" do
      @array = AlgorithmArray.[](1,2,3,4,5,6)
      @array.combinations(4).length.should == 15
    end
  end
end

Finally the code to satisfy our tests.
algorithm_array.rb

class AlgorithmArray < Array
  attr_reader :iteration_count

  #
  #  Finds the possible combinations of elements in the array.
  # * *Args*
  #   - +combination_length+ -> The length of the combinations to be found.
  # * *Returns*
  #   - An array containing all the possible combinations.
  def combinations(combination_length)
    @iteration_count=0
    @level=0
    unless combination_length.nil? || combination_length < 1
      positions = combination_length - 1
      return_array = Array.new()
      build_array = self[0..positions]
      return_array[return_array.length]= build_array.join()
      build_array.pop()
      positions.downto(0) do | position |
        combinate_by_recursion(return_array,build_array,positions,position,position+1)
        @level = @level - 1
        build_array.pop()
      end
      return_array
    end
  end


  #
  #  Using recursion finds the remaining possible combinations of elements in the array.  The first
  #  combination is found in the combinations method.  The combinations method calls this method.
  # * *Args*
  #   - +return_array+ -> An array referenced to act as a container for the combinations.
  #   - +build_array+ ->  An array acting as a stack to hold the combination currently under construction.
  #   - +positions+ -> An integer that indicates the length of the combination
  #   - +current_position+ ->  The current position in the array being changed.
  #   - +end_position+ -> The position in the array whose value is being pushed into the current position.
  # * *Returns*
  #   - An array containing all the possible combinations.
  def combinate_by_recursion(return_array,build_array,positions,current_position,end_position)
    @level = @level + 1
    if positions < current_position
      return_array[return_array.length]= build_array.join()
      return
    end

    while end_position < self.length
      @iteration_count = @iteration_count + 1
      build_array.push(self[end_position])
      combinate_by_recursion(return_array,build_array,positions,current_position + 1,end_position + 1)
      @level = @level - 1
      build_array.pop()
      end_position=end_position+1
    end
  end  
end

Algorithmathon Day 18: Longest Common Substring Revisited

We previously found the Longest Common Substring (LCS) using a trie on Day 13. Today our goal is to solve this problem a different way. This solution is O(n2) because it involves a loop within a loop. We will scan through the first string and for every character we will scan every character in the second string for a match. If a match is found we will then scan the next characters in both strings for a match. This means that the worst case scenario is when neither string has a matching sub-string. The solution should work something like this.

  1. Read next character from string one.
  2. Go to the beginning of string two.
  3. Read next character from string two.
  4. If the characters match read the next characters from both strings. Otherwise go to step 1.
  5. If the characters match go to step 3. Otherwise record the substring and to to step 1.

As always we begin with our RSpec tests.

algorithm_string_spec.rb

require 'spec_helper'

describe AlgorithmString do

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

  describe "Instance" do
    describe "Longest common substring method tests" do
      it "should return 'bcd' when ABCD.longest_common_substring(BCDE)  is called" do
        a_string= AlgorithmString.new('ABCD')
        a_string.longest_common_substring('BCDE').should == 'BCD'
      end

      it "should return 'try' when TRY.longest_common_substring(RETRY)  is called" do
        a_string= AlgorithmString.new('TRY')
        a_string.longest_common_substring('RETRY').should == 'TRY'
      end 

       it "should return 'FGH' when ABCDFGHXYZ.longest_common_substring(TSVPFGHARS)  is called" do
        a_string= AlgorithmString.new('ABCDFGHXYZ')
        a_string.longest_common_substring('TSVPFGHARS').should == 'FGH'
      end     
    end
  end
end

Now for our solution.

algorithm_string_spec.rb

class AlgorithmString < String

  #Find the longest common substring with the 
  #string_to_compare parameter.
  # * *Args*
  #   - +string_to_compare+ -> A string which is compared to this string instance to find the longest common substring
  # * *Returns*
  #   - A string that is the first longest common substring found. 
  def longest_common_substring(string_to_compare)
    @longest_begin = -1
    @longest_length = 0    
    unless self.length < 1 || string_to_compare.nil? || string_to_compare.length < 1
      @current_outer = 0
      while (@current_outer + @longest_length) < self.length
        @current_inner = 0
        while @current_inner < string_to_compare.length
          if self[@current_outer] == string_to_compare[@current_inner]
            process_first_character_match(string_to_compare)
            break
          end
          @current_inner = @current_inner + 1
        end
        @current_outer = @current_outer + 1
      end
    end
    self.slice(@longest_begin,@longest_length)
  end


  private

    #  Called from longest_common_substring when a first character match is found.
    #  Advances to the next character in both strings to look for a match.
    #
    #   - +string_to_compare+ -> A string which is compared to this string instance to find the longest common substring
    #
    # * *Returns*
    #   - A string that is the matching characters found. 
    def process_first_character_match(string_to_compare)
      current_begin=@current_outer
      current_length=1
      @current_outer = @current_outer + 1
      @current_inner = @current_inner + 1
      while @current_outer < self.length && @current_inner < string_to_compare.length
        if self[@current_outer] == string_to_compare[@current_inner]
            current_length=current_length + 1
        else
          break
        end
        @current_outer = @current_outer + 1
        @current_inner = @current_inner + 1
      end      
      if current_length > @longest_length
         @longest_begin=current_begin
         @longest_length = current_length
      end      
    end
end

Algorithmathon Day 17: Telephone Words

It is easier for most humans to remember words rather than to remember numbers. Having only 10 numbers and 26 letters the numbers would need to double or triple up with letters. The history of the telephone keypad is interesting. For example it wasn’t until mobile telephones became ubiquitous that the world was even using the same letters for the same numbers. The results of this world standard makes little since to me. We will view the correlations between letters and numbers in our code.

Our challenge will be to write a small program to list out the possible combinations of letters for a telephone number. I think of this problem as being a series of wheels with letters on the circumference. If each wheel represents a number then some wheels will have no letters on it while some will have three or even four letters. The first wheel starts spinning and when it reaches the first letter it starts spinning the the second wheel which starts spinning the third wheel and so on. For a seven digit number the cost could range from 7 to 47. The first being the case for the number 111-1111 and the second being 999-9999. Most numbers will fall towards the middle of these two extremes.

A solution will involve steps similar to the below.

  1. Read the number
  2. Read the first/next letter and place it in a stack
  3. If there is another number go to step 1.
  4. Remove the last letter from the stack
  5. Go to step 2

Seems pretty straightforward let’s hop right into build our RSpec tests.

telephone_words_spec.rb

require 'spec_helper'

describe TelephoneWords do

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

  describe "Instance" do

    it "should not return nil when 'build_words([2,2,2])' is called" do
      telephone_words = TelephoneWords.new()
      number_array = [2,2,2]
      telephone_words.build_words(number_array).should_not be_nil
    end

    it "should return 27 when 'build_words([2,2,2]).length' is called" do
      telephone_words = TelephoneWords.new()
      number_array = [2,2,2]
      telephone_words.build_words(number_array).length.should == 27
    end 

    it "should return 27 when 'build_words([1,2,2,2]).length' is called" do
      telephone_words = TelephoneWords.new()
      number_array = [1,2,2,2]
      telephone_words.build_words(number_array).length.should == 27
    end   

    it "should return 27 when 'build_words([2,2,2,1]).length' is called" do
      telephone_words = TelephoneWords.new()
      number_array = [2,2,2,1]
      telephone_words.build_words(number_array).length.should == 27
    end 

    it "should return 27 when 'build_words([2,1,2,2]).length' is called" do
      telephone_words = TelephoneWords.new()
      number_array = [2,1,2,2]
      telephone_words.build_words(number_array).length.should == 27
    end  

    it "should return 2916 when 'build_words([3,5,2,2,9,6,6]).length' is called" do
      telephone_words = TelephoneWords.new()
      number_array = [3,5,2,2,9,6,6]
      telephone_words.build_words(number_array).length.should == 2916
    end  
  end
end

Finally our solution.

telephone_words.rb

class TelephoneWords < Array
  
  def initialize()
    @number_dictionary = { 0=> [], 1 => [], 2 => ['A','B','C'], 3 => ['D','E','F'], 4 => ['G','H','I'], 5 => ['J','K','L'], 6 => ['M','N','O'], 7 => ['P','Q','R','S'], 8 => ['T','U','V'], 9 => ['W','X','Y','Z'] }
  end


  #Find all possible letter combinations from a telephone number.
  #
  #* *Args*    :
  #  - +telephone_number+ -> The telephone number to be analyzed.
  #* *Returns* :
  #  - An array containing strings representing all the possible letter combinations.
  def build_words(telephone_number)
    if telephone_number.nil? || telephone_number.length < 1
      return
    end
    return_results = Array.new()
    build_words_by_recursion(telephone_number,Array.new(),return_results,0)
    return return_results
  end

  private
    
  #Find all possible letter combinations from a telephone number by recursing
  #through the possible letter combinations.
  #
  #* *Args*    :
  #  - +telephone_number+ -> The telephone number to be analyzed.
  #  - +current_word+ -> The combinations of letters currently being put together to build a word.
  #  - +return_results+ -> An array used to store the combinations of letters
  #  - +depth+ -> Tracks which telephone number is currently being examined.
  #* *Returns* :
  #  - An array containing strings representing all the possible letter combinations.
    def build_words_by_recursion(telephone_number,current_word,return_results,depth)
      if depth > (telephone_number.length - 1)
        return_results[return_results.length]=current_word.join()
      end
      unless telephone_number[depth].nil?
        if telephone_number[depth] == 0 || telephone_number[depth] == 1
          current_word.push(telephone_number[depth].to_s)
          build_words_by_recursion(telephone_number,current_word,return_results,depth + 1)
          current_word.pop()
        else
          @number_dictionary[telephone_number[depth]].each { | letter |
            current_word.push(letter)
            build_words_by_recursion(telephone_number, current_word, return_results, depth + 1)
            current_word.pop()
          }          
        end
      end
    end
end

Algorithmathon Day 16: Permutations of a String

Day 16’s goal has turned out to be surprisingly fascinating. Permutations of a string have a solution that is a factor of the length of the string. This means that a string with four characters will have 24 solutions which is the result of 4 x 3 x 2 x 1. This then can be our ideal goal and is represented by n!. We want to find the permutations of a string with the number of operations being equal or close to the multiplied factors of the string length.

This goal turned out to be difficult to achieve. In fact we will see that we do not achieve it. We will explore three solutions each of which provides a somewhat improved solution to the prior one. Even so we will not reach our goal. Searching for the solution was very interesting and I only stopped because I needed to move on to other subjects.

The number of iterations is the length of the string raised to the power of the number of factors in the string. A string of length 3 has 6 permutations. Which is the factorial of 3. 3 x 2 x 1 = 6. Research suggests an answer of n! x n x n.

We should now construct our RSpec tests. This time around we will leave one test failing because we never reach our ideal goal of n! iterations.

algorithm_string_spec.rb

require 'spec_helper'

shared_examples "a permutation" do | target_string, target_method, goal |

  describe "When #{target_method}' is called" do
    before(:each) do
      @string = AlgorithmString.new(target_string)
    end

    it "should not return nil" do
      @string.send(target_method).should_not be_nil
    end

    it "should return #{goal}" do
      @string.send(target_method).length.should == goal
    end 

    it "should return #{goal} when 'iteration_count' is called" do
      @string.send(target_method)
      @string.iteration_count.should == goal
    end 

    it "should match @verify_array" do
      verify_array = target_string.chars.to_a.permutation.map(&:join)
      local_array = @string.send(target_method)
      verify_array.each { | value |
        local_array.include?(value).should be_true
      }
    end
  end
end

describe AlgorithmString do  

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

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

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

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

  describe "Instance" do

    describe "'ABC' permutations" do
      it_should_behave_like "a permutation", "ABC","permutate", 6 
      it_should_behave_like "a permutation", "ABC","permutate2", 6 
      it_should_behave_like "a permutation", "ABC","permutate3", 6 

    end
    describe "'ABCD' permutations" do
      it_should_behave_like "a permutation", "ABCD","permutate", 24 
      it_should_behave_like "a permutation", "ABCD","permutate2", 24 
      it_should_behave_like "a permutation", "ABCD","permutate3", 24

    end
    describe "'ABCDE' permutations" do
      it_should_behave_like "a permutation", "ABCDE","permutate", 120
      it_should_behave_like "a permutation", "ABCDE","permutate2", 120
      it_should_behave_like "a permutation", "ABCDE","permutate3", 120

    end    
  end 
end 

Our code to meet these tests.

algorithm_string.rb

class AlgorithmString < String
  attr_reader :iteration_count

  #Determine all possible orderings of characters in a string
  #
  #  - returns an array with all the possible orderings.
  def permutate()
    @iteration_count=0
    return_array = Array.new()
    permutate_by_recursion(return_array,Array.new(),Array.new(),0)
    return_array
  end

  def permutate2()
    @iteration_count=0    
    return_array = Array.new()
    string_array = self.split('')
    permutate_by_recursion2(return_array,string_array,0)
    return_array
  end

  def permutate3()
    @iteration_count=0    
    return_array = Array.new()
    string_array = self.split('')
    permutate_by_recursion3(return_array,string_array,"")
    return_array
  end  

  private
  def permutate_by_recursion(return_array,build_array,tracking_array, current_position)
    final_position= self.length - 1

    if current_position > final_position
      return_array[return_array.length]=build_array.join()
      return
    end
    
    for i in 0..final_position
      @iteration_count = @iteration_count + 1
      unless tracking_array[i]
        build_array.push(self[i])
        tracking_array[i]=true
        permutate_by_recursion(return_array,build_array,tracking_array,current_position + 1)
        build_array.pop()
        tracking_array[i]=false
      end
    end
  end

  def permutate_by_recursion2(return_array, string_array, current_position)
    final_position= self.length - 1

    if current_position > final_position
      return_array[return_array.length]=string_array.join()
      return
    end
    
    for i in current_position..final_position
      @iteration_count = @iteration_count + 1
      switch_character(string_array,current_position,i)
      permutate_by_recursion2(return_array,string_array,current_position + 1)
      switch_character(string_array,current_position,i)
    end
  end  

  def switch_character(string_array,first,second)    
    value_holder=string_array[second]
    string_array[second]=string_array[first]
    string_array[first]=value_holder
  end

  def permutate_by_recursion3(return_array, string_array, string_value)
    if string_array.length == 1
      return_array[return_array.length]=string_value + string_array[0]
      return
    end
    string_array.each_with_index { | value, index |
      @iteration_count = @iteration_count + 1
      prefix = string_value + value
      temp_array = string_array.clone()
      temp_array.delete_at(index)
      permutate_by_recursion3(return_array, temp_array, prefix)
    }

  end 
  
end

As you can see the first solution permutate was not very efficient and required iterations greater than n3 and n! x n2. Our second solution permutate2 switches values around with the string and is able to do considerably better. It solves the problem somewhere between n2 and n x n2. This solutions is my favorite because it seems the least resource intensive. Finally we have permutate3 which uses the fewest iterations/recursive calls. The difference is not insignificant and the this solution could also be applied to permutate2 to reduce its number of recursive calls.

Algorithmathon Day 15: Binary Search

On day 15 we will be looking into the Binary Search. It is a relatively straight forward algorithm for searching ordered data. Its a simple process where you pick an arbitrary location to start. You compare the value you are searching for with the value from the location selected. If the search value is higher you pick a value to the right for the next search. The search value might be lower in which case you would pick a value to the left. The key is to track the highest and lowest known value locations and to pick the middle location between them. This would work something like the following.

  1. The first value and the last value are the low and high locations.
  2. Pick the value in the middle of the the high and low values. Call this current value.
  3. If the high and low values are equal then return nothing.
  4. If the high location is greater than the number of values return nothing
  5. If the low location is less than the first value location return nothing
  6. If the search value is less than the current value make the current value location the high location and go to step 2.
  7. If the search value is greater than the current value make the current location the low location and go to step 2.
  8. Return the value location

As always we begin with our RSpec tests.

algorithm_array_spec.rb

require 'spec_helper'

describe AlgorithmArray do

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

  describe "Instance" do


    describe "Start search from default location" do
      before(:each) do
        @array = AlgorithmArray.[](1,3,7,11,13,17,19,23,29,31)
      end

      it "should return 2 when 'new_find(7)' is called" do
        @array.new_find(7).should == 2
      end

      it "should return 0 when 'new_find(1)' is called" do
        @array.new_find(1).should == 0
      end

      it "should return 8 when 'new_find(29)' is called" do
        @array.new_find(29).should == 8
      end

      it "should return 4 when 'new_find(13)' is called" do
        @array.new_find(13).should == 4
      end 

      it "should return nil when 'new_find(443)' is called" do
        @array.new_find(443).should be_nil
      end      
    end

    describe "Start search from end location" do
      before(:each) do
        @array = AlgorithmArray.[](1,3,7,11,13,17,19,23,29,31)
      end

      it "should return 2 when 'new_find(7,9)' is called" do
        @array.new_find(7,9).should == 2
      end

      it "should return 0 when 'new_find(1,9)' is called" do
        @array.new_find(1,9).should == 0
      end

      it "should return 8 when 'new_find(29,9)' is called" do
        @array.new_find(29,9).should == 8
      end

      it "should return 4 when 'new_find(13,9)' is called" do
        @array.new_find(13,9).should == 4
      end    
    end

    describe "Start search from first location" do
      before(:each) do
        @array = AlgorithmArray.[](1,3,7,11,13,17,19,23,29,31)
      end

      it "should return 2 when 'new_find(7,0)' is called" do
        @array.new_find(7,0).should == 2
      end

      it "should return 0 when 'new_find(1,0)' is called" do
        @array.new_find(1,0).should == 0
      end

      it "should return 8 when 'new_find(29,0)' is called" do
        @array.new_find(29,0).should == 8
      end

      it "should return 4 when 'new_find(13,0)' is called" do
        @array.new_find(13,0).should == 4
      end    
    end    
  end

end

And the code to satisfy these tests.

algorithm_array_spec.rb

class AlgorithmArray < Array
  #Find the location of the matching element in the array.
  #
  #* *Args*    :
  #+search_object+:: The object being looked for.
  #* *Returns* :
  #  - an integer representing the location in the array the matching element is located.             
  def new_find(search_object,start_location=nil)
    if start_location.nil?
      start_location=self.length/2
    end
    new_find_by_recursion(search_object,start_location,self.length-1,0)
  end

  private

  #Find the location of the matching element in the array.
  #
  #* *Args*    :
  #+search_object+:: The object being looked for.
  #+search_location+:: The location in the array to compare values.
  #+high+:: Tracks the lowest location in the array that is know to contain a value greater than the search_object.
  #+high+:: Tracks the highest location in the array that is know to contain a value less than the search_object.
  #* *Returns* :
  #  - an integer representing the location in the array the matching element is located or nil if it is not found.               
  def new_find_by_recursion(search_object,search_location,high,low)
    if search_location >= self.length || search_location < 0 || high == low
      return
    end
    if self[search_location] < search_object
      low = search_location
      next_location = high - ((high - low)/2)
      new_find_by_recursion(search_object,next_location,high,low)
    elsif self[search_location] > search_object
      high = search_location
      next_location = low + ((high - low)/2)      
      new_find_by_recursion(search_object,next_location,high,low)
    else
      return_value = search_location
    end
  end

end

Algorithmathon Day 14: String Manipulations

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.

Algorithmathon Day 13: Trie Longest Common Substring

Instead of more String manipulations, as I indicated, we will be looking into Tries and the Longest Common Substring problem. A friend mentioned the problem to me and I became very interested in Tries as a result.

A Trie is a type of Tree that proves itself useful in string manipulation. To find the Longest Common Substring (LCS) a Suffix Trie is particularly useful. You create a Suffix tree by taking all the possible suffixes of a string and adding it to the Trie. We can find the LCS by adding all of the suffixes for two strings to a Trie with a label for each string. Then finding the longest path with both string labels will give us the LCS.

  1. Label strings
  2. Find all suffixes of the Strings
  3. Add all suffixes to the trie.
  4. Find next pointer which points to a branch with both string labels
  5. Follow the branch until it no longer has both string labels.
  6. Record the resulting sequence of letters
  7. If the sequence of letters is longer than the last sequence of letters remember it.
  8. Goto step 4

The cost of adding the strings should be n(n-1). For string S1 and string S2 this would be S1(S1 – 1) + S2(S2 – 1). If S1 represents the the longer string. The searching should have a cost of S1 + (26 * S2(S2 – 1)). Where S2 is the shorter of the two strings.

Descriptions of Suffix Tries often refer to them being Compressed Trie variant. To reduce complexity I have chose not to compress the trie.

We will need several RSpec tests to verify the needed functionality for adding strings to the Trie.

trie_spec.rb

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

    it "should have method 'add'" do
      Trie.method_defined?(:add).should be_true
    end 
  end

  describe "Instance" do


    describe "Add method tests" do
      before(:each) do
        @trie = Trie.new()
        @trie.add("ABCDEFG",0)
        @trie.add("DEFGHIJK",1)
      end

      it "should not return nil when 'root' is called" do
        @trie.root.should_not be_nil
      end

  
      it "should not return nil when 'root[65]' is called" do
        @trie.root[65].should_not be_nil
      end

      it "should not return nil when 'root[68]' is called" do
        @trie.root[68].should_not be_nil
      end    

      it "should not return nil when 'root[65][66]' is called" do
        @trie.root[65][66].should_not be_nil
      end        

      it "should not return nil when 'root[65][66][67][68][69][70][71]' is called" do
        @trie.root[65][66][67][68][69][70][71].should_not be_nil
      end

      it "should not return 1 when 'root[65][66][67][68][69][70][71].length' is called" do
        @trie.root[65][66][67][68][69][70][71].length.should == 2
      end 

      it "should not return 1 when 'root[65][66][67][68][69][70][71][0]' is called" do
        @trie.root[65][66][67][68][69][70][71][0].should == 1
      end

      describe "Markers indicating a specific string" do
        it "should not return nil when 'root[68][1]' is called" do
          @trie.root[68][1].should_not be_nil
        end 

        it "should return true when 'root[68][1][1]' is called" do
          @trie.root[68][1][1].should be_true
        end

        it "should return false when 'root[68][1][0]' is called" do
          @trie.root[68][1][0].should be_false
        end    
      end    
    end
  end
end

The code below satisfies these tests and provides the core functionality of our Trie. Rather than building a custom node Class we are using Arrays.

trie.rb

class Trie
  attr_reader :root

  def initialize()
    @root = Array.new(100)
  end

  def add(new_string,marker=0)
    unless new_string.nil? || new_string.length < 1
      add_by_recursion(@root,new_string,marker)
    end
  end

  private
  def add_by_recursion(current_node_array,new_string,marker)
    first_char=new_string.slice!(0)
    unless first_char.nil?
      first_char_number=first_char.chr.ord
      if current_node_array[first_char_number].nil?
        current_node_array[first_char_number] = Array.new()
      end 
      add_marker(current_node_array[first_char_number],marker)   
      add_by_recursion(current_node_array[first_char_number],new_string,marker)
    else
      current_node_array[0]=1
    end
  end

  def add_marker(current_node_array,marker)
    if current_node_array[1].nil?
      current_node_array[1]=Array.new()
    end
    current_node_array[1][marker]=true
  end

end

We now need to write a method to add all the suffixes of a string to the trie.

trie_spec.rb (excerpt)

#code omitted here
    it "should have method 'add_suffixes'" do
      Trie.method_defined?(:add_suffixes).should be_true
    end 
#code omitted here
    describe "Add_suffix method tests" do
      before(:each) do
        @trie = Trie.new()
        @trie.add_suffixes("ABCDEFG",0)
        @trie.add_suffixes("FGHIJK",1)
      end

      it "should not return nil when 'root[65]' is called" do
        @trie.root[65].should_not be_nil
      end      

      it "should not return nil when 'root[68]' is called" do
        @trie.root[68].should_not be_nil
      end

      it "should not return nil when 'root[72]' is called" do
        @trie.root[72].should_not be_nil
      end

      it "should not return nil when 'root[75]' is called" do
        @trie.root[75].should_not be_nil
      end

      it "should return false when 'root[69][1][1]' is called" do
        @trie.root[69][1][1].should be_false
      end

      it "should return true when 'root[69][1][0]' is called" do
        @trie.root[69][1][0].should be_true
      end

      it "should return true when 'root[70][1][0]' is called" do
        @trie.root[70][1][0].should be_true
      end

      it "should return true when 'root[70][1][1]' is called" do
        @trie.root[70][1][1].should be_true
      end

      it "should return true when 'root[71][1][0]' is called" do
        @trie.root[71][1][0].should be_true
      end

      it "should return true when 'root[71][1][1]' is called" do
        @trie.root[71][1][1].should be_true
      end

      it "should return false when 'root[72][1][0]' is called" do
        @trie.root[72][1][0].should be_false
      end

      it "should return true when 'root[72][1][1]' is called" do
        @trie.root[72][1][1].should be_true
      end

    end
#code omitted here

The code to satisfy these tests is quite straightforward. We add all possible suffixes of the string with a marker.

trie.rb

#code omitted here
  def add_suffixes(new_string,marker)
    unless new_string.nil? || new_string.length < 1
      string_end=new_string.length-1
      for counter in 0..string_end
        add(new_string[counter..string_end],marker)
      end
    end
  end
#code omitted here

Now all that is required is for us to find the LCS. Which we can do by searching for branches of the trie that have markers from both strings and returning the longest one.

trie_spec.rb (excerpt)

#code omitted here
    it "should have method 'longest_common_substring'" do
      Trie.method_defined?(:longest_common_substring).should be_true
    end    
#code omitted here
    describe "Longest common substring method tests" do
      it "should return 'bcd' when Trie.longest_common_substring(ABCD,BCDE)  is called" do
        trie= Trie.new()
        trie.longest_common_substring('ABCD','BCDE').should == 'BCD'
      end

      it "should return 'try' when Trie.longest_common_substring(TRY,RETRY)  is called" do
        trie= Trie.new()
        trie.longest_common_substring('TRY','RETRY').should == 'TRY'
      end 

       it "should return 'FGH' when Trie.longest_common_substring(ABCDFGHXYZ,TSVPFGHARS)  is called" do
        trie= Trie.new()
        trie.longest_common_substring('ABCDFGHXYZ','TSVPFGHARS').should == 'FGH'
      end     
    end
#code omitted here

Finally the code to satisfy the latest RSpec tests will give us our functionality.

trie.rb

#code omitted here
  def longest_common_substring(string_zero, string_one)
    add_suffixes(string_zero,0)
    add_suffixes(string_one,1)
    longest_common_substring_by_recursion()
  end
#code omitted here
  def longest_common_substring_by_recursion()
    root_end=@root.length-1
    latest_stack=Array.new()
    for counter in 65..root_end
      unless @root[counter].nil?
        if @root[counter][1][0] && @root[counter][1][1]
          tracking_stack=Array.new()
          tracking_stack.push(counter.chr)
          longest_common_substring_by_recursion_follow_branch(@root[counter],tracking_stack)
          if tracking_stack.length > latest_stack.length
            latest_stack = tracking_stack
          end
        end 
      end
    end
    latest_stack.join
  end

  def longest_common_substring_by_recursion_follow_branch(current_node_array,tracking_stack)
    array_end=current_node_array.length-1
    for counter in 65..array_end
      unless current_node_array[counter].nil?
        if current_node_array[counter][1][0] && current_node_array[counter][1][1]
          tracking_stack.push(counter.chr)
          longest_common_substring_by_recursion_follow_branch(current_node_array[counter],tracking_stack)
        end 
      end
    end
  end
#code omitted here

Configuring Weblogic 10.3 to use Struts2 Convention Plugin

It can be a bit of a pain to configure Weblogic Server to work with Struts2. This is to document what is needed so that I will have it recorded and it will also be available to others. Most of the heavy lifting was done by Amit in his article Getting Struts 2.1 to work in Weblogic 10.3. Several good comments as well.

There are some differences. I am using Maven 3 as my build tool and the Struts version is 2.3.8. First off you will need to have a Manifest file in your webapp/war in the META-INF folder. My Manifest file is completely empty. If you are familiar with Maven war projects it would have a path similar to the following

    project_root_folder/webapp/src/main/resources/META-INF/Manifest

You will also need to update your struts.properties file which will be located someplace similar to the below.

    project_root_folder/webapp/src/main/resources/struts.properties

The below entries will need to be added to the struts.properties file. The include jars entry basically adds the jar containing the actions back to the path. This is necessary because Weblogic Server changes several things about the EAR and WAR files that you deploy to the server.

struts.properties (excerpt)

#stuff omitted here
struts.convention.action.mapAllMatches = true
struts.convention.action.includeJars=.*?/_wl_cls_gen.*?jar(!/)?
struts.convention.action.fileProtocols=jar,zip
#stuff omitted here