Wednesday, August 14, 2013

Strategy Design Pattern Using Ruby

Back when I worked in Global Business Services at IBM, I participated in a Design Patterns user group.

It was moderated by a super smart dude, "Coop".

We studied the patterns found in the Gang of Four book and worked through coding examples in Java each time we met.

Ends up most of us had been using proven patterns in our code, but didn't realize they had names.

Object oriented programming (OOP) is great when used properly and that's where design patterns come in...

A day ago during an interview, I was asked to implement a Ten Pin Bowling Game Scoring Algorithm using Ruby. So, I put the Strategy Pattern to work to solve it and landed an awesome job.

I was given the following rules...

1. 10 Frames
2. Each frame throw the ball 2 times *
3. 10 pins
4. Each pin is worth 1 point


# Spare

7 3 -> Frame 1: 15
5 0 -> Frame 2: 15 + 5 -> 20


# Strike

10 0 -> Frame 1: 18
5 3 -> Frame 2: 18 + 8 -> 26


... and asked to code that along with Rspec test cases, which I will cover in another blog posting.

After a short pair programming session I was able to take some time to look at the problem and saw that Objects involved:
  • BowlingGame (Client)
  • Frame (StrategyBase)
  • Spare (ConcreteStrategy)
  • Strike (ConcreteStrategy)
A Spare Is A Frame, ditto for a Strike.

How to Play

After the BowlingGame is initialized with the Frame, Spare and Strike classes you call the roll method from 12 to 22 times, depending on what was rolled and then finally call the score method to find out how well you did.

Sample Code


class BowlingGame
    NUMBER_OF_FRAMES = 10

    # BowlingGame.new(Strike, Spare, Frame)
    def initialize(*policies)
        @policies = policies  # Each Frame type has different policies used for scoring
        @rolls = []           # Array of rolls (number of pins knocked down)
    end

    # Add number of pins knocked down to @rolls array
    def roll(pins_knocked_down)
        @rolls << pins_knocked_down
    end

    # Sum each frame's score for total
    # See: http://lexsheehan.blogspot.com/search?q=functional+programming
    def score
        frames.reduce(0) { |sum, frame| sum + frame.score }
    end

    # A frame consists of two rolls, unless first roll is a Strike (special rules for last frame)
    def frames
        roll_index = 0
        frames = []
        NUMBER_OF_FRAMES.times do |i|
            frames << frame(roll_index)
            # Polymorphism: Frames could be a Strike or a Spare, both of which have a number_of_rolls method
            # Spare has 2 rolls and Strike has 1 roll
            is_last_frame = i.eql?(NUMBER_OF_FRAMES - 1)  # Last frame gets bonus roll(s)
            roll_index += frames.last.number_of_rolls(is_last_frame)
        end
        frames
    end

    # Use strategy pattern to select appropriate Frame type (regular Frame, Spare or Strike)
    # See:  http://en.wikipedia.org/wiki/Strategy_pattern
    def frame(roll_index)
        @policies.each do |policy|
            # Select frame based on policy in found? methods
            return policy.new(@rolls, roll_index) if policy.found?(@rolls, roll_index)
        end
    end

end

class Frame
    def initialize(rolls, roll_index)
        @rolls = rolls            # Array of rolls, where each equates to number of pins knocked down in that roll
        @roll_index = roll_index  # The first roll index in this frame
    end

    def score
        @rolls[@roll_index] + @rolls[@roll_index + 1]  # Sum of both rolls in frame
    end

    def self.found?(rolls, roll_index)
        true  # If neither Spare or Strike then this is a regular Frame
    end

    def number_of_rolls(is_last_frame)
        2  # Default to 2 rolls (regardless of whether it's last frame)
    end
end

class Strike < Frame
    # In the frame where strike is rolled, add 10 to number of pins knocked down in next two rolls
    def score
        10 + @rolls[@roll_index + 1] + @rolls[@roll_index + 2]
    end

    # Strike strategy found when number of pins knocked down in first rolls of frame equals 10
    def self.found?(rolls, roll_index)
        rolls[roll_index].eql?(10)
    end

    # Override Frame type's number_of_rolls method
    def number_of_rolls(is_last_frame)
        # If the last frame starts with a strike, we get 2 bonus rolls
        is_last_frame ? 3 : 1
    end
end

A Few Test Cases


    it "scores 0 with a gutter ball game" do
        20.times { game.roll 0 }
        expect(game.score).to eq(0)
    end

    it "scores 300 with all strikes" do
        12.times { game.roll 10 }
        expect(game.score).to eq(300)
    end

    it "scores 150 with all 5's" do
        21.times { game.roll 5 }
        expect(game.score).to eq(150)
    end

References

Get the code and a nice README with more references here: https://github.com/l3x/lex-dp-strategy-ruby