The Romans Are Coming Thu 13 Dec, 2012

This was a fun coding kata that I encountered whilst we were screening applicatants for a front-end developer role. Our resident JS developer set this task, and being curious, I decided to give it a shot myself.

PS - if you happen to be applying for a job and you're working on this problem, be smart and don't copy and paste this code. If you can't understand the code, or are unable to talk someone through the thought processes behind it, it'll be obvious and it'll reflect horribly on you.

The Exercise

Implement the following JavaScript function that converts a number into its Roman Numeral representation; function romanNumeralGenerator (int) { }

For example, see the following sample inputs and outputs

1 = 'I'
5 = 'V'
20 = 'XX'
24 = 'XXIV'
3999 = 'MMMCMXCIX'

You only need to support numbers between 1 and 3999.

My Solution

The route I took to implementing this was in two parts

1. a recursive method to obtain the Roman representation of the number supplied
2. a method to 'fix' the output to the proper format e.g. replacing 4 repeating numerals with the correct representation (9 --> VIIII --> IX)

There may be better ways to do this, but here's what I ended up with.

var converter = (function () {
  'use strict';

  var romanNumeralsArray = [
    {roman: 'I', number: 1},
    {roman: 'V', number: 5},
    {roman: 'X', number: 10},
    {roman: 'L', number: 50},
    {roman: 'C', number: 100},
    {roman: 'D', number: 500},
    {roman: 'M', number: 1000}
  ];

  var length = romanNumeralsArray.length,
      outputString = '',
      inputNumber = 0;

  // get index of item in roman numeral array
  function getIndexOfLetterInNumeralsArray(strValue) {
    var i, obj;
    for (i = 0; i < length; i += 1) {
      if (romanNumeralsArray[i].roman === strValue) {
        obj = romanNumeralsArray[i];
        return romanNumeralsArray.indexOf(obj);
      }
    }
    return -1;
  }

  function romanNumeralGenerator(intVal, stringVal) {
    var i,
        matchedNumberIndex,
        matchedNumber = 0;

    // break condition for the recursion
    if (intVal < 1 || intVal > 3999) {
      return stringVal;
    }

    // iterate through numerals array to find the highest number that goes into the input
    for (i = 0; i < length; i += 1) {
      if (romanNumeralsArray[i].number <= intVal && romanNumeralsArray[i].number > matchedNumber) {
        matchedNumber = romanNumeralsArray[i].number;
        matchedNumberIndex = i;
      }
    }

    // add corresponding letter to the answer and subtract the number from the input
    stringVal += romanNumeralsArray[matchedNumberIndex].roman;
    intVal = intVal - matchedNumber;

    // recurse
    stringVal = romanNumeralGenerator(intVal, stringVal);
    return stringVal;
  }

  function amendOutput(input) {
    var i,
        output = '',
        match = input.match(/(.)\1{3}/g),
        allMatches,
        matchedCharacter,

        //info from the input string
        repeatingCharFirstPosition,
        repeatingCharPreceedingChar,

        // indices of the above characters in the numerals array
        rindex, pindex;

    // is there a character repeating 4 times?
    if (match) {
      allMatches = input.match(/(.)\1{3}/g).toString().split(',');

      for (i = 0; i < allMatches.length; i += 1) {

        matchedCharacter = allMatches[i].split('')[0],
      	repeatingCharFirstPosition = input.indexOf(matchedCharacter),
      	repeatingCharPreceedingChar = input.split('')[repeatingCharFirstPosition - 1],
      	rindex = getIndexOfLetterInNumeralsArray(matchedCharacter),
      	pindex = getIndexOfLetterInNumeralsArray(repeatingCharPreceedingChar);

        // if the character preceeding the repeating one is the next numeral up
        if (pindex === (rindex + 1)) {
          output = output.substring(0, repeatingCharFirstPosition - 1);

          //if this is the first pass through fixing the string
          if (!output) {
            output = input.substring(0, repeatingCharFirstPosition - 1);
          }

          output += matchedCharacter + romanNumeralsArray[rindex + 2].roman;

        } else {
          output += matchedCharacter + romanNumeralsArray[rindex + 1].roman;
        }
      }
      input = output;
    }
    return input;
  }

  return {
    romanNumeralGenerator: function (inputInt) {
      var answer = '';
      answer = romanNumeralGenerator(inputInt, answer);
      answer = amendOutput(answer);
      return answer;
    }
  }
}());