Saturday, February 15, 2014

Roman Numeral Converter and the Strategy Pattern

The Roman numeral converter is a converter that will converter a decimal value (Eg. 4) to its Roman numeral equivalent value (Eg. IV).

This implementation of the converter (of which there are many other alternative implementations) uses a divide and conquer approach. The conversion is broken down into smaller "bite size" parts (ones, tens, hundreds, thousands) which lends itself nicely to using the strategy pattern.

What is the Strategy pattern?
The strategy pattern is a way to encapsulate a family of similar algorithms. Each algorithm is a strategy and the pattern allows one or many strategies to be selected at run-time.

The strategy interface
Each strategy is required to implement an interface so it can be consumed by the client consistently. The IConverter interface is used to achieve this and specifies a single method called Convert.

1
2
3
4
public interface IConverter
{
  string Convert(int number);
}

A strategy implementation
The OnesConverter implements the IConverter interface to convert the ones (1 - 9) to their Roman numeral equivalents. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class OnesConverterStrategy : IConverter
{
  public string Convert(int number)
  {
    int onesToConvert = CalculateNumberOfOnesToConvert(number);

    string conversion = string.Empty;

    int i = 1;

    while (i <= onesToConvert)
    {
      if (i == 4)
        conversion = "IV";
      else if (i == 5)
        conversion = "V";
      else if (i == 9)
        conversion = "IX";
      else
        conversion += "I";
      i++;
    }

    return conversion;
  }

  private int CalculateNumberOfOnesToConvert(int number)
  {
    int numberOfOnes = number % 10;

    return numberOfOnes;
  }
}

Each converter follows a similar pattern where the CalculateNumberOfXXXXToConvert method uses a modulus calculation to determine the number of units (number of tens or number of hundreds etc.) to convert to Roman numerals. This is used within a while loop to generate the conversion.

Roman numeral converter
The RomanNumeralConverter class instantiates a List<IConverter> in the order in which they will be called (thousands > ones). It then enumerates through this list building up the Roman numeral conversion as it progresses and returns the completed conversion to the caller.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class RomanNumeralConverter
{
  private List<IConverter> _converters;

  public RomanNumeralConverter()
  {
    _converters = new List<IConverter>
    {
      new ThousandsConverter(),
      new HundredsConverter(),
      new TensConverter(),
      new OnesConverter()
    };
  }

  public string ConvertToRomanNumerals(int number)
  {
    if (number <= 0 || number > 3000)
    return "Invalid value";

    string result = string.Empty;

    _converters.ForEach(x => result += x.Convert(number));

    return result;
  }
}

The benefits of this approach is that each of the strategy implementation can be tested in isolation and allows the RomanNumeralConverter to be extended by introducing additional converters without effecting the existing converters (as long as the converter initialization order is preserved).

The downside to this implementation is that there is a bit of duplication in each of the converters as essentially the algorithm is the same but only the Roman numerals change. A single converter could be potentially used here which could use a multi-dimensional array to switch which Roman numerals to use based on the place value (ones, tens etc.) of the decimal number currently being converted.

The complete project can be found here with accompanying unit tests.

In a subsequent post, I will extend the RomanNumeralConverter to use a factory to generate an enumerable of IConverter strategies based on the decimal value required to be converted. This will allow us to further utilize the strategy patterns ability to load specific strategies at run-time and introduce the factory pattern.

No comments:

Post a Comment