11 Years of Prime Factors Kata

In this post I want to celebrate the Prime Factors Code Kata. Prime Factors is a small coding exercise first used by Robert C. Martin in 2005. It is my favourite code kata and it has been almost nine years since I last wrote about it - time to change that. Weird enough, the first code kata I ever worked on - outside of university assignments that turned out to be katas later - was Roman Numerals in 2007. The first time I did the Prime Factors was during Christmas holidays 2009 in Java and Ruby:

import java.util.ArrayList;
import java.util.List;

public class PrimeFactors {
  public static List<Integer> generate(int n) {
    List<Integer> primes = new ArrayList<Integer>();

    for (int candidate = 2; candidate <= n; candidate++) {
      for (; n % candidate == 0; n /= candidate) {
        primes.add(candidate);
      }
    }

    return primes;
  }
}

Now the Java code is exactly the code Robert Martin showed, I was following his example. The Ruby version from back then looks pretty similar, just using while instead of for.

module PrimeFactors
  def generate(n)
    prime_factors = []

    candidate = 2
    while n > 1 do
      while n % candidate == 0 do
        prime_factors << candidate
        n /= candidate
      end
      candidate += 1
      candidate = n if candidate > Math.sqrt(n) # performance fix
    end

    prime_factors
  end
end

If you are wondering how I am still able to find the code, I organise my code katas to allow lookup and comparison. Since then I did the kata 141 times and it has many uses.

Learn a language
Prime Factors is one of the first pieces of code I write - Test Driven of course - when revisiting old languages, like Commodore BASIC or looking at a new language, like Forth, using Gforth 0.7:

: prime_factors ( n -- n1 n2 n3 n4 )
  DUP 1 > IF           \ test for ?DO
    DUP 2 ?DO
      BEGIN
        DUP I MOD 0 =  \ test candidate I
      WHILE
        I SWAP I /     \ add candidate, reduce number
      REPEAT
    LOOP
  THEN
  DUP 1 = IF DROP THEN ;

T{ 1 prime_factors -> }T
T{ 2 prime_factors -> 2 }T
T{ 3 prime_factors -> 3 }T
T{ 4 prime_factors -> 2 2 }T
T{ 6 prime_factors -> 2 3 }T
T{ 8 prime_factors -> 2 2 2 }T
T{ 9 prime_factors -> 3 3 }T

Gforth came with a modified testing framework based on John Hayes S1I's tester.fs, defining the functions T{, -> and }T for testing. Note that the given function prime_factors is not realistic as the number of returned arguments is not known by the caller.

When I had a look at Scala, of course I did Prime Factors:

import java.lang.Math.sqrt

object PrimeFactors {
  def generate(number: Int): List[Int] = {

    def fold(current: Pair[Int, List[Int]], candidate: Int): Pair[Int, List[Int]] = {
      if (current._1 % candidate == 0)
        fold((current._1 / candidate, candidate :: current._2), candidate)
      else
        current
    }

    val (remainder, factors) =
      (2 to sqrt(number).intValue).foldLeft((number, List[Int]()))(fold)

    if (remainder > 1)
      (remainder :: factors).reverse
    else
      factors.reverse
  }
}

This is crazy. The code creates a sequence of all candidate primes and folds it starting from left by dividing by the candidate recursively, appending to the begin of the list, which is cheap. Because of that the list is reversed at the end. I have no idea why I created this, probably I was playing around with foldLeft. This is not a good example, please do not copy it. After all these years, the Forth solution seems easier to grasp. ;-)

So which languages are missing? PowerShell looks much like my PHP (shown below) and my Python Prime Factors looks similar too, just with Python specific range(2, number + 1) and //= inside. And of course JavaScript is missing:

PrimeFactors = function() {
  this.factors = [];
};

PrimeFactors.prototype.generate = function(num) {
  var candidate;
  for (candidate = 2; candidate <= num; candidate += 1) {
    num = this.tryCandidate(num, candidate);
  }
  return this.factors;
};

PrimeFactors.prototype.tryCandidate = function(num, candidate) {
  while (num % candidate === 0) {
    num = this.reduceByFactor(num, candidate);
  }
  return num;
};

PrimeFactors.prototype.reduceByFactor = function(num, factor) {
  this.factors.push(factor);
  return num / factor;
};

Isn't that lovely? Again this is not good code, please do not copy it. At least I showed some creativity using prototype functions.

Learn a testing framework
Using TDD to write some known code is a perfect way to learn more about a testing framework. So I explored XSLTunit using Prime Factors in XSLT or NUnit in C#:

using NUnit.Framework;

[TestFixture]
public class PrimeFactorsTest
{
  [TestCase(new int[0], 1)]
  [TestCase(new int[] { 2 }, 2)]
  [TestCase(new int[] { 3 }, 3)]
  [TestCase(new int[] { 2, 2 }, 4)]
  [TestCase(new int[] { 2, 2, 2 }, 8)]
  [TestCase(new int[] { 3, 3 }, 9)]
  public void TestFactors(int[] expected, int number)
  {
    CollectionAssert.AreEqual(expected, PrimeFactors.Generate(number));
  }

  [Test]
  [Timeout(100)]
  public void TestLarge()
  {
    CollectionAssert.AreEqual(new int[] { int.MaxValue },
                              PrimeFactors.Generate(int.MaxValue));
  }
}

Test your own testing framework
Sometimes, when I need to create my own unit testing framework, e.g. TPUnit for old Turbo Pascal, assert-scm (Scheme R5RS) or ASM Unit for Windows Assembly, I use Prime Factors as test cases:

_prime_factors:
  mov     esi, 0          ; esi = number of factors
  mov     edi, ebx        ; edi = address of factors
  mov     ecx, eax        ; ecx = current number
  mov     ebx, 1          ; ebx = candidate

  jmp .not_diviseable

.loop_over_candidates:
  inc     ebx             ; next candidate

.break_if_candidate_is_larger_than_square:
; if candidate * candidate <= number then try candidate
  mov     eax, ebx
  mul     ebx
  cmp     eax, ecx
  jbe     .try_candidate

; else number is a (large) prime and we are done
  mov     [edi + esi * register_size], ecx
  add     esi, 1
  jmp     .done

.try_candidate:
; if number % candidate == 0 then add candidate
  mov     eax, ecx
  xor     edx, edx
  div     ebx
  cmp     edx, 0          ; remainder is 0
  jne     .not_diviseable

.is_diviseable:
  mov     [edi + esi * register_size], ebx
                          ; store candidate in factors
  add     esi, 1          ; we found a factor
  mov     ecx, eax        ; number is remainder of division
  jmp     .try_candidate  ; try current candidate again

.not_diviseable:
; if number > 1 then try next candidate
  cmp     ecx, 1
  jne     .loop_over_candidates

.done:
; return number of factors
  mov     eax, esi
  ret

This piece of assembly calcultes the prime factors of the number passed in EAX into in the dword array address EBX.

TDD Demo
In 2012 I started practising Prime Factors as kata performance, minimising the number of keys I pressed. I ran it around 50 times. In the end I used the practice to calm down when I was anxious - it was like mediation. I still have to perform it somewhere, adding music and all... I have used it demoing TDD in uncounted presentations - actually around 40: during my university guest lectures, user group meetings and at my clients. Most demos were in Java and some in PHP,

<?php
class PrimeFactors {
  static function generate($n) {
    $factors = [];
    for ($candidate = 2; $candidate <= $n; $candidate += 1) {
      while ($n % $candidate == 0) {
        $factors[]= $candidate;
        $n /= $candidate;
      }
    }
    return $factors;
  }
}

and a single demo of test driving R code,

primeFactors <- function(number) {
  factors <- vector(mode="integer")

  candidate <- 2
  while (candidate <= sqrt(number)) {
    while (number %% candidate == 0) {
      factors <- c(factors, candidate)
      number <- number / candidate
    }
    candidate = candidate + 1
  }

  if (number > 1) {
    factors <- c(factors, number)
  }

  factors
}

It seems, most programming languages look the same. The last sentence is not true for NATURAL, Cobol's cousin, which is ugly. I will not show it here as it would destroy this lovely post.

Conclusion
By writing this post, I learned that I still need to create Prime Factors in the programming languages Go, Kotlin, OpenOffice Basic, Oracle PL/SQL and of course TypeScript - I could - and I will, it is just a matter of time. So Prime Factors - in fact any small enough code kata - is a great tool for exploring, studying and practising programming languages, testing frameworks, IDE tools and Test Driven Development in general. I will leave you with my latest addition to my collection of Prime Factors, using C99. Have fun!

#include <math.h>

typedef struct {
  unsigned char count;
  unsigned int values[31];
} PrimeFactors;

void PrimeFactors_init(PrimeFactors* factors)
{
  (*factors).count = 0;
}

void PrimeFactors_add(PrimeFactors* factors, const unsigned int factor)
{
  int count = (*factors).count;
  (*factors).values[count] = factor;
  (*factors).count = count + 1;
}

void generate(const unsigned int number, PrimeFactors* factors)
{
  PrimeFactors_init(factors);

  unsigned int remaining = number;
  for (unsigned int candidate = 2; candidate <= sqrtl(remaining); candidate += 1) {
    while (remaining % candidate == 0) {
      PrimeFactors_add(factors, candidate);
      remaining /= candidate;
    }
  }

  if (remaining > 1) {
    PrimeFactors_add(factors, remaining);
  }
}

Testing Koans

Koans
Koans have been proposed as an effective way to learn a new programming language. But what exactly are Koans? According to Wikipedia a Koan (where the o has a macron, a straight bar placed above it - which my text editor refuses to produce) is a "case, story, dialogue, question or statement in the history and lore of Zen Buddhism". Huh? Reading the Wikipedia article did not help me at all. All I understand is that a Koan is something the Buddhist monks would work with, a mystical sentence or maybe a kind of poem, which does not make any sense, but somehow helps them on their way to enlightenment. It seems the metaphor has been transferred from Buddhism to software, e.g. Hacker Koans and Koans are related to the TAO of Programming. (Again no idea what TAO is supposed to mean here. This is like a recursive definition.)

Ruby Koans
As far as I know, the first Programming Koans were available in Ruby, created by the late Jim Weirich, a popular Ruby hacker. Ruby Koans consists of several little exercises, starting with basic things and building on each other to move to more advanced topics in the end. The goal is to learn Ruby, to walk the "path to enlightenment" as Jim put it. He also wanted to teach the Ruby culture. The Ruby community has a strong focus on testing, which is considered essential to "do great things in the language". In fact the exercises are a list of failing test cases, where tiny pieces of code have to be filled in to make them pass. For example, here is the exercise to learn accessing array elements,

def test_accessing_array_elements
  array = [:peanut, :butter, :and, :jelly]

  assert_equal __(:peanut), array[0]
  assert_equal __(:peanut), array.first
  assert_equal __(:jelly), array[3]
  assert_equal __(:jelly), array.last
  assert_equal __(:jelly), array[-1]
  assert_equal __(:butter), array[-3]
end

The double underscore marks the place where the code has to be changed to make it work and pass the test. These tests are very simple and there is not much explanation. Maybe this is the connection to the Zen Koans: The Language Koans are a list of exercises to work through, to master the language (i.e. reach enlightenment). Each one is very small (i.e. a sentence) but does not make much sense on its own. The exercises are sorted by increasing difficulty (i.e. the path to walk). Following Jim's example, Koans are usually based on unit tests which you make succeed. Language Koans are available for many programming languages, see a list of Koans by Laura Diane Hamilton.

Testing Koans
I took the idea for Testing Koans from Carlos Blé's training JavaScript for Testers. He created some Koans for JavaScript with inverted work-flow. The code was already in place, but the assertions were missing. That was reasonable as the training was created for tester.

xUnit Koans
Earlier this year I ran an introductory unit testing workshop for the local PHP community. I expected a junior audience and aimed for the most basic exercise for xUnit assertions and life cycle methods. I wanted the participants to focus on PHPUnit alone. I created some sample code, together with unit tests, and then deleted the assertion statements. The first test looked similar to the following Java code:

import org.junit.Test;

public class Session1_GreeterTest {

  @Test
  public void shouldReturnHelloName() {
    Greeter greeter = new Greeter();
    // TODO check that "Hello Peter" is greeter.greet("Peter")
  }

  @Test
  public void shouldReturnHelloForNull() {
    Greeter greeter = new Greeter();
    // TODO check that "Hello" is greeter.greet(null)
  }

  // more tests skipped...

}

The participants went through the tests one by one, adding assertions or fixing incomplete statements, making the tests pass. While this looked like a very basic and short exercise, developers unfamiliar to PHPUnit (and xUnit in general) needed several hours to complete all my PHPUnit Testing Koans.

Due to the uniform nature of all xUnit ports, the style and structure of the exercise can be used for other programming languages. I ported the exercise to Java using JUnit, creating Java/JUnit Koans. Both Koans cover the basic functionality of PHPUnit and JUnit, e.g. assertions, testing for exceptions and before- and after-methods. More advanced features could be added. I will port the Koans to C#/NUnit and Ruby/minitest as soon as I will need them.

Conclusion
Koans are a great way to partition the process of knowledge acquisition into a series of little exercises. They verify themselves, giving you fast feedback but you can still learn at your own pace. Language Koans are established and available for many languages. These can be extended to any library or public API you want to master. Testing Koans work similar, just inverted. They are available for PHPUnit and JUnit for now. I would love to see more ports and also Koans for different testing styles, e.g. RSpec or Jasmine Testing Koans.

Using Hamcrest Matchers With Composer

To help my friends of the Vienna PHP User Group to get started with Coding Dojos, I created a project template. Obviously the used programming language was PHP and PHPUnit, the PHP xUnit implementation, was required.

Composer
Setting up a new project almost always starts with dependency management and I used Composer to define my dependencies. Composer was configured by its composer.json,

{
  "name": "codecop/CodingDojo-PHP",
  "description": "Coding Dojo template",
  "license": "BSD",
  "require": {
  },
  "require-dev": {
    "phpunit/phpunit": "4.5.*"
  }
}

After verifying my composer installation with composer --version I downloaded PHPUnit with composer install. PHPUnit and its transitive dependencies were installed into the vendor directory as expected.

PHPUnit
Next I configured PHPUnit with its phpunit.xml,

<?xml version="1.0" encoding="UTF-8"?>
<phpunit xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:noNamespaceSchemaLocation="http://schema.phpunit.de/4.5/phpunit.xsd"
    backupGlobals="false"
    colors="true"
    beStrictAboutTestsThatDoNotTestAnything="true"
    beStrictAboutOutputDuringTests="true"
    beStrictAboutTestSize="true"
    beStrictAboutTodoAnnotatedTests="true"
    verbose="true">

    <testsuites>
        <testsuite name="All Tests">
            <directory suffix="Test.php">test</directory>
        </testsuite>
    </testsuites>
</phpunit>

This told PHPUnit to load all the *Test.php files inside the test directory for test classes. I especially like the beStrictAbout* flags and enabled them all. These flags warn about smelly tests, e.g. test methods without any assertions. I ran PHPUnit with ./vendor/bin/phpunit to verify my setup. It did not show any tests - after all this was a new and empty project. I have seen people creating an alias to run PHPUnit, but I created a (Windows) script phpunit.bat in the local directory with the same effect,

@call "%~dp0vendor\bin\phpunit" %*

Now I was ready to go and wrote some unit tests, e.g.

<?php

require 'Hello.php';

class HelloTest extends \PHPUnit_Framework_TestCase {

    /** @test */
    function shouldReturnHelloName() {
        $greeter = new Greeter();
        $this->assertEquals("Hello Peter", $greeter->greet("Peter"));
    }

}

Hamcrest Matchers
In the Java community Hamcrest Matchers are popular and they even ship with the core JUnit framework. I like Hamcrest because it allows me to write my own matchers, which make assertions much more expressive than plain assertEquals. Luckily there were some ports of it and I was happy to see a Hamcrest PHP port. I added it to composer.json,

"require-dev": {
  "phpunit/phpunit": "4.5.*",
  "hamcrest/hamcrest-php": "1.2.*"
}

and updated my installation with composer install. Hamcrest offers global functions for its matchers, which allow for shorter syntax, especially when matchers are chained together. To enable this global functions, Composer has to auto load the main Hamcrest file, which is configured using autoload-dev in composer.json,

"autoload-dev": {
  "files": ["vendor/hamcrest/hamcrest-php/hamcrest/Hamcrest.php"]
}

Using global functions has some drawbacks and is considered a bad practise in large scale projects. There are different ways to use Hamcrest PHP with Composer without loading the global functions, e.g. see Hamcrest PHP issues at GitHub. For a first time Coding Dojo I wanted to stay with the simplest way to use Hamcrest and kept the global functions.

So I was able to write my unit tests using Hamcrest matchers, e.g.

<?php

require 'Hello.php';

class HelloTest extends \PHPUnit_Framework_TestCase {

    /** @test */
    function shouldReturnHelloName() {
        $greeter = new Greeter();
        assertThat($greeter->greet("Peter"), equalTo("Hello Peter"));
    }

}

While the test above succeeded, PHPUnit refused to show me a green bar. This was because Hamcrest's assertThat was not recognised as assertion and PHPUnit marked the test as erroneous. With a heavy heart I had to remove one of PHPUnit's beStrictAbout flags,

<?xml version="1.0" encoding="UTF-8"?>
<phpunit xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:noNamespaceSchemaLocation="http://schema.phpunit.de/4.5/phpunit.xsd"
    backupGlobals="false"
    colors="true"
    beStrictAboutTestsThatDoNotTestAnything="false"
    beStrictAboutOutputDuringTests="true"
    beStrictAboutTestSize="true"
    beStrictAboutTodoAnnotatedTests="true"
    verbose="true">

That was it. Finally I was ready to rock, matchers included!

(The complete project as zip is here.)