Code Kata - Roman Calculator

‘Code Kata’ is a programming exercise for programmers to hone their skills. The name, Kata, came from the Japanese concept of Kata in the martial Arts.

There are 21 different katas that you can practice. I was asked by an interviewer to solve Roman Calculator Kata. Particularly, just the addition and the subtraction. This might sound easy if you are considering that you will convert the Roman numbers into integers, add-sub them and convert back. But the problem is if you are a Roman, you don’t even know what is an integer. So the calculator that you are going to implement, must do the addition-subtraction the way the Romans did.

The procedures that Romans followed are explained in detail here and here. My solution can be found here, written in C.

Although it wasn’t allowed to turn the roman number into integer, but I will have a function to do exactly that so that I can cross validate my result. This way I can convert any roman numbers to decimal or vice versa to test my actual Roman Calculator code.

Note: Converting roman number into integer is a ‘Project Euler Problem’ (Problem 89). The math behind the conversion is explained here.

Roman Converter

Roman-to-Decimal

My Roman Converter lib has two global functions, roman2dec() and dec2roman(). Roman to decimal converter was divided into two functions, roman2dec_char() and roman2dec_str().
roman2dec_char will take a single character and will return corresponding decimal value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static uint16_t roman2dec_char(char romanChar)
{
	switch(toupper(romanChar))
	{
		case 'I': return 1;
		case 'V': return 5;
		case 'X': return 10;		
		case 'L': return 50;		
		case 'C': return 100;		
		case 'D': return 500;		
		case 'M': return 1000;	
		default	: return 0;
	}
}

If this function returns zero, then you can tell an invalid character was passed to the function, because there is no zero in roman number.

roman2dec_str() uses this function. All you have to do is add all the characters’ corresponding decimal value. There is just one exception. The roman numbers are organized in a descending order from left to right. So, if you come across a smaller number before a larger number then you will have to subtract that smaller value from the larger value. So, I started to add the numbers from the right and kept track of the previous value for comparison.

Decimal-to-Roman

Converting a decimal number into a roman number is a bit complicated, because of the subtracting part. What you have to do is subtract the largest roman number from the decimal number until the decimal number gets less than that particular roman number, then switched to the next largest roman number that is less than the decimal number and so on until you reach zero.

I put all the possible roman numbers, including the subtract parts, in one array and their corresponding decimal value in another array.

1
2
static const int romanDecValue[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
static const char *romanNumeral[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

Roman Calculator

The Roman Calculator library has two global functions, add2romanNum and sub2romanNum. If you haven’t visited the algorithm links already, please do so. I will copy the example from that page:

Addition

Perform CCCLXIX + DCCCXLV.

1.Substitute for any subtractives: CCCLXVIIII + DCCCXXXXV
[‘uncompactRoman’ function]

2.Catenate to obtain:CCCLXVIIIIDCCCXXXXV
[Done by ‘uncompactRoman’ function]

3.Sort to obtain:DCCCCCCLXXXXXVVIIII
[‘bubble_sort_descending’ function]

4.Combine groups to obtain:
DCCCCCCLXXXXXXIIII
DCCCCCCLLXIIII
DCCCCCCCXIIII
DDCCXIIII
MCCXIIII
[‘combineRomanNum’ function]

5.Substitute any subtractives to obtain:MCCXIV
[‘compactRoman’ function]

Subtraction

Subtraction requires special attention. As roman numbers cannot represent zero or negative numbers, you will have to make sure you are not subtracting a larger number from a smaller number or the both numbers aren’t the same.

Perform CXXIX − XLIII

1.Substitute for any subtractives: CXXVIIII − XXXXIII
[‘uncompactRoman’ function]

Note: Here we checked if the 1st number is larger than 2nd number isNum1greaterThanNum2 function.

2.Cross out common symbols: CXXVIIII and XXXXIII

3.Need X’s, convert C to LXXXXX: LXXXXXVI (LXXXVI) and XX

[‘crossOutCommons’ function]

4.Rewrite:LXXXVI
[‘bubble_sort_descending’ function]

5.Check for grouping: LXXXVI
[Because of the way I handled crossOutCommons, this step isn’t necessary]

6.Substitute any subtractives to obtain:LXXXVI
[‘compactRoman’ function]

The code can be found here.