The Roman numerals kata: TDD with and without analysis

Katas are small exercises that are repeatedly executed to improve one aspect of our programming capabilities - being design, automation, or a practice like Test-Driven Development. The Roman numerals kata attempts to create a conversion mechanism from integers to a Roman representation (a string):

• 1, 2 and 3 become I, II and III respectively.
• 5 and 10 become V and X respectively.
• 6 become VI, as symbols are additive.
• 4 becomes IV, as symbols are used subtractively (in this case subtracting 1 from 5) to avoid repeating a symbol more than three times in a row.

If you have never tried the kata and want to do so in the future, I urge you to pick it up before reading further as I would spoil some of the experience for you.

I recently executed the kata as a TDD exercise by myself and in a workshop in the local PHP user group in Milan. We reached two different solutions, and I want to analyze here why, and which is preferrable with regards to certain concerns. The solution is not the point of a kata: the experience (and what it teaches you) is; however, the roads you can take are part of the experience.

The hardcore TDD solution

When "pure" TDD is teached with this kata, one test is added at the time and production code is modified to make this test pass along with all the previously introduced ones. Then, a arbitrary long refactoring phase is performed to improve the code and prepare it to evolve further.

Most of the solutions I found on the web (also in the form of videos) to compare them with mine went like this :

private static final int[]    VALUES  = { 1000, 900,  500, 400,  100, 90,   50,  40,   10,  9,    5,   4,    1   };
private static final String[] SYMBOLS = { "M",  "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };

public static String arabicToRoman(int arabic) {
    StringBuilder result = new StringBuilder();
    int remaining = arabic;
    for (int i = 0; i < VALUES.length; i++) {
        remaining = appendRomanNumerals(remaining, VALUES[i], SYMBOLS[i], result);
    }
    return result.toString();
}

I was not really satisfied with these kind of solutions as they are essentially an optimized lookup table more than a conversion algorithm. There is lots of duplication in this code: symbols like I and X are repeated in more than one subtractive form (IV and IX), and the subtractive rule itself is scattered among the values of the SYMBOLS array. If rules were to change (which does not happen in a kata but does in the real world), it would be difficult to adapt this code to cover Etruscan or Greek numerals, that have different models of subtractivity and symbol reuse.

Again and again, TDD proved not sufficient (but facilitating) for algorithm generation; at least, for generating an algorithm well-factored enough to present changeable parts instead of a single procedure or a lookup table.

How the domain comes into play

If applying a pure red-green-refactor cycle cannot help us, what should we do? I took a look at Wikipedia, which is a good source to get acquainted with the domain of numerical systems (I stick to the Roman one however). Thus I discovered some interesting facts:

1. the United States National Institute of Standards and Technology could find no authority that could describe if the year 1999 should be written as MDCCCCLXXXXVIIII, MCMXCIX, or MIM.[2] Despite the lack of standardization, an additional set of rules has been frequently applied for the last few hundred years
2. Only one small-value symbol may be subtracted from any large-value symbol.
3. The symbols "I", "X", "C", and "M" can be repeated three times in succession, but no more. (They may appear more than three times if they appear non-sequentially, such as XXXIX.) "D", "L", and "V" can never be repeated.
4. "I" can be subtracted from "V" and "X" only. "X" can be subtracted from "L" and "C" only. "C" can be subtracted from "D" and "M" only. "V", "L", and "D" can never be subtracted.
5. A number written in Arabic numerals can be broken into digits. For example, 1903 is composed of 1, 9, 0, and 3. To write the Roman numeral, each of the non-zero digits should be treated separately. In the above example, 1,000 = M, 900 = CM, and 3 = III. Therefore, 1903 = MCMIII.

(All quotes are from http://en.wikipedia.org/wiki/Roman_numerals,)

This knowledge is represented as a set of requirements, or can be seen as domain rules. By taking the time to find a source of knowledge about the domain of my application, I have extracted some relevant bits that can greatly simplify my model of the problem:

• We have clear requirements! Acceptance criteria are clearly defined as there are multiple possibilities for the numerical conversion. (1)
• There is a mechanism that is repeated across orders of magnitude: I is subtracted from 5 and 10, but X is subtracted from 50 and 100, and so on (2, 3, 4).
• We can divide the Arabic number into different ciphers and convert them separately, keeping in mind their position. Converting 42 becomes converting 40 and 2 plus a concatenation: 'XL' plus 'II'.

Yet I couldn't find a single solution published online that leverages this important property to improve the code.

Analysis-based solution

Thus I set out to create a more flexible solution to the Roman numerals conversion problem. In this case I used only functions instead of objects to keep the solution clear for our user group audience, but I suspect that by introducing one or more classes such as OrderOfMagnitude and RomanCipher the code could speak for itself more clearly.

I published on Github both this solution of mine and the classical one that we reached at the user group.

function romanCipher($firstSymbol, $middleSymbol, $lastSymbol)
{
    return function($number) use ($firstSymbol, $middleSymbol, $lastSymbol) {
        if ($number == 0) {
            return '';
        }
        $symbols = array(1 => $firstSymbol,
                         5 => $middleSymbol,
                         10 => $lastSymbol);
        $roman = '';
        foreach ($symbols as $denomination => $symbol) {
            if ($number == $denomination - 1) {
                return $firstSymbol . $symbol;
            }
        }
        foreach (array_reverse($symbols, true) as $denomination => $symbol) {
            while ($number >= $denomination) {
                $roman .= $symbol;
                $number -= $denomination;
            }
        }
        return $roman;
    };
}

class RomanNumeralsTest extends PHPUnit_Framework_TestCase
{
    public function setUp()
    {
        $this->toRoman = function($number) {
            $ciphers = array(
                '1' => romanCipher('I', 'V', 'X'),
                '2' => romanCipher('X', 'L', 'C'),
                '3' => romanCipher('C', 'D', 'M'),
                '4' => romanCipher('M', '?', '?'),
            );
            $arabic = (string) $number;
            $fullRoman = '';
            for ($i = 0; $i < strlen($arabic); $i++) {
                $position = strlen($arabic) - $i;
                $cipher = $ciphers[$position];
                $fullRoman .= $cipher($arabic{$i});
            }
            return $fullRoman;
        };
    }
    ...

The code is longer than the classic solution; but isn't well-factored code always a bit longer than a brute force version? I also found out that I could write more focused tests that collected domain properties; while refactoring I renamed tests from:

    public function test4IsConvertedToIV()
    ...
    public function test124ISConvertedToCXXIV()

to:

    public function testSmallerSymbolsOnTheLeftAreSubtractive()
    ...
    public function testEvenNumbersGreaterThan100CanBeDividedIntoCiphers()
    {
        $this->assertEquals('C' . 'XX' . 'IV', $this->toRoman(124));
        $this->assertEquals('CM' . 'XC' . 'IX', $this->toRoman(999));
    }

Conclusions

I presented TDD at our workshop as a facilitating condition for writing clean code, but not as a sufficient one. Analysis is not dead and writing tests or jumping into coding some spike is not the only way you have to approach a problem.

To be fair, the pure TDD approach let everyone reach a working solution, covered by automated tests; in many utility components of your application, such a result proves useful as you can write code that works and clean it up as much as you need (and no further). If numerical conversions aren't your core domain, you can just go for the brute force code where its complexity is manageable; just like you could go for bubble sort in case you needed to sort only a dozen of elements.