Back Thu 13 Dec, 2012

The Romans Are Coming

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;
}
}
}());