The Challenge

My latest challenge to my database programming students was to create a C# class that would perform various number conversions, starting with Arabic numbers (0 to 3999) to Roman numerals and vice versa.

I required that all public functions in the class needed to be declared as static, so that they could be called from outside the class without having to create a new instance. Also, the class was to be completely portable;  it must not use any functions such as message boxes that would prevent them from copying the entire class into any other type of project and referencing it.  Of course, all code must also have error handling and commenting.

My students came up with various solutions and I think some had more help from StackOverflow than others.  I know that one of them learned the hard way not to search for “XXX” on Google.

One popular strategy was to use the C# Dictionary class to hold the Roman characters and their equivalents.  I don’t always get around to writing up my own solutions to these challenges before I assign them, so I happily swiped that strategy for my own code which was otherwise written from scratch. I ended up using the SortedDictionary class instead.

Getting Retro with Roman Numerals

You can view the entire commented class on GithubGist but I thought I’d throw in some highlights, starting with the Arabic to Roman conversion.

The standard Dictionary class worked without a problem each time I tested it but the SortedDictionary was almost identical and ensures that the entries will always be returned in the same order. The only difference was that it’s sorted from the smallest key value.

Standard Roman numerals go up to 3999 (MMMCMXCIX).  The traditional method for going higher is to put an overline on the characters, starting with V, to multiply them by 1000.  This was a bit much for a simple conversion class so I settled for limiting the input to 3999. On the plus side, I did get to show my students another example of how errors are handled in .NET.

The rest of the algorithm goes as follows:

1. Get the first dictionary entry starting with 1000 and assign the key and value to variables.
2. Determine the sublevel for that number at which subtractive notation must be used (i.e. 900 = CM, 400 = CD, 10 = IX).  Store that in a variable.
3. The input number is continually reduced by subtracting the current dictionary key and adding the appropriate Roman letters to the string.
   • If the input number remains above the numeric equivalent of the current Roman symbol (i.e. 1000), then that number is subtracted and the Roman letter is added (i.e. 2014 would have M added twice.)
   • If there are already three of the same letter at the end of the string, remove them and add the right subtractive notation (i.e. III becomes IV).
4. If the input number is in the range where subtractive notation must be used, look for the correct Roman letter to append before the current letter. (i.e. The current letter is M and then the number reduces to 920 which starts with CM. The code determines that C is the correct letter to put before M.)
5. Subtract the value added to the Roman numberal from the input number.
6. If the input number falls below the subtractive level, retrieve the values from the next dictionary entry and test again until it reaches 0.

Normally, I can do Roman numerals in my head or on paper in a second or two. Some of my students were probably less familiar with them at this point. Either way, the process of breaking down the rules for the conversion in a way that could be put into code was an interesting one. I also looked around the Internet for solutions at first and saw a few different methods including one that used recursion that I’ll have to bring up when I teach my students about that.  I really wanted to do this from scratch, though, so I did and it was more fun.

One challenge was determining the correct subtractive letter at each point.  “X” is the subtractive element for both 50 and 100 (XL = 40, XC = 100) so there had to be a formula that would tell the code to use that one for both.  I came up with this:

arabicSubLevel = arabicNumber - ((arabicNumber.ToString()[0] == '1') ? 
        (arabicNumber / 10) : (arabicNumber / 5));

The ?: operation is a simplified IF … THEN operation. The formula says “If the first digit in the number is 1, then divide the current number by 10. otherwise divide by 5.  Subtract the result from the current number being used.”

This means that if the number being subtracted by the input value is 1000, it will divide by 10 and get 100.  If we’re at the dictionary entry for 500, it will divide by 5 and still get C as the subtractive letter.

Back to the Present

Roman to Arabic was quite a bit easier and the algorithm was as follows:

1. Start with the first letter of the string (C = 100).
2. If the letter after that (D = 500) is worth more than the first one, subtract the value of the first letter from the second and add the result to the return value.
   (i.e. “CD”:  500 (D) – 100 (C) = 400).
3. If the next letter is worth less according to the dictionary, just add the value of the current letter to the return value.
4. If subtractive notation is used, move forward to characters in the Roman numeral string, otherwise just move forward 1.
5. Repeat the process.

Then I remembered that I needed to evaluate the input Roman numeral strings to ensure that they were well formed and didn’t contain any invalid characters or combinations.  That’s when it got trickier but I did it and you can see the results on GithubGist.

Testing

The great thing about this kind of class is that it’s easy to throw a huge number of tests at it really quickly.  I created a Windows form with a button and the following code in the click event:

 private void btnFill_Click(object sender, EventArgs e)
 {
   string romanNumeral;
   lbNumbers.Items.Clear();
   for(int x = 1; x < 4000; x++)
   {
     romanNumeral = NumericConversions.ArabicToRoman(x);
     lbNumbers.Items.Add(NumericConversions.RomanToArabic(romanNumeral));
   }
 }

This tests both functions by converting an integer to Roman and then back again and inserting the result in a ListBox which can be quickly scanned for errors. It took about 2 seconds on my primary machine.

So, at this point, my students have converted between decimal and binary in SQL and between Arabic and Roman in C#.  I haven’t introduced them to Hexidecimal or Octal yet but this just might have been the right project to desensitize them to the point where they won’t panic too much.