TDD Beyond Basics : Prime Factors Kata

Objective


Learn to evaluate whether the amount of test code to production code is reasonable or not.

Discussion


The principle of Ensure Commensurate Effort and Responsibility states that the amount of effort it takes to to write or modify tests should not exceed the effort it takes to implement the corresponding functionality. This principle is discussed in depth in xUnit Test Patterns by Gerard Meszaros.

Problem Statement


Factorize a positive integer number into its prime factors.

Problem Domain Analysis


Here is some sample input and output.

alt text

Solution Domain Analysis


Start with the divisor 2 and repeatedly reduce n by a factor of 2 until 2 is no longer an exact divisor. We then try 3 as a divisor and again repeat the reduction process and so son until n has been reduced to 1.

Consider n = 60. Marking with an * the unsuccessful attempts to divide, we have:

alt text

That is, 60 = 2 x 2 x 3 x 5, and those numbers are primes.

Steps


Step 1

Create prime_factor_spec.rb:

describe PrimeFactor do
  it 'should return 2 for input of 2' do
    prime_factorial = PrimeFactor.new(2)

    prime = prime_factorial.calculate

    expect(prime).to eq([2])
  end
end

Create prime_factor.rb :

class PrimeFactor
  def initialize(n)
    @n = n
  end

  def calculate

  end
end

The test fails for the right reason.

Step 2

Change prime_factor.rb :

class PrimeFactor
  def initialize(n)
    @n = n
  end

  def calculate
    [2]
  end
end

The test passes.

Step 3

Add the next test:

  it 'should return 3 for input of 3' do
    prime_factorial = PrimeFactor.new(3)

    prime = prime_factorial.calculate

    expect(prime).to eq([3])
  end

The test fails.

Step 4

Change the calculate method as follows:

  def calculate
    [@n]
  end

Both tests pass.

Step 5

Add the next test:

  it 'should return [2,2] for input of 4' do
    prime_factorial = PrimeFactor.new(4)

    prime = prime_factorial.calculate

    expect(prime).to eq([2,2])
  end

This test fails.

Step 6

Add the following quick and dirty implementation.

  def calculate
    result = []

    remainder = @n / 2
    result << 2
    result << remainder if Prime.prime?(remainder)

    result
  end

This test now passes. But it breaks the second spec. We will make it pending for now.

Step 7

Here is some notes from Prime Factor discussion:

n = 12
12 / 2 = 6

Is 12 evenly divisible by 2? Yes. Add 2 to the result list.

The remainder 6 is not a prime number, so we need to continue processing. Try 2 again:

6 / 2 = 3

6 is evenly divisible by 2, so add 2 to the result list. Is the remainder 3 a prime? Yes. Add it to the result list and STOP. Using this as the reference, here is the implementation that passes the test:

  def calculate
    result = []

    until Prime.prime?(@n)
      if (@n % 2) == 0
        result << 2
        @n = @n / 2
      elsif (@n % 3) == 0
        result << 3  
        @n = @n / 3
        elsif 
      end
    end
    result << @n

    result
  end

From the notes, we have found the terminating condition for our algorithm. We are also using the concept of reduction we learned in an earlier article.

Step 8

Uncomment the second test. This test passes without making any changes because our code is generic enough to handle the edge case of one element.

Step 9

  it 'should return [3,7,7] for input of 147' do
    prime_factorial = PrimeFactor.new(147)

    prime = prime_factorial.calculate

    expect(prime).to eq([3,7,7])    
  end

Step 10

Here is the quick and dirty implementation that makes all the tests pass.

def calculate
  result = []

  until Prime.prime?(@n)
    if (@n % 2) == 0
      result << 2
      @n = @n / 2
    elsif (@n % 3) == 0
      result << 3
      @n = @n / 3
    elsif (@n % 7) == 0        
      result << 7
      @n = @n / 7
    end
  end
  result << @n

  result
end

Step 11

Reading the mathisfun.com worked out examples and converting them into tests has given us more insight into the problem. We see that we need to continuously look for the given number is evenly divisible by a series of prime numbers.

We have already discussed how to generate primes using The Sieve of Erastosthenes in a previous article. Let's adapt that function so that given a number, erastosthenes function will give us the next prime for us to use in the divisible by prime check condition. For an in-depth discussion on how the Sieve of Erastosthenes can be used to solve prime factor problem read the book How to Solve It by Computer (Prentice-Hall International Series in Computer Science) by R. G. Dromey.

After experimenting in the irb, here is a function that assumes we only need a list of primes upto 100, it takes a number and gives the next prime in the list. This function is added to our existing Erastostenes class.

def self.next(n)
  e = Erastostenes.new(100)  
  primes = e.calculate
  primes.detect{|x| x > n}
end

Step 12

Let's refactor our code so that it uses our Sieve of Erastostenes for the evenly divisible check. Here is a partial refactoring:

def calculate
  result = []

  current_prime = 2

  until Prime.prime?(@n)
    if (@n % current_prime) == 0
      result << current_prime
      @n = @n / current_prime
    elsif (@n % 3) == 0
      result << 3
      @n = @n / 3
    elsif (@n % 7) == 0        
      result << 7
      @n = @n / 7
    end
  end
  result << @n

  result
end

All tests passes. Let's continue the refactoring.

Step 13

Here is the cleaned up version of the calculate method:

def calculate
  result = []

  current_prime = 2

  until Prime.prime?(@n)
    if (@n % current_prime) == 0
      result << current_prime
      @n = @n / current_prime
    else
      current_prime = Erastostenes.next(current_prime)
    end
  end
  result << @n

  result
end

All tests pass.

Step 14

I added more specs one by one to check the answer for different numbers, here is the new specs:

it 'should return [2,3] for input of 6' do
  prime_factorial = PrimeFactor.new(6)

  prime = prime_factorial.calculate

  expect(prime).to eq([2, 3])
end

it 'should return [2,2, 2] for input of 8' do
  prime_factorial = PrimeFactor.new(8)

  prime = prime_factorial.calculate

  expect(prime).to eq([2, 2, 2])
end

it 'should return [2,7] for input of 14' do
  prime_factorial = PrimeFactor.new(14)

  prime = prime_factorial.calculate

  expect(prime).to eq([2, 7])
end

it 'should handle any number' do
  prime_factorial = PrimeFactor.new(168)

  prime = prime_factorial.calculate

  expect(prime).to eq([2, 2, 2, 3, 7])
end

All the tests pass without making any modification to our solution.

Complete Code Listing


require_relative 'erastosthenes.rb'
require 'prime'

class PrimeFactor
  def initialize(n)
    @n = n
  end

  def calculate
    result = []

    current_prime = 2

    until Prime.prime?(@n)
      if (@n % current_prime) == 0
        result << current_prime
        @n = @n / current_prime
      else
        current_prime = Erastostenes.next(current_prime)
      end
    end
    result << @n

    result
  end
end

describe PrimeFactor do
  it 'should return 2 for input of 2' do
    prime_factorial = PrimeFactor.new(2)

    prime = prime_factorial.calculate

    expect(prime).to eq([2])
  end

  it 'should return 3 for input of 3' do
    prime_factorial = PrimeFactor.new(3)

    prime = prime_factorial.calculate

    expect(prime).to eq([3])
  end

  it 'should return [2,2] for input of 4' do
    prime_factorial = PrimeFactor.new(4)

    prime = prime_factorial.calculate

    expect(prime).to eq([2,2])
  end

  it 'should return [2, 2, 3] for input of 12' do
    prime_factorial = PrimeFactor.new(12)

    prime = prime_factorial.calculate

    expect(prime).to eq([2,2,3])
  end

  it 'should return [3,7,7] for input of 147' do
    prime_factorial = PrimeFactor.new(147)

    prime = prime_factorial.calculate

    expect(prime).to eq([3,7,7])    
  end

  it 'should return [2,3] for input of 6' do
    prime_factorial = PrimeFactor.new(6)

    prime = prime_factorial.calculate

    expect(prime).to eq([2, 3])
  end

  it 'should return [2,2, 2] for input of 8' do
    prime_factorial = PrimeFactor.new(8)

    prime = prime_factorial.calculate

    expect(prime).to eq([2, 2, 2])
  end

  it 'should return [2,7] for input of 14' do
    prime_factorial = PrimeFactor.new(14)

    prime = prime_factorial.calculate

    expect(prime).to eq([2, 7])
  end

  it 'should handle any number' do
    prime_factorial = PrimeFactor.new(168)

    prime = prime_factorial.calculate

    expect(prime).to eq([2, 2, 2, 3, 7])
  end

  it 'should handle any number' do
    prime_factorial = PrimeFactor.new(330)

    prime = prime_factorial.calculate

    expect(prime).to eq([2, 3, 5, 11])
  end

end

Discussion


We have 20 lines of production code and almost 70 lines of test code. Ideally we want the minimal number of tests that gives us enough confidence in our code. After you write the story test, do some exploratory testing and write some tests based on exploratory tests, evaluate whether the test to code ratio is reasonable.

We made a simplifying assumption in generating a prime factors list by limiting it to 100. You can improve this implementation by reading the Prime Factors Analysis article.

Exercises


  1. Can you delete some of the tests? What is the minimum number of tests for this problem?
  2. Study the Prime Factors Analysis. Compute the prime number required only up to a certain number discussed in that article.
  3. To find prime factors of a given number, you can use this online tool Find the Prime Factors of a Number


Related Articles


Create your own user feedback survey