Roman Numeral Coding Challenge - Developer Decisions

Tue, Jun 25, 2019

Read in 5 minutes

I decided to do a simple coding challenge but I wanted to apply more real world considerations to the scenario and go through the decisions a developer would have to make.

Roman Numeral Coding Challenge - Developer Decisions

What is the challenge

Write a method that accepts an integer (between 1 and 3,999 inclusive) and returns a string. The string should be the value of the number accepted in the form of roman numerals. If the number is outside of the constraints, an exception should be thrown.

Handling the exceptions

As constraints can change from time to time, we don’t want them to be too difficult to find. As a result, I’m going to declare them as constants at the top of the library.

const int minimumValue = 1;
const int maximumValue = 3999;

Developers have different approaches to handling constraints. As a preference, I prefer them handled straight away at the top of the method but within a region so that I can close them off when working on the method.

public static string ConvertIntToRomanNumerals(int number)
{
      #region Constraints
      if (number < minimumValue)
      {
          throw new ArgumentOutOfRangeException("The number to convert to roman numerals needs to be greated than " + (minimumValue - 1) + ".");
      }
      if (number > maximumValue)
      {
          throw new ArgumentOutOfRangeException("The number to convert to roman numerals needs to be less than " + (maximumValue + 1) + ".");
      }
      #endregion Constraints
}

Roman Numeral Data Collection

Now that we have the constraints out of the way, we are going to need some form of a data collection to store the roman numeral characters and their associated numbers. What are our choices?

Narrowing it down ….

Under the hood, a Dictionary uses KeyValuePair’s. The Dictionary object has a major advantage when iterating through HashCodes. As we aren’t using these, lets rule out using a Dictionary.

Lets compare Tuples by looking at benchmarking.

8.3944 allocation, Tuple

0.4949 allocation, KeyValuePair

0.3457 allocation, Tuple literal (FASTEST)

2.16168 argument, Tuple

2.17551 argument, KeyValuePair

2.17316 argument, Tuple literal

1.84421 return, Tuple (FASTEST)

5.42422 return, KeyValuePair

5.32932 return, Tuple literal

2.44545 load, Tuple

3.27982 load, KeyValuePair

2.56207 load, Tuple literal

Literal Tuple has an 8ms allocation advantage. Whereas there is only a 4ms advantage to Tuple’s on returning the values. As this is a simple task, we will most likely be only allocating and returning once per entry. Therefore, we have the biggest advantage using Literal Tuples.

The final comparison - Literal Tuple vs KeyValuePair’s

In terms of performance, the Literal Tuple wins hands down. For applications requiring the very best in performance we have our answer. However, not all coding is about performance. A KeyValuePair carries a semantic meaning with it. It tells the developer that there is a relationship between the key and value. They aren’t just properties being passed. This subtle indication to another developer makes your code more much more readable.

As performance isn’t our major concern, I’m going to use a list of KeyValuePair’s.

Implementing the data collection

#region Data Values Setup

List<KeyValuePair<int, string>> numeralValues = new List<KeyValuePair<int, string>>();
numeralValues.Add(new KeyValuePair<int, string>(1000, "M"));
numeralValues.Add(new KeyValuePair<int, string>(900, "CM"));
numeralValues.Add(new KeyValuePair<int, string>(500, "D"));
numeralValues.Add(new KeyValuePair<int, string>(400, "CD"));
numeralValues.Add(new KeyValuePair<int, string>(100, "C"));
numeralValues.Add(new KeyValuePair<int, string>(90, "XC"));
numeralValues.Add(new KeyValuePair<int, string>(50, "L"));
numeralValues.Add(new KeyValuePair<int, string>(40, "XL"));
numeralValues.Add(new KeyValuePair<int, string>(10, "X"));
numeralValues.Add(new KeyValuePair<int, string>(9, "IX"));
numeralValues.Add(new KeyValuePair<int, string>(5, "V"));
numeralValues.Add(new KeyValuePair<int, string>(4, "IV"));
numeralValues.Add(new KeyValuePair<int, string>(1, "I"));
#endregion Data Values Setup

Like the constraints, the code here is rarely going to change. When working on the method, the collection contents will only occasionally be reviewed by the developer. Therefore, I’ve wrapped the collection in another region so it can be collapsed out of the way.

You’ll notice the collection is in reverse numerical order. This is an intentional decision.

We could have the collection in any order and use a sorting method to ensure 100% that, when iteration occurs, the items in the collection are processed in the correct order. However, we are going to have unit testing for the code that will identify issues cause by the collection being in the wrong order. Therefore, I feel confident that the performance hit that comes with the sorting will not be required and we can sort the order manually at design time.

Storing the string as we iterate

We have one final decision. We are going to be building up our response piece by piece. We have 3 options.

We can easily remove the final option as we don’t know what the capacity will be. Looking a string and StringBuilder benchmarking we can see see that there is a switch in performance winner at 6 and 8 concatenations with simple string concatenation winning for a smaller number of concatenations.

In this simple program, we could argue that the maximum number of iterations will be kept low by the constraints and we should, therefore, go with the string option. However, what happens if the constraint is lifted in the future? This could have a significant performance impact. Personally, I prefer a defensive programming style that promotes stability. Therefore, I will choose a StringBuilder in this instance.

All decisions made, lets program the logic

// Build the output
StringBuilder sbOutput = new StringBuilder();
foreach (var numeralValue in numeralValues)
{
      while (number >= numeralValue.Key)
      {
            sbOutput.Append(numeralValue.Value);
            number -= numeralValue.Key;
      }
}
return sbOutput.ToString();

What’s happening here? We iterate through the values in the data collection, This is where order is import as we want 5 = V and not IIIII. If the current number is greater than the value we can reduce the number left to be converted and add to associated numeral to the output.

Loop, repeat and output.

Do you have a better approach? Let me know!

Source Code: https://github.com/cfelstead/Roman-Numerals-Coding-Challenge