Re-inventing The Wheel

Adrian's Revenge

As I have mentioned before, I am trying to get into TDD, but I was always a little bit intimidated about jumping in head first. I have read a couple of books on TDD, but never actually went through with it. Here are some of the reasons I have been avoiding it:

• Our project at work never used TDD, and is getting so big adding unit tests did not seem feasible.
• I always felt that my projects at home "weren't worthy"
• I wasn't entirely convinced I knew what I was doing

Kent Beck would probably say all of these excuses boiled down to one thing: fear (the intimidation factor, fear of a time sink, fear of failing). I'm hoping that once I gain a little experience, this will lead to confidence, which will lead to less fear.

But here's my problem with gaining experience: without accountability, the proper motivation for me to start using TDD just isn't there. My immediate teammates aren't into TDD (Sampy was, but he moved on), so it would have been weird being the only person on my team involved. And ultimately, my home projects have no accountability either: the only person reviewing my code is me, and the only people using my code are me and my wife. The only people I'd be letting down with my poor code are the twwo of us (and she is all too used to getting let down by me). So, there is no massive incentive to learn this new technique when my goal is to move onto the next project ASAP. I also have a problem with following the examples in the books: they never seemed "real" enough to me. They were either too trivial, or used technology I was lacking in (web services? databases? who uses those?). Plus, I often felt like following along in a book is "cheating".

Of course, it turns out that this blog is the perfect motivation: its work-related, so technically not a waste of Microsoft time. There is accountability, because in theory other people could be reading the posts. So, hopefully we'll be seeing more TDD stuff on here.

But there is still one little problem: I still don't really know what I'm doing. I would like a smaller example that isn't too trivial, and I wouldn't feel badly about screwing up. I wasn't sure what to work on, until I was reading our team's wiki site. I noticed a lot of documents posted by a teammate of mine, Bill Hanlon. My manager Valentina had suggested I speak with him about TDD, saying that he had an exercise he had people work on first, but I never got around to asking him about it. By fate, I happened to stumble upon his example: converting numbers to Roman numerals.

He wrote on the wiki that he came across this idea from a newsgroup posting (I'll link to it at the end) which said that converting to Roman numerals is best correctly done by using a certain technique, and the poster wondered if TDD led people towards using this technique. I won't say what the technique was: I feel a little cheated knowing now what it was because I was worried it would unduly influence my code (I don't think it did, but I could be wrong. We'll see).

I agreed with Bill that this seemed like a nice introduction to TDD: it's an example that is fairly easy (I was pretty sure I could do it all in an afternoon), not too trivial, and even moderately interesting. I'm going to write a running commentary as I go through these steps (something like what Kent Beck did in Test-Driven Development By Example (including all of the seemingly agoninzingly slow baby steps), except probably not nearly as engaging), for 2 reasons:

1. This is a forcing function to actually get me to finally do a TDD exercise
2. This may help others get started who had the same fears that I did

If you are worried that following along would be cheating (as I felt I when reading through the books), then go ahead and go through the exercise on your own and we can compare notes later. I won't be offended if you do that, just make sure you come back later (otherwise, you may be breaking my heart).

Ground Rules

Okay, there is one slight problem with dealing with Roman numerals through TDD: it will be hard to write tests without knowing the right answer. In modern times, here are the usual circumstances a person runs into Roman numerals:

• Movie sequels (I always loved the story of how The Madness of King George was titled in the Stated versus in Britain (check out the IMDB trivia))
• Occassional dates on buildings and movie credits
• Super Bowls (I think the local football club may have been involved with that in some capacity just last year)

I learned about them in grade school, but I only remembered the basics. Just in case you're in the same boat, here is a nice little summary from mathworld.wolfram.com:

Roman numerals are a system of numerical notations used by the Romans. They are an additive (and subtractive) system in which letters are used to denote certain "base" numbers, and arbitrary numbers are then denoted using combinations of symbols. Unfortunately, little is known about the origin of the Roman numeral system (Cajori 1993, p. 30).

The following table gives the Latin letters used in Roman numerals and the corresponding numerical values they represent.

character	numerical value
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

For example, the number 1732 would be denoted MDCCXXXII in Roman numerals. However, Roman numerals are not a purely additive number system. In particular, instead of using four symbols to represent a 4, 40, 9, 90, etc. (i.e., IIII, XXXX, VIIII, LXXXX, etc.), such numbers are instead denoted by preceding the symbol for 5, 50, 10, 100, etc., with a symbol indicating subtraction. For example, 4 is denoted IV, 9 as IX, 40 as XL, etc.

I also found a web page that shows how to convert to and from Roman Numerals: http://www.ivtech.com/roman/. This seems especially useful since:

• It helps me define correct answers
• This is seems a pretty good representation of how I expect the code for this task to go.

I foresee 2 methods that need to be written:

• public static string ToRomanNumeral(int arabic): it converts a number to a Roman Numeral representation (as a string)
• public static int ToArabicNumeral(string roman): converts a string representing a Roman numeral into a number.

The first method will accept numbers 1 - 3999, and issue an exception if the value is out of range. The second will also issue an exception if the string is not formatted correctly.

With those goals in mind, here are the lists of tests I came up with for converting to Roman numerals (we'll start with that one because I think it will be easier):

• 0 (lower boundary case)
• 1 - 11 (some basic cases that oddly don't seem redundant terribly redundant to me. I could be convinced to drop some of them (especially 11), but I want to be a little conservative considering how cheap it is going to be to define and execute these tests).
• 40 (the first "subtraction case" that doesn't involve I)
• 50 (introduces a new digit)
• 90, 100, 400, 500, 900, 1000 (more subtraction cases and new digits)
  3999 (upper bounds)
• 4000 (out of bounds)

I would expect the ToArabicNumeral will have similar cases, but we'll worry about that later.

Creating the projects

I am going to use Visual Studio 2005 Team Suite to write our code and our tests (I feel a little guilty about it, especially knowing what Team Suite costs (ah, the advantages of working at Microsoft!)). If you have an Express or Profesional SKU, I definitely recommend nUnit for writing your tests (I learned about nUnit while going through Test-Driven Development in Microsoft.NET). Most of the work will be the same (it's all just code; I think the major difference is in the attributions and probably different Assert structure).

We start by creating a new C# dll project: RomanNumeralConverter. Lets rename class1.cs to something that makes a little more sense: RomanNumeralConverter.cs (sorry I just need to interject here: it seems like .NET doesn't like this whole "let's have a namespace and a class in that namespace have the same name. It happens to me all the time at home, and I wonder if I am doing something wrong. For the most part, my libraries are pretty isolated between projects, so I don't bother to share them between projects. I would try to avoid separate libraries, but quite often my primary application and libraries are in different languages (most of my applications are now written in C#, but every once in a while I find myself needing to do something using the VB My namespace). Sorry, back to the real event).

Before I write any code (even a method siganture), I want to create my tests. Go to the Test menu on VS, select "New Unit Test" followed by the "Unit Test Wizard". We will be using C#, and lets call the tests RomanNumeralConverterTests. Make sure the RomanNumeralConverter project is selected on the next screen.

Now that we have the projects defined, lets get something to turn red. We have a couple of good candidates for our first test (0 and 1 make the most sense), but I would prefer to test a valid case ahead of a bounds checking case: it justs feels like progress is being made. So, let's test the number 1.

Open RomanNumeralConverterTests.cs and add the following code at the bottom of that class:

        [TestMethod()]
        public void TestToRomanNumeral()
        {
            Assert.AreEqual("I", RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(1));
        }

This method illustrates the signature of the ToRomanNumeral method: static method in the RomanNumeralConverter class, with an int as an input, and a string as an output. Now let's run the test and hope we see some red. Open the Test View window (Test : Windows : Test View) and verify that the TestToRomanNumeral item is selected. Click the "Run Selection" button on the window.

We get a slight problem, a compiler error:

RomanNumeralConverterTest.cs(72,78): error CS0117: 'RomanNumeralConverter.RomanNumeralConverter' does not contain a definition for 'ToRomanNumeral'

(for spacing reasons, I edited the paths down to something more reasonable)

That should be easy enough to fix: let's define this method in RomanNumeralConverter.cs. We already know what the signature should be, its just a matter of filling in the body:

        public static string ToRomanNumeral(int arabic)
        {
            return string.Empty;
        }

Let's build to make sure this compiles, and then try running our tests again:

Failed	TestToRomanNumeral	RomanNumeralConverterTests	Assert.AreEqual failed. Expected:<I>, Actual:<>.

Obviously, returning the empty string was not the way to go (and in case you were wondering returning null wouldn't have been any better, I tried it :-). So, let's update our method to get this test passing:

        public static string ToRomanNumeral(int arabic)
        {
            return "I";
        }

And run our test again:

Failed	TestToRomanNumeral	RomanNumeralConverterTests	Assert.AreEqual failed. Expected:<I>, Actual:<>.

That's a little surprising: I really expected this to work. Well, it turns out that the test classes seems to be pretty lame: they won't automatically re-compile the project that is getting tested. (By the way, this is more than just lame, this seems to be EXTREMELY lame, which makes me wonderif  I did something wrong?). Rebuilding the RomanNumeralConverter project and running the tests again gives us:

Passed	TestToRomanNumeral	RomanNumeralConverterTests

Woo-hoo! Our first green test! Not seeing anything to refactor, let's see what else we can break. I still don't feel like doing the boundary checking, so let's go ahead with 2. Being a noob, I'm not sure what would be the more pragmatic way to write a test here: should I create a new TestMethod for this next case, or is it okay to just add this case to the already defined tests? I'm not sure what the TDD-police would say, but I'm going to go ahead and add this test to the existing method. But if the TDD-police call, I'm not here!

        public void TestToRomanNumeral()
        {
            Assert.AreEqual("I", RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(1));
            Assert.AreEqual("II", RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(2));
        }

This time, the tests show:

Failed	TestToRomanNumeral	RomanNumeralConverterTests	Assert.AreEqual failed. Expected:<II>, Actual:<I>. 	

So, we need to update the code to get 2 working (and also have 1 continue to work, of course). Here's what I did:

        public static string ToRomanNumeral(int arabic)
        {
            if (arabic == 1)
            {
                return "I";
            }
            return "II";
        }

The tests pass:

Passed	TestToRomanNumeral	RomanNumeralConverterTests

And there was much rejoicing. Maybe I'm still a little dense, but I don't see much here to refactor. So, let's go to the next case: 3.

public void TestToRomanNumeral() { // ... Assert.AreEqual("III", RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(3)); }

(Note: from now on, I'm not going to bother showing the full body of this test method: I'll always be adding new test cases to the end; you should be able to keep up. Of course in retrospect, this just seems to strengthen the argument that I should be writing separate tests...).

Another test we expect to fail:

Failed	TestToRomanNumeral	RomanNumeralConverterTests	Assert.AreEqual failed. Expected:<III>, Actual:<II>. 	

And another test that seems to be easy to fix:

        public static string ToRomanNumeral(int arabic)
        {
            if (arabic == 1)
            {
                return "I";
            }
            else if (arabic == 2)
            {
                return "II";
            }
            return "III";
        }

The tests pass (another note: I'm not going to show the passing statements any more, either), but something sure stinks: I'm a little worried that I'm going to end up writing 3999 if statements. There has to be a better way. Well, how about:

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();
            for (int i = 0; i < arabic; i++)
            {
                roman.Append('I');
            }
            return roman.ToString();
        }

Let's keep appending I's onto our string until we have the right value. And this test passes. On to test 4:

        public void TestToRomanNumeral()
        {
            // ...
            Assert.AreEqual("IV", RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(4));
        }

Failed	TestToRomanNumeral	RomanNumeralConverterTests	Assert.AreEqual failed. Expected:<IV>, Actual:<IIII>. 	

Well, our test failed: the code returned "IIII" when it should have returned "IV" (trust me, don't look at the nearest clock for confirmation).

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 3)
            {
                for (int i = 0; i < arabic; i++)
                {
                    roman.Append('I');
                }
            }
            else
            {
                roman.Append("IV");
            }

            return roman.ToString();
        }

This gets the test to pass. I'm feeling a little guilty about this, but I honestly can't think of anything better. So, let's move on to 5:

        public void TestToRomanNumeral()
        {
            // ...
            Assert.AreEqual("V", RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(5));
        }

Failed	TestToRomanNumeral	RomanNumeralConverterTests	Assert.AreEqual failed. Expected:<V>, Actual:<IV>. 	

Same old problem: I think my else statements are getting a bit too open-ended. But I still can't think of anything better:

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 3)
            {
                for (int i = 0; i < arabic; i++)
                {
                    roman.Append('I');
                }
            }
            else if (arabic == 4)
            {
                roman.Append("IV");
            }
            else
            {
                roman.Append('V');
            }

            return roman.ToString();
        }
    }

How about 6?

        public void TestToRomanNumeral()
        {
            // ...
            Assert.AreEqual("VI", RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(6));
        }

Failed	TestToRomanNumeral	RomanNumeralConverterTests	Assert.AreEqual failed. Expected:<VI>, Actual:<V>. 	

The code below again gets this code passing...

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 3)
            {
                for (int i = 0; i < arabic; i++)
                {
                    roman.Append('I');
                }
            }
            else if (arabic == 4)
            {
                roman.Append("IV");
            }
            else if (arabic == 5)
            {
                roman.Append('V');
            }
            else
            {
                roman.Append("VI");
            }

            return roman.ToString();
        }
    }

... but now I feel really guilty about it. It seems like we're moving from 3999 if statements to 3997. Is this really progress? Maybe 7 will provide a revelation:

        public void TestToRomanNumeral()
        {
            // ...
            Assert.AreEqual("VII", RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(7));
        }

Failed	TestToRomanNumeral	RomanNumeralConverterTests	Assert.AreEqual failed. Expected:<VII>, Actual:<VI>.

This is getting frustrating, but nothing has hit me yet:

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 3)
            {
                for (int i = 0; i < arabic; i++)
                {
                    roman.Append('I');
                }
            }
            else if (arabic == 4)
            {
                roman.Append("IV");
            }
            else if (arabic == 5)
            {
                roman.Append('V');
            }
            else if (arabic == 6)
            {
                roman.Append("VI");
            }
            else
            {
                roman.Append("VII");
            }

            return roman.ToString();
        }

Of course, this passes as well. This whole thing is starting to sound familiar. Where have I heard this before? Suddenly it hits me: didn't Bart Simpson have a problem with trying to figure out Roman numerals? It turns out he did: (from the Lemon of Troy episode):

Bart: Think, Bart. Where have you seen roman numerals before? I know...Rocky V ["vee"]! That was the fifth one. So, Rocky five plus Rocky two equals...Rocky VII! "Adrian's Revenge"!

(This episode also features the following line uttered by Mrs. Krabappel, Bart's teacher: "If you don't learn Roman numerals, you'll never know the date certain motion pictures were copyrighted.")

If Bart was able to figure it out, we should as well: if we can get 5 and 2 working, we should be able to get 7:

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 3)
            {
                for (int i = 0; i < arabic; i++)
                {
                    roman.Append('I');
                }
            }
            else if (arabic == 4)
            {
                roman.Append("IV");
            }
            else if (arabic == 5)
            {
                roman.Append('V');
            }
            else if (arabic > 5)
            {
                roman.Append('V');
                roman.Append(ToRomanNumeral(arabic - 5));
            }
            return roman.ToString();
        }

The test still passes. Now let's look to refactor. I see 2 roman.Append('V') statements. Lets try to get rid of this redundancy:

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 3)
            {
                for (int i = 0; i < arabic; i++)
                {
                    roman.Append('I');
                }
            }
            else if (arabic == 4)
            {
                roman.Append("IV");
            }
            else if (arabic >= 5)
            {
                roman.Append('V');
                roman.Append(ToRomanNumeral(arabic - 5));
            }
            return roman.ToString();
        }

And our tests still pass. But there is something here that stinks: we have a recursive method, but I have absolutely no faith in our base case (indeed, it looks like we have 2 base cases). This doesn't seem safe. Maybe its time to test our lower bounds more explicitly. Lets add a test for out of range characters. This seems like a totally separate case, so I'm actually going to create a new TestMethod this time around.

I didn't see a good built-in way to verify that our code throws an exception, so I'm going to write a helper function that catches the expected exception and returns true if the exception is issued, and false if no exception is issued:

        [TestMethod()]
        public void TestOutOfRangeArabic()
        {
            Assert.IsTrue(VerifyException(0), "OverflowException not issued as expected");
        }

        private bool VerifyException(int testValue)
        {
            try
            {
                RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(testValue);
            }
            catch (OverflowException)
            {
                return true;
            }
            catch (Exception)
            {
                return false;
            }
            return false;
        }

Running our tests again shows that this new test fails:

Passed	TestToRomanNumeral	RomanNumeralConverterTests		
Failed	TestOutOfRangeArabic	RomanNumeralConverterTests	Assert.IsTrue failed. OverflowException not issued as expected	

This leads to the following code:

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 0)
            {
                throw new OverflowException("Value was either too large or too small for a Roman Numeral");
            }

            if (arabic <= 3)
            {
                for (int i = 0; i < arabic; i++)
                {
                    roman.Append('I');
                }
            }
            else if (arabic == 4)
            {
                roman.Append("IV");
            }
            else if (arabic >= 5)
            {
                roman.Append('V');
                roman.Append(ToRomanNumeral(arabic - 5));
            }
            return roman.ToString();
        }

(How did I come up with that exception type and text? Try Int32.Parse(1000000000000) and see what you get). Running the tests now yields:

Failed	TestToRomanNumeral	RomanNumeralConverterTests	Test method RomanNumeralConverterTests.RomanNumeralConverterTest.TestToRomanNumeral threw exception:  System.OverflowException: Value was either too large or too small for a Roman Numeral.	
Passed	TestOutOfRangeArabic	RomanNumeralConverterTests		

Well, that's close: I got the test which had been failing to succeed, but the test that had been succeeding is now failing. It turns out then when we pass in 5, we make a recursive call with 0, which issues the exception. Let's update our code:

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 0)
            {
                throw new OverflowException("Value was either too large or too small for a Roman Numeral");
            }

            if (arabic <= 3)
            {
                for (int i = 0; i < arabic; i++)
                {
                    roman.Append('I');
                }
            }
            else if (arabic == 4)
            {
                roman.Append("IV");
            }
            else if (arabic >= 5)
            {
                roman.Append('V');
                if (arabic > 5)
                {
                    roman.Append(ToRomanNumeral(arabic - 5));
                }
            }
            return roman.ToString();
        }

Now both tests are passing. (Note: looking back on this now that I have finished the exercise, it seems a little strange to have that for loop in with the recursive call. Why didn't I convert this for loop to a recursive call? (And why didn't I make it recursive to begin with?). Sorry, this is just the way it turned out.)

On to test 8:

        public void TestToRomanNumeral()
        {
            // ...
            Assert.AreEqual("VIII", RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(8));
        }

Actually, this test passes out of the gate: no need to change code! (I learned the hard way to run a test once its written to make sure that it is really red. Trust me: Assert.Equals and Assert.AreEqual don't do the same thing!).

I'm feeling a little better about my recursive call (but a little bit worse about having a testcase of 8. Should I get rid of it? I don't think I will, since its alreaday written and passing). The test for 9:

        public void TestToRomanNumeral()
        {
            // ...
            Assert.AreEqual("IX", RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(9));
        }

Failed	TestToRomanNumeral	RomanNumeralConverterTests	Assert.AreEqual failed. Expected:<IX>, Actual:<VIV>.

Our recursive call failed us here: 5 + 4 does equal 9, but it looks like we need another special case. I'm feeling incredibly dense, but I still haven't thought of anything better but another special case:

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 0)
            {
                throw new OverflowException("Value was either too large or too small for a Roman Numeral");
            }

            if (arabic <= 3)
            {
                for (int i = 0; i < arabic; i++)
                {
                    roman.Append('I');
                }
            }
            else if (arabic == 4)
            {
                roman.Append("IV");
            }
            else if (arabic >= 5 && arabic < 9)
            {
                roman.Append('V');
                if (arabic > 5)
                {
                    roman.Append(ToRomanNumeral(arabic - 5));
                }
            }
            else if (arabic >= 9)
            {
                roman.Append("IX");
            }
            return roman.ToString();
        }

Both tests pass, but I'm officially feeling uncomfortable. Forging ahead with 10:

        public void TestToRomanNumeral()
        {
            // ...
            Assert.AreEqual("X", RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(10));
        }

Failed	TestToRomanNumeral	RomanNumeralConverterTests	Assert.AreEqual failed. Expected:<X>, Actual:<IX>. 	

One more special case gets this passing:

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 0)
            {
                throw new OverflowException("Value was either too large or too small for a Roman Numeral");
            }

            if (arabic <= 3)
            {
                for (int i = 0; i < arabic; i++)
                {
                    roman.Append('I');
                }
            }
            else if (arabic == 4)
            {
                roman.Append("IV");
            }
            else if (arabic >= 5 && arabic < 9)
            {
                roman.Append('V');
                if (arabic > 5)
                {
                    roman.Append(ToRomanNumeral(arabic - 5));
                }
            }
            else if (arabic == 9)
            {
                roman.Append("IX");
            }
            else
            {
                roman.Append('X');
            }
            return roman.ToString();
        }

Yuck. Enough is enough: we need to refactor. The first thing I want to do is get rid of that repeating 9. Let's turn the if statements upside down, and keep decrementing arabic as we go. This is essentially what the recursive calls were doing, but now the if statements are done in a more logical order:

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 0)
            {
                throw new OverflowException("Value was either too large or too small for a Roman Numeral");
            }

            if (arabic >= 10)
            {
                roman.Append('X');
                arabic = arabic - 10;
            }
            if (arabic == 9)
            {
                roman.Append("IX");
                arabic = arabic - 9;
            }
            if (arabic >= 5)
            {
                roman.Append('V');
                arabic = arabic - 5;
            }
            if (arabic == 4)
            {
                roman.Append("IV");
                arabic = arabic - 4;
            }
            while (arabic > 0)
            {
                roman.Append('I');
                arabic--;
            }
            return roman.ToString();
        }

The tests still pass, and I'm a little less disappointed in the code. Note that I changed the for loop to a while loop, since that seems more consistent with the rest of the code. Notice that it seems to be following the same pattern:

• test arabic against a value
• if match, append a character
• update arabic

It seems like we could refactor all of these repetitions into a helper method (a more adventuresome person might try to use the the "Factor: Extract method" feature). Let's try it with 10 first and see what we get:

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 0)
            {
                throw new OverflowException("Value was either too large or too small for a Roman Numeral");
            }

            AddDigitToString(ref arabic, 10, "X", roman);
            if (arabic == 9)
            {
                roman.Append("IX");
                arabic = arabic - 9;
            }
            if (arabic >= 5)
            {
                roman.Append('V');
                arabic = arabic - 5;
            }
            if (arabic == 4)
            {
                roman.Append("IV");
                arabic = arabic - 4;
            }
            while (arabic > 0)
            {
                roman.Append('I');
                arabic--;
            }
            return roman.ToString();
        }

        private static void AddDigitToString(ref int arabic, int value, string romanDigit, StringBuilder roman)
        {
            if (arabic >= value)
            {
                roman.Append(romanDigit);
                arabic = arabic - value;
            }
        }

Both tests are still passing, so let's finish off the rest of these:

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 0)
            {
                throw new OverflowException("Value was either too large or too small for a Roman Numeral");
            }

            AddDigitToString(ref arabic, 10, "X", roman);
            AddDigitToString(ref arabic, 9, "IX", roman);
            AddDigitToString(ref arabic, 5, "V", roman);
            AddDigitToString(ref arabic, 4, "IV", roman);
            while (arabic > 0)
            {
                roman.Append('I');
                arabic--;
            }
            return roman.ToString();
        }

And our tests still pass. What about 11?

        public void TestToRomanNumeral()
        {
            // ...
            Assert.AreEqual("XI", RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(11));
        }

That one works out of the gate as well, and I'm pretty confident 12 through 19 will as well. 20? Not so sure, I think there will be a problem here. I hadn't originally planned on testing this, but I think I missed a testcase from my initial list. Let's see:

        public void TestToRomanNumeral()
        {
            // ...
            Assert.AreEqual("XX", RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(20));
        }

Failed	TestToRomanNumeral	RomanNumeralConverterTests	Assert.AreEqual failed. Expected:<XX>, Actual:<XIXI>. 	

So our string was built up by 10, 9, and 1. Really what we want to do is get all of the X's out of the way up front, and then going on to the rest:

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 0)
            {
                throw new OverflowException("Value was either too large or too small for a Roman Numeral");
            }

            while (arabic >= 10)
            {
                AddDigitToString(ref arabic, 10, "X", roman);
            }
            AddDigitToString(ref arabic, 9, "IX", roman);
            AddDigitToString(ref arabic, 5, "V", roman);
            AddDigitToString(ref arabic, 4, "IV", roman);
            while (arabic > 0)
            {
                roman.Append('I');
                arabic--;
            }
            return roman.ToString();
        }

This gets the tests passing; 30 feels like another redundant test, but what the heck:

        public void TestToRomanNumeral()
        {
            // ...
            Assert.AreEqual("XXX", RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(30));
        }

Yep, this passed right away. Oh, well. Let's try 40:

        public void TestToRomanNumeral()
        {
            // ...
            Assert.AreEqual("XL", RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(40));
        }

Failed	TestToRomanNumeral	RomanNumeralConverterTests	Assert.AreEqual failed. Expected:<XL>, Actual:<XXXX>. 	

4 X's is not the way to go here, let's add another special case:

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 0)
            {
                throw new OverflowException("Value was either too large or too small for a Roman Numeral");
            }

            AddDigitToString(ref arabic, 40, "XL", roman);
            while (arabic >= 10)
            {
                AddDigitToString(ref arabic, 10, "X", roman);
            }
            AddDigitToString(ref arabic, 9, "IX", roman);
            AddDigitToString(ref arabic, 5, "V", roman);
            AddDigitToString(ref arabic, 4, "IV", roman);
            while (arabic > 0)
            {
                roman.Append('I');
                arabic--;
            }
            return roman.ToString();
        }

Tests pass; let's go to 50:

        public void TestToRomanNumeral()
        {
            // ...
            Assert.AreEqual("L", RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(50));
        }

Failed	TestToRomanNumeral	RomanNumeralConverterTests	Assert.AreEqual failed. Expected:<L>, Actual:<XLX>. 	

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 0)
            {
                throw new OverflowException("Value was either too large or too small for a Roman Numeral");
            }

            AddDigitToString(ref arabic, 50, "L", roman);
            AddDigitToString(ref arabic, 40, "XL", roman);
            while (arabic >= 10)
            {
                AddDigitToString(ref arabic, 10, "X", roman);
            }
            AddDigitToString(ref arabic, 9, "IX", roman);
            AddDigitToString(ref arabic, 5, "V", roman);
            AddDigitToString(ref arabic, 4, "IV", roman);
            while (arabic > 0)
            {
                roman.Append('I');
                arabic--;
            }
            return roman.ToString();
        }

I'm really liking this helper function. Things are moving along much faster. 51 - 89 should be redundant. I don't think there are any curveballs out there: everything should be 50 + a number between 1 and 39. 90 is different:

        public void TestToRomanNumeral()
        {
            // ...
            Assert.AreEqual("XC", RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(90));
        }

Failed	TestToRomanNumeral	RomanNumeralConverterTests	Assert.AreEqual failed. Expected:<XC>, Actual:<LXL>. 

Add in our special case for 90 as well.

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 0)
            {
                throw new OverflowException("Value was either too large or too small for a Roman Numeral");
            }

            AddDigitToString(ref arabic, 90, "XC", roman);
            AddDigitToString(ref arabic, 50, "L", roman);
            AddDigitToString(ref arabic, 40, "XL", roman);
            while (arabic >= 10)
            {
                AddDigitToString(ref arabic, 10, "X", roman);
            }
            AddDigitToString(ref arabic, 9, "IX", roman);
            AddDigitToString(ref arabic, 5, "V", roman);
            AddDigitToString(ref arabic, 4, "IV", roman);
            while (arabic > 0)
            {
                roman.Append('I');
                arabic--;
            }
            return roman.ToString();
        }

This works, but the old failure sort of rang a bell: "Expected:<XC>, Actual:<LXL>" is very similar to "Expected:<IX>, Actual:<VIV>", the failure we received when testing 9. And now it seems evident to me that there is a pattern I had missed before. Let's re-write this a little bit, and take a closer look:

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 0)
            {
                throw new OverflowException("Value was either too large or too small for a Roman Numeral");
            }

            AddDigitToString(ref arabic, 90, "XC", roman);
            AddDigitToString(ref arabic, 50, "L", roman);
            AddDigitToString(ref arabic, 40, "XL", roman);
            while (arabic >= 10)
            {
                AddDigitToString(ref arabic, 10, "X", roman);
            }

            AddDigitToString(ref arabic, 9, "IX", roman);
            AddDigitToString(ref arabic, 5, "V", roman);
            AddDigitToString(ref arabic, 4, "IV", roman);
            while (arabic >= 1)
            {
                AddDigitToString(ref arabic, 1, "I", roman);
            }

            return roman.ToString();
        }

What's the difference? I added a single newline and changed the second while loop a little bit. Notice the pattern? The numbers between the 2 groups are different by exactly a factor of 10, and the Roman Numerals are different, but otherwise these are pretty much the same. Let's move the top set into a function, and see what that gets us:

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 0)
            {
                throw new OverflowException("Value was either too large or too small for a Roman Numeral");
            }

            AddDigitRangeToString(ref arabic, 100, "C", 50, "L", 10, "X", roman);

            AddDigitToString(ref arabic, 9, "IX", roman);
            AddDigitToString(ref arabic, 5, "V", roman);
            AddDigitToString(ref arabic, 4, "IV", roman);
            while (arabic >= 1)
            {
                AddDigitToString(ref arabic, 1, "I", roman);
            }

            return roman.ToString();
        }

        private static void AddDigitRangeToString(ref int arabic, int highValue, string highDigit, int middleValue, string middleDigit, int lowValue, string lowDigit, StringBuilder roman)
        {
            AddDigitToString(ref arabic, highValue - lowValue, lowDigit + highDigit, roman);
            AddDigitToString(ref arabic, middleValue, middleDigit, roman);
            AddDigitToString(ref arabic, middleValue - lowValue, lowDigit + middleDigit, roman);
            while (arabic >= lowValue)
            {
                AddDigitToString(ref arabic, lowValue, lowDigit, roman);
            }
        }

The tests still pass, so lets do the same for the bottom group:

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 0)
            {
                throw new OverflowException("Value was either too large or too small for a Roman Numeral");
            }

            AddDigitRangeToString(ref arabic, 100, "C", 50, "L", 10, "X", roman);
            AddDigitRangeToString(ref arabic, 10, "X", 5, "V", 1, "I", roman);

            return roman.ToString();
        }

One last bit of redundancy: the 10 and the X appear twice; do I want to fix this, or am I feeling lazy? Lazy. Let's go on to 100:

        public void TestToRomanNumeral()
        {
            // ...
            Assert.AreEqual("C", RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(100));
        }

Failed	TestToRomanNumeral	RomanNumeralConverterTests	Assert.AreEqual failed. Expected:<C>, Actual:<XCX>. 	

So, we ended up with 90 and 10. Let's use our original helper method with 100:

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 0)
            {
                throw new OverflowException("Value was either too large or too small for a Roman Numeral");
            }

            AddDigitToString(ref arabic, 100, "C", roman);
            AddDigitRangeToString(ref arabic, 100, "C", 50, "L", 10, "X", roman);
            AddDigitRangeToString(ref arabic, 10, "X", 5, "V", 1, "I", roman);

            return roman.ToString();
        }

This is starting to sound familiar, too (even though the tests now pass). I want to add the 200 test next:

        public void TestToRomanNumeral()
        {
            // ...
            Assert.AreEqual("CC", RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(200));
        }

Failed	TestToRomanNumeral	RomanNumeralConverterTests	Assert.AreEqual failed. Expected:<CC>, Actual:<CXCX>. 	

Very familiar indeed: I had a very similar message when trying to convert 20 (Expected:<XX>, Actual:<XIXI>). I'm definitely sensing a pattern: all my errors for 400, 500, and 900 are going to look like those for 40, 50, and 90. I'm feeling bold, so let's go ahead and add our digit range helper to get this test working:

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 0)
            {
                throw new OverflowException("Value was either too large or too small for a Roman Numeral");
            }

            AddDigitRangeToString(ref arabic, 1000, "M", 500, "D", 100, "C", roman);
            AddDigitRangeToString(ref arabic, 100, "C", 50, "L", 10, "X", roman);
            AddDigitRangeToString(ref arabic, 10, "X", 5, "V", 1, "I", roman);

            return roman.ToString();
        }

Tests all pass. Let's add the tests for 400, 500, and 900 to see how that works (this time, I skipped 300 because I thought the 30 test was redundant, and 300 is pretty much the same deal).

        public void TestToRomanNumeral()
        {
            // ...
            Assert.AreEqual("CD", RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(400));
            Assert.AreEqual("D", RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(500));
            Assert.AreEqual("CM", RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(900));
        }

Those also pass. Are they redundant? I'm starting to think they are: it might be better to be testing our helper functions directly, and simply testing our base cases (1, 5, 10, 50, 100, 500, 1000) directly. However, I feel that these functions are better being private, so I'm not sure its possible to test these helpers directly.

Anything to refactor? Sure seems like it: the (100, "C") and (10, "X") pairs appear twice. Now that I notice how I wrote that, it seems a little strange to leave the value and the representation of the value decoupled. Let's create a struct which encompasses both:

        struct RomanTuple
        {
            public int Value;
            public string Digit;

            public RomanTuple(int value, string digit)
            {
                Value = value;
                Digit = digit;
            }
        }

Why a struct? I feel a full-blown class here would be overkill; maybe I'm too old-school. But I can't think of any methods I would want done on a tuple, so I'll leave it a struct. Also note that I left these things as strings rather than using chars: my heart says to use char, but my head says string: they are easier to concatenate. So, using this struct we get:

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 0)
            {
                throw new OverflowException("Value was either too large or too small for a Roman Numeral");
            }

            RomanTuple thousand = new RomanTuple(1000, "M");
            RomanTuple fiveHundred = new RomanTuple(500, "D");
            RomanTuple oneHundred = new RomanTuple(100, "C");
            RomanTuple fifty = new RomanTuple(50, "L");
            RomanTuple ten = new RomanTuple(10, "X");
            RomanTuple five = new RomanTuple(5, "V");
            RomanTuple one = new RomanTuple(1, "I");

            AddDigitRangeToString(ref arabic, thousand, fiveHundred, oneHundred, roman);
            AddDigitRangeToString(ref arabic, oneHundred, fifty, ten, roman);
            AddDigitRangeToString(ref arabic, ten, five, one, roman);

            return roman.ToString();
        }

        private static void AddDigitRangeToString(ref int arabic, RomanTuple high, RomanTuple middle, RomanTuple low, StringBuilder roman)
        {
            AddDigitToString(ref arabic, high.Value - low.Value, low.Digit + high.Digit, roman);
            AddDigitToString(ref arabic, middle.Value, middle.Digit, roman);
            AddDigitToString(ref arabic, middle.Value - low.Value, low.Digit + middle.Digit, roman);
            while (arabic >= low.Value)
            {
                AddDigitToString(ref arabic, low.Value, low.Digit, roman);
            }
        }

Technically, this change added code, but I think it is a little more readable. Which is a trade-off I will take any day of the week, especially if the tests still pass (and they do).

We only have 3 tests left (at least for conversion to Roman Numerals): 1000, 3999 and 4000. Let's finish off 1000 and 3999 in one go:

        public void TestToRomanNumeral()
        {
            // ...
            Assert.AreEqual("M", RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(1000));
            Assert.AreEqual("MMMCMXCIX", RomanNumeralConverter.RomanNumeralConverter.ToRomanNumeral(3999));
        }

Failed	TestToRomanNumeral	RomanNumeralConverterTests	Assert.AreEqual failed. Expected:<M>, Actual:<CMC>. 	

Let's add a familiar while loop to take care of both of these:

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 0)
            {
                throw new OverflowException("Value was either too large or too small for a Roman Numeral");
            }

            RomanTuple thousand = new RomanTuple(1000, "M");
            RomanTuple fiveHundred = new RomanTuple(500, "D");
            RomanTuple oneHundred = new RomanTuple(100, "C");
            RomanTuple fifty = new RomanTuple(50, "L");
            RomanTuple ten = new RomanTuple(10, "X");
            RomanTuple five = new RomanTuple(5, "V");
            RomanTuple one = new RomanTuple(1, "I");

            while (arabic >= thousand.Value)
            {
                AddDigitToString(ref arabic, thousand.Value, thousand.Digit, roman);
            }
            AddDigitRangeToString(ref arabic, thousand, fiveHundred, oneHundred, roman);
            AddDigitRangeToString(ref arabic, oneHundred, fifty, ten, roman);
            AddDigitRangeToString(ref arabic, ten, five, one, roman);

            return roman.ToString();
        }

Tests pass. Moving on to the last test:

        public void TestOutOfRangeArabic()
        {
            Assert.IsTrue(VerifyException(0), "OverflowException not issued as expected");
            Assert.IsTrue(VerifyException(4000), "OverflowException not issued as expected");
        }

Failed	TestOutOfRangeArabic	RomanNumeralConverterTests	Assert.IsTrue failed. OverflowException not issued as expected

Is easily solved with another up-front check:

        public static string ToRomanNumeral(int arabic)
        {
            StringBuilder roman = new StringBuilder();

            if (arabic <= 0 || arabic >= 4000)
            {
                throw new OverflowException("Value was either too large or too small for a Roman Numeral");
            }

            RomanTuple thousand = new RomanTuple(1000, "M");
            RomanTuple fiveHundred = new RomanTuple(500, "D");
            RomanTuple oneHundred = new RomanTuple(100, "C");
            RomanTuple fifty = new RomanTuple(50, "L");
            RomanTuple ten = new RomanTuple(10, "X");
            RomanTuple five = new RomanTuple(5, "V");
            RomanTuple one = new RomanTuple(1, "I");

            while (arabic >= thousand.Value)
            {
                AddDigitToString(ref arabic, thousand.Value, thousand.Digit, roman);
            }
            AddDigitRangeToString(ref arabic, thousand, fiveHundred, oneHundred, roman);
            AddDigitRangeToString(ref arabic, oneHundred, fifty, ten, roman);
            AddDigitRangeToString(ref arabic, ten, five, one, roman);

            return roman.ToString();
        }

Conclusion

We worked on writing a function to convert a number to its Roman numeral equivalent by using TDD (we'll save the converse for a different blog entry) and the tools for TDD within Visual Studio. Along the way, I probably wrote the longest blog entry in the history of the world.

Anyway, the newsgroup posting I alluded to earlier claimed that the proper technique for the conversion is to use a table. My solution is pretty close once you think of my RomanTuple definitions as table entries. The big differences between the my solution and that on the site is

• I didn't go all the way and put my tuples into an array that I could iterate over
• I have fewer tuples 
• I refused to write a loop that I knew wouldn't execute more than once (my calls to AddDigitToString). Possibly a result of previous point.

What does all this mean? I'm not really sure. Bill's solution was basically the same as that on the site, so I guess I lose :-). At the very least, I need more practice. (The site also had some more test cases which I may have missed). I also wonder if I would have happened upon a different solution if I had known I wasn't writing this up for the blog: I think my solution is more readable, but maybe that's just an indicator of how I think.

But at least I think I found my interview question should I ever be involved on a hiring loop.