Practicing TDD using the Roman Numerals kata

Test-Driven Development (TDD) is a scientific approach to software development that supports incremental design. I’ve found that, although very powerful, this approach takes some getting used to. Although the rules of TDD are simple, they’re not always easy:

  1. Write a failing test
  2. Write the simplest bit of code that makes it pass
  3. Refactor the code to follow the rules of simple design

This is also called the Red-Green-Refactor cycle of TDD.

Writing a failing test isn’t always easy. Lots of TDD beginners write tests that are to big; TDD is all about taking baby steps. Likewise, writing the simplest bit of code to make the test pass is sometimes difficult. Many developers are trained to write generic code that can handle more than just the case at hand; they must unlearn these habits and truly focus on doing The Simplest Thing That Could Possibly Work.

The hardest part of TDD, however, is the final step. Some TDD novices skip it altogether, others have trouble evolving their design. Code that follows the rules of simple design

  1. Passes all the tests
  2. Contains no duplication
  3. Clearly expresses the programmer’s intent
  4. Minimizes code

The first is easy, since your xUnit framework will either give you Red or Green. But then the fun begins. Let’s walk through an example to see TDD in action.

We’ll use the Roman Numerals kata for this example. A kata is a term inherited from the martial arts. To get really good at something, you have to practice. The martial arts understood this long before the Software Crafsmanship movement was born.
They use katas to practice their basic moves over and over again. Software katas are similar. They focus on fundamental skills like TDD and incremental design.

In the Roman Numerals kata, we convert Arabic numbers (the one we use daily: 1, 2, 3, 4, 5, …) into their Roman equivalent: I, II, III, IV, V, … It’s a good kata, because it allows one to practice skills in a very concentrated area, as we’ll see.

So let’s get started. The first step is to write a failing test:

public class RomanNumeralsTest {

  @Test
  public void one() {
    Assert.assertEquals("1", "I", RomanNumerals.arabicToRoman(1));
  }

}

Note that this step really is not (only) about tests. It really is about designing your API from the client’s perspective. Think of something that you as a user of the API would like to see to solve your bigger problem. In this kata, the API is just a single method, so there is not much to design.

OK, we’re at Red, so let’s get to Green:

public class RomanNumerals {

  public static String arabicToRoman(int arabic) {
    return "I";
  }

}

But that’s cheating! That’s not an algorithm to convert Arabic numerals into Roman! True, it’s not, but it isn’t cheating either. The rules of TDD state that we should write the simplest code that passes the test. It’s only cheating if you play by the old rules. You must unlearn what you have learned.

Now for the Refactor step. The test passes, there is no duplication, we express our intent (that currently is limited to convert 1 into I) clearly, and we have the absolute minimum number of classes and methods (both 1), so we’re done. Easy, right?

Now we move to the next TDD cycle. First Red:

public class RomanNumeralsTest {

  @Test
  public void oneTwo() {
    Assert.assertEquals("1", "I", RomanNumerals.arabicToRoman(1));
    Assert.assertEquals("2", "II", RomanNumerals.arabicToRoman(2));
  }

}

No need to change our API. In fact we won’t have to change it again for the whole kata. So let’s move to Green:

public static String arabicToRoman(int arabic) {
  if (arabic == 2) {
    return "II";
  }
  return "I";
}

OK, we’re Green. Now let’s look at this code. It’s pretty obvious that if we continue down this path, we’ll end up with very, very bad code. There is no design at all, just a bunch of hacks. That’s why the Refactor step is essential.

We pass the tests, but how about duplication? There is duplication in the Arabic number passed in and the number of I’s the method returns. This may not be obvious to everyone because of the return in the middle of the method. Let’s get rid of it to better expose the duplication…

public static String arabicToRoman(int arabic) {
  StringBuilder result = new StringBuilder();
  if (arabic == 2) {
    result.append("I");
  }
  result.append("I");
  return result.toString();
}

…so that we can remove it:

public static String arabicToRoman(int arabic) {
  StringBuilder result = new StringBuilder();
  for (int i = 0; i < arabic; i++) {
    result.append("I");
  }
  return result.toString();
}

What we did here was generalize an if statement into a for (or while). This is one of a bunch of transformations one often uses in TDD. The net effect of a generalization like this is that we have discovered a rule based on similarities. This means that our code can now handle more cases than the ones we supplied as tests. In this specific case, we can now also convert 3 to III:

@Test
public void oneTwoThreeRepeatIs() {
  Assert.assertEquals("1", "I", RomanNumerals.arabicToRoman(1));
  Assert.assertEquals("2", "II", RomanNumerals.arabicToRoman(2));
  Assert.assertEquals("3", "III", RomanNumerals.arabicToRoman(3));
}

Now that we have removed duplication, let’s look at expressiveness and compactness. Looks OK to me, so let’s move on to the new case. We got 3 covered, so 4 is next:

@Test
public void four() {
  Assert.assertEquals("4", "IV", RomanNumerals.arabicToRoman(4));
}

This fails as expected, because we generalized to far. We need an exception to our discovered rule:

  public static String arabicToRoman(int arabic) {
    StringBuilder result = new StringBuilder();
    if (arabic == 4) {
      return "IV";
    }
    for (int i = 0; i < arabic; i++) {
      result.append("I");
    }
    return result.toString();
  }

This uses return in the middle of a method again, which we discovered may hide duplication. So let’s not ever use that again. One alternative is to use an else statement. The other is to decrease the arabic parameter, so that the for loop never executes. We have no information right now on which to base our choice, so either will do:

public static String arabicToRoman(int arabic) {
  StringBuilder result = new StringBuilder();
  if (arabic == 4) {
    result.append("IV");
  } else {
    for (int i = 0; i < arabic; i++) {
      result.append("I");
    }
  }
  return result.toString();
}

It’s hard to see duplication in here, and I think the code expresses our current intent and is small, so let’s move on to the next test:

@Test
public void five() {
  Assert.assertEquals("5", "V", RomanNumerals.arabicToRoman(5));
}

Which we make pass with:

public static String arabicToRoman(int arabic) {
  StringBuilder result = new StringBuilder();
  if (arabic == 5) {
    result.append("V");
  } else if (arabic == 4) {
    result.append("IV");
  } else {
    for (int i = 0; i < arabic; i++) {
      result.append("I");
    }
  }
  return result.toString();
}

This is turning into a mess. But there is no duplication apparent yet, and the code does sort of say what we mean. So let’s push our uneasy feelings aside for a little while and move on to the next test:

@Test
public void six() {
  Assert.assertEquals("6", "VI", RomanNumerals.arabicToRoman(6));
}

Which passes with:

public static String arabicToRoman(int arabic) {
  StringBuilder result = new StringBuilder();
  if (arabic == 6) {
    result.append("VI");
  } else if (arabic == 5) {
      result.append("V");
  } else if (arabic == 4) {
    result.append("IV");
  } else {
    for (int i = 0; i < arabic; i++) {
      result.append("I");
    }
  }
  return result.toString();
}

Hmm, uglier still, but at least some duplication is now becoming visible: VI is V followed by I, and we already have code to append those. So we could first add the V and then rely on the for loop to add the I:

public static String arabicToRoman(int arabic) {
  StringBuilder result = new StringBuilder();
  int remaining = arabic;
  if (remaining >= 5) {
    result.append("V");
    remaining -= 5;
  }
  if (remaining == 4) {
    result.append("IV");
    remaining -= 4;
  }
  for (int i = 0; i < remaining; i++) {
    result.append("I");
  }
  return result.toString();
}

Still not very clean, but better than before. And we can now also handle 7 and 8. So let’s move on to 9:

@Test
public void nineIsXPrefixedByI() {
  Assert.assertEquals("9", "IX", RomanNumerals.arabicToRoman(9));
}
public static String arabicToRoman(int arabic) {
  StringBuilder result = new StringBuilder();
  int remaining = arabic;
  if (remaining == 9) {
    result.append("IX");
    remaining -= 9;
  }
  if (remaining >= 5) {
    result.append("V");
    remaining -= 5;
  }
  if (remaining == 4) {
    result.append("IV");
    remaining -= 4;
  }
  for (int i = 0; i < remaining; i++) {
    result.append("I");
  }
  return result.toString();
}

There’s definitely a pattern emerging. Two ifs use ==, and one uses >=, but the rest of the statements is the same. We can make them all completely identical by a slight generalization:

public static String arabicToRoman(int arabic) {
  StringBuilder result = new StringBuilder();
  int remaining = arabic;
  if (remaining >= 9) {
    result.append("IX");
    remaining -= 9;
  }
  if (remaining >= 5) {
    result.append("V");
    remaining -= 5;
  }
  if (remaining >= 4) {
    result.append("IV");
    remaining -= 4;
  }
  for (int i = 0; i < remaining; i++) {
    result.append("I");
  }
  return result.toString();
}

Now we can extract the duplication:

public static String arabicToRoman(int arabic) {
  StringBuilder result = new StringBuilder();
  int remaining = arabic;
  remaining = appendRomanNumerals(remaining, 9, "IX", result);
  remaining = appendRomanNumerals(remaining, 5, "V", result);
  remaining = appendRomanNumerals(remaining, 4, "IV", result);
  for (int i = 0; i < remaining; i++) {
    result.append("I");
  }
  return result.toString();
}

private static int appendRomanNumerals(int arabic, int value, String romanDigits, StringBuilder builder) {
  int result = arabic;
  if (result >= value) {
    builder.append(romanDigits);
    result -= value;
  }
  return result;
}

There is still duplication is the enumeration of calls to appendRomanNumerals. We can turn that into a loop:

private static final int[]    VALUES  = { 9,    5,   4 };
private static final String[] SYMBOLS = { "IX", "V", "IV" };

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);
  }
  for (int i = 0; i < remaining; i++) {
    result.append("I");
  }
  return result.toString();
}

Now that we look at the code this way, it seems that the for loop does something similar to what appendRomanNumerals does. The only difference is that the loop does it multiple times, while the method does it only once. We can generalize the method and rewrite the loop to make this duplication more visible:

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);
  }
  while (remaining >= 1) {
    result.append("I");
    remaining -= 1;
  }
  return result.toString();
}

private static int appendRomanNumerals(int arabic, int value, String romanDigits, StringBuilder builder) {
  int result = arabic;
  while (result >= value) {
    builder.append(romanDigits);
    result -= value;
  }
  return result;
}

This makes it trivial to eliminate it:

private static final int[]    VALUES  = { 9,    5,   4,    1   };
private static final String[] SYMBOLS = { "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();
}

Now we have discovered our algorithm and new cases can be handled by just adding to the arrays:

  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" };

There is still some duplication in the arrays, but one can wonder whether eliminating it would actually improve the code, so we’re just going to leave it as it is. And then there is some duplication in the fact that we have two arrays with corresponding elements. Moving to one array would necessitate the introduction of a new class to hold the value/symbol combination and I don’t think that that’s worth it.

So that concludes our tour of TDD using the Roman Numerals kata. What I really like about this kata is that it is very focused. There is hardly any API design, so coming up with tests is really easy. And the solution isn’t all that complicated either; you only need if and while. This kata really helps you hone your skills of detecting and eliminating duplication, which is a fundamental skill to have when evolving your designs.

Have fun practicing!

Update: Here is a screencast of a better version of the kata:

About these ads

8 Responses to Practicing TDD using the Roman Numerals kata

  1. […] Last time, I got started with JavaScript by doing the Roman Numerals kata. […]

  2. […] Now that I’m all set up, it’s time to do a little exercise to get my feet wet. For this I picked the Roman Numerals kata. […]

  3. Good info. Lucky me I recently found your
    blog by accident (stumbleupon). I have saved as a favorite for later!

  4. [...] one of the immediate benefits of Test Driven Development (TDD), as for example outlined nicely by Ray Sinnema on his blog entry about test-driving a code kata. Our tests that were written “after the fact” often lacked the proper amount of [...]

  5. [...] Reading about something gives only shallow knowledge, so let’s try out the TPP on a small, familiar problem: the Roman Numerals kata. [...]

  6. [...] There are numerous katas that can help you with that, like the Roman Numerals Kata. [...]

  7. [...] are many katas that do just that, like the Roman Numerals Kata. They usually target a specific skill, like Test-Driven Development (TDD). Share [...]

  8. [...] the tests first makes it possible for the tests to drive the design. By formulating your test, in code, in a way that looks natural, you design an API that is [...]

Please Join the Discussion

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 289 other followers