Monday, 8 December 2014

DESING PATTERN BY EXAMPLE (IN RUBY) : TEMPLATE AND STRATEGY

Hi and welcome back everybody!

In this post I will show you an example of refactoring existing code to use the template and strategy design pattern in Ruby!

The application we are going to design today models a game where an oracle thinks of a number in a certain range (0...Max) and each participant to this game makes a number of guess to find out what this number is
After each guess, the oracle tells the participant if he is correct or not!

The starting code for this application is composed only by two classes and a main:


  • The participant class is the first class I am going to show you.  A participant tries to guess the 'secret' number using several different strategies:
 require_relative 'oracle.rb'  
 # Tries to guess the 'secret' number using several different strategies  
 class Participant  
  attr_reader :num_attempts   
  def initialize(oracle, max_num_attempts:10)  
   @oracle, @max_num_attempts = oracle, max_num_attempts  
   @num_attempts = 0  
  end  
  def reset  
   @num_attempts = 0  
  end  
  def play_randomly(lower,upper)  
   num = Kernel.rand(lower..upper)  
   @num_attempts+=1  
   while @oracle.is_this_the_number?(num)!=:correct  
    && (@num_attempts <= @max_num_attempts) do  
    num = Kernel.rand(lower..upper)  
    @num_attempts+=1  
   end  
   if (@num_attempts <= @max_num_attempts)  
    :success  
   else  
    fail  
   end  
  end  
  def play_linear(lower)  
   num=lower  
   @num_attempts+=1  
   while @oracle.is_this_the_number?(num)!=:correct  
    && (@num_attempts <= @max_num_attempts) do  
   end  
    num+=1  
    @num_attempts+=1  
   end  
   if (@num_attempts <= @max_num_attempts)  
    :success  
   else  
    fail  
   end  
  end  
  def play_smart_random(lower, upper)  
   num = Kernel.rand(lower..upper)  
   @num_attempts+=1  
   while ((result = @oracle.is_this_the_number?(num)) != :correct)  
    && (@num_attempts <= @max_num_attempts) do  
   end  
    if result == :less_than  
     upper = num-1  
    elsif result == :greater_than  
     lower = num+1  
    end  
    num = Kernel.rand(lower..upper)  
    @num_attempts+=1  
   end  
   if (@num_attempts <= @max_num_attempts)  
    :success  
   else  
    fail  
   end  
  end  
  def play_binary_search(lower, upper)  
   num = (lower+upper)/2  
   @num_attempts+=1  
   while ((result = @oracle.is_this_the_number?(num)) != :correct)  
    && (@num_attempts <= @max_num_attempts) do  
   end  
    if result == :less_than  
     upper = num-1  
    elsif result == :greater_than  
     lower = num+1  
    end  
    num=(lower+upper)/2  
    @num_attempts+=1  
   end  
   if (@num_attempts <= @max_num_attempts)  
    :success  
   else  
    fail  
   end  
  end  
  private  
  def fail  
   :fail  
  end  
 end  

  • The second class represent the Oracle, which generates the number the Participant is trying to guess:

 class Oracle  
  attr_writer :secret_number  
  def initialize(secret_num:0)  
    @secret_number = secret_num end  
    def is_this_the_number? num  if num == @secret_number  
    :correct  elsif num > @secret_number  
    :less_than  elsif num < @secret_number  
    :greater_than  end end  
 end  

As you can see the class Participant defines several methods to play this game highlighted in red. Each of them uses a different algorithm. The main method, wants to make a comparison between this algorithm and measure their performances:

 # Evaluate the performance of participants using different guessing strategies  
 require_relative 'oracle.rb'  
 require_relative 'participant.rb'  
 NUM_OF_RUNS = 8  
 oracle = Oracle.new  
 # evaluate random strategy  
 total_num_attempts = 0  
 total_num_failures = 0  
 homer = Participant.new(oracle, max_num_attempts: NUM_OF_RUNS*2)  
 1.upto(NUM_OF_RUNS) do |i|  
  oracle.secret_number = i  
  homer.reset  
  if homer.play_randomly(1,NUM_OF_RUNS)==:success  
   total_num_attempts += homer.num_attempts  
  else  
   total_num_failures += 1  
  end  
 end  
 puts "play randomly took on average   
 #{total_num_attempts/(NUM_OF_RUNS-total_num_failures)} attempts to succeed"  
 # evaluate linear strategy  
 total_num_attempts = 0  
 total_num_failures = 0  
 bart = Participant.new(oracle, max_num_attempts:NUM_OF_RUNS*2)  
 1.upto(NUM_OF_RUNS) do |i|  
  oracle.secret_number = i  
  bart.reset  
  if bart.play_linear(1)==:success  
   total_num_attempts += bart.num_attempts  
  else  
   total_num_failures += 1  
  end  
 end  
 puts "play_linear took on average #{total_num_attempts/(NUM_OF_RUNS-total_num_failures)} attempts to succeed"  
 total_num_attempts = 0  
 total_num_failures = 0  
 maggie = Participant.new(oracle, max_num_attempts:NUM_OF_RUNS*5)  
 1.upto(NUM_OF_RUNS) do |i|  
  oracle.secret_number = i  
  maggie.reset  
  if maggie.play_smart_random(1,NUM_OF_RUNS)==:success  
   total_num_attempts += maggie.num_attempts  
  else  
   total_num_failures += 1  
  end  
 end  
 puts "play_smart_random took on average #{total_num_attempts/(NUM_OF_RUNS-total_num_failures)} attempts to succeed"  
 total_num_attempts = 0  
 total_num_failures = 0  
 lisa = Participant.new(oracle, max_num_attempts:NUM_OF_RUNS*5)  
 1.upto(NUM_OF_RUNS) do |i|  
  oracle.secret_number = i  
  lisa.reset  
  if lisa.play_binary_search(1,NUM_OF_RUNS)==:success  
   total_num_attempts += lisa.num_attempts  
  else  
   total_num_failures += 1  
  end  
 end  
 puts "play_binary_search took on average #{total_num_attempts/(NUM_OF_RUNS-total_num_failures)} attempts to succeed"  


If we run this application we will get results similar to these ones:

play randomly took on average 4 attempts to succeed
play_linear took on average 4 attempts to succeed
play_smart_random took on average 1 attempts to succeed
play_binary_search took on average 4 attempts to succeed

As we said before, the Participant class defines different strategy for playing this game. This is totally fine and it will work producing some results that may change execution by execution; 
However, if we take a minute to reflect, we understand that the only aim of the class Participant, is to play this game! The concept that a Participant can play using different strategies should be extrapolated from the class Participant itself.

The strategy pattern (also known as the policy pattern) is a software design pattern that enables an algorithm's behavior to be selected at runtime. The strategy pattern:
  • defines a family of algorithms,
  • encapsulates each algorithm, and
  • makes the algorithms interchangeable within that family.

Strategy lets the algorithm vary independently from clients that use it. Strategy is one of the patterns included in the influential book Design Patterns by Gamma et al. that popularised the concept of using patterns in software design. In our specific case, we know that the class Participant know four different strategies to play this game, so we will extract each of this strategy in four different classes.

But wait a second, we can do even better here. If you take even a closer look, you will see that every "play" method as a part in common; This piece of code:


   if (@num_attempts <= @max_num_attempts)  
     :success  else   fail  
   end end  

This means that the method play is divided in two main basic steps: guess the number and discover the outcome !
The template method pattern is a behavioural design pattern that defines the program skeleton of an algorithm in a method, called template method, which defers some steps to subclasses. 
It lets one redefine certain steps of an algorithm without changing the algorithm's structure. 
In our specific case, we are going to create a PlayStrategy class that will define

these two steps:

  1. The playGame step will be delegate to the subclasses; The PlayStrategy doesn't know any strategy to play with, so it will defer the implementation of this step to concrete subclasses that know how to play.
  2. The outcome step will be implemented in this class. All the subclasses can call this method because it contains common code.

The class playStrategy will look like this:


 class PlayStrategy  
  def play(lower,upper,context)  
   playGame(lower,upper,context)  
   outcome(context)  
  end  
  def playGame(lower,upper,context)  
   raise("This method should be implemented in the interface")  
  end  
  def outcome(context)  
   if (context.num_attempts <= context.max_num_attempts)  
     :success  else   :fail  end end  
 end  


As we can see the method play doesn't have a real implementation. It just raise 

an exception if it is invoked on an object instance of this class. This is one of 

the way to simulate abstract method in Ruby.

New concrete subclasses will all look like this one:


 require_relative 'play_strategy'  
 class BinarySearchPlay < PlayStrategy  
  def playGame(lower, upper,context)  
   num = (lower+upper)/2  
   context.num_attempts+=1  
   while ((result = context.oracle.is_this_the_number?(num)) != :correct)  
    && (context.num_attempts <= context.max_num_attempts) do  
    # puts "#{__method__}:I guessed #{num}"  
    if result == :less_than  
     upper = num-1  
    elsif result == :greater_than  
     lower = num+1  
    end  
    num=(lower+upper)/2  
    context.num_attempts+=1  
   end  
  end  
 end  

They will define the specific algorithm they implement.

The participant class is much simpler now because we have extract the knowledge of the different play strategies:

 require_relative 'oracle.rb'  
 class Participant  
  attr_accessor :num_attempts  
  attr_reader :playStrategy  
  attr_reader :oracle  
  attr_reader :max_num_attempts  
  def initialize(oracle,playStrategy, max_num_attempts:10)  
   @oracle, @max_num_attempts = oracle, max_num_attempts  
   @num_attempts = 0  
   @playStrategy = playStrategy  
  end  
  def play(lower,upper)  
   @playStrategy.play(lower,upper,self)  
  end  
  def reset  
   @num_attempts = 0  
  end  
  private  
  def fail  
   :fail  
  end  
 end  

Participant doesn't know how to play, but the instance variable @playStrategy will help it on this matter.

Finally the main:


 # Evaluate the performance of participants using different guessing strategies  
 require_relative 'oracle.rb'  
 require_relative 'participant.rb'  
 require_relative 'binary_search_play'  
 require_relative 'linear_play'  
 require_relative 'play_strategy'  
 require_relative 'smart_random_play'  
 require_relative 'random_play'  
 NUM_OF_RUNS = 8  
 oracle = Oracle.new  
 # evaluate random strategy  
 total_num_attempts = 0  
 total_num_failures = 0  
 homer = Participant.new(oracle, RandomPlay.new, max_num_attempts: NUM_OF_RUNS*2,)  
 1.upto(NUM_OF_RUNS) do |i|  
  oracle.secret_number = i  
  homer.reset  
  if homer.play(1,NUM_OF_RUNS)==:success  
   # puts "play randomly found #{i} in #{homer.num_attempts} attempts"  
   total_num_attempts += homer.num_attempts  
  else  
   # puts "play randomly failed to find #{i} after #{homer.num_attempts} attempts"  
   total_num_failures += 1  
  end  
 end  
 puts "play randomly took on average #{total_num_attempts/  
      (NUM_OF_RUNS-total_num_failures)} attempts to succeed"  
 # evaluate linear strategy  
 total_num_attempts = 0  
 total_num_failures = 0  
 bart = Participant.new(oracle, LinearPlay.new, max_num_attempts:NUM_OF_RUNS*2)  
 1.upto(NUM_OF_RUNS) do |i|  
  oracle.secret_number = i  
  bart.reset  
  if bart.play(1,0)==:success  
   # puts "play_linear found #{i} in #{bart.num_attempts} attempts"  
   total_num_attempts += bart.num_attempts  
  else  
   # puts "play_linear failed to find #{i} after #{bart.num_attempts} attempts"  
   total_num_failures += 1  
  end  
 end  
 puts "play_linear took on average #{total_num_attempts/  
      (NUM_OF_RUNS-total_num_failures)} attempts to succeed"  
 # evaluate 'smart random' strategy  
 total_num_attempts = 0  
 total_num_failures = 0  
 maggie = Participant.new(oracle, SmartRandomPlay.new,max_num_attempts:NUM_OF_RUNS*5)  
 1.upto(NUM_OF_RUNS) do |i|  
  oracle.secret_number = i  
  maggie.reset  
  if maggie.play(1,NUM_OF_RUNS)==:success  
   # puts "play_smart_random found #{i} in #{maggie.num_attempts} attempts"  
   total_num_attempts += maggie.num_attempts  
  else  
   # puts "play_smart_random failed to find #{i} after #{maggie.num_attempts} attempts"  
   total_num_failures += 1  
  end  
 end  
 puts "play_smart_random took on average #{total_num_attempts/  
      (NUM_OF_RUNS-total_num_failures)} attempts to succeed"  
 # evaluate binary search strategy  
 total_num_attempts = 0  
 total_num_failures = 0  
 lisa = Participant.new(oracle,LinearPlay.new, max_num_attempts:NUM_OF_RUNS*5)  
 1.upto(NUM_OF_RUNS) do |i|  
  oracle.secret_number = i  
  lisa.reset  
  if lisa.play(1,NUM_OF_RUNS)==:success  
   # puts "play_binary_search found #{i} in #{lisa.num_attempts} attempts"  
   total_num_attempts += lisa.num_attempts  
  else  
   # puts "play_binary_search failed to find #{i} after #{lisa.num_attempts} attempts"  
   total_num_failures += 1  
  end  
 end  
 puts "play_binary_search took on average #{total_num_attempts/  
      (NUM_OF_RUNS-total_num_failures)} attempts to succeed"  

The most important difference to notice, highlighted in red, is that when we create a Participant, we also pass the Strategy as parameter to the constructor. In this way, we decoupled the PlayStrategy from the Participant class, and we will have to call simply the "play" method on the Participant because the strategy as been "injected" by the Client in the Participant constructor.


This is a class diagram of the new application:













HAPPY CODING!!

Luca

Google+ Followers