Roman Numerals: part I
A few days ago I attempted a Roman Numerals kata, which basically wanted me to implement a function to convert a “normal number” (I took this to mean an integer) to a Roman numeral. I chose to use Kotlin as I wanted to explore how the language worked for a problem that would probably not require many complex language features.
I captured the result after each red-green-refactor cycle in a branch of my GitHub repo tdd-template; feel free to browse the commits there but I’m going to describe them below, with some accompanying comments.
Setup
I used Kotlin 1.0.3 with JUnit and JUnitParams
The first test: 1 ⇒ I
It was nice and easy to choose what this should be!
import org.junit.Test
import kotlin.test.assertEquals
class DecimalToRomanConverterTest {
@Test fun `1 is written as I`() {
assertEquals("I", 1.toRoman())
}
}“Hang on”, I hear you cry. “Since when did integers have a toRoman method?! And how can you even call a method on a primitive int?”
Well, as you probably guessed, this is a bit of Kotlin magic.
Firstly, Kotlin provides some basic types, including Int, which are treated as objects having methods (like Integer in Java) but which are actually translated to the equivalent of Java’s primitive int by the compiler.
Secondly, Kotlin has extension functions which, as far as I can tell, are syntactic sugar for a static method whose first argument is the target type.
Finally, note the use of backticks for the test method name, which allows a nice natural method name (and description in test runner outputs). This is arguably an abuse of the backtick, which in Kotlin is there as a way of referencing a method (say a Java method) which is named with a Kotlin reserved word.
So, I implemented this extension method. (Alt-Enter and… why, thanks IntelliJ, yes I would like to “Create extension function ‘toRoman’”, and I think I’ll target Int since you so kindly suggested it.)
fun Int.toRoman(): String {
return "I"
}The second test: 2 ⇒ II
Next simplest test: I could have chosen to convert 10, or 5, as they correspond to single Roman digits. But I figured that wouldn’t teach me anything about the more general solution, so instead I moved on to writing 2 in Roman numerals.
@Test fun `2 is written as II`() {
assertEquals("II", 2.toRoman())
}kotlin.String implements kotlin.CharSequence (just like their Java counterparts), and there are a whole load of neat functions defined on CharSequence. One of these is repeat(n: Int), which “Returns a string containing this char sequence repeated [n] times”. Perfect!
In an extension function, you can refer to the target instance (in this case, the integer 2) with this, so the implementation was again straightforward:
fun Int.toRoman(): String {
return "I".repeat(this)
}Refactoring
Just because I could, I converted the two test methods to expression bodies:
class DecimalToRomanConverterTest {
@Test fun `1 is written as I`() = assertEquals("I", 1.toRoman())
@Test fun `2 is written as II`() = assertEquals("II", 2.toRoman())
}It seemed clear that all my tests would be this shape, so I decided to apply some JUnitParams magic. JUnitParams has many ways to define the parameter values directly in the annotation on the test method, but I thought my list might get quite long, so I created a companion method that returned the dataset:
import junitparams.JUnitParamsRunner
import junitparams.Parameters
import junitparams.naming.TestCaseName
import org.junit.Test
import org.junit.runner.RunWith
import kotlin.test.assertEquals
@RunWith(JUnitParamsRunner::class)
class DecimalToRomanConverterTest {
@Test
@TestCaseName("{0} is written as {1}")
@Parameters
fun testIntToRomanConversion(number: Int,
romanRepresentation: String) {
assertEquals(romanRepresentation, number.toRoman())
}
private fun parametersForTestIntToRomanConversion() =
arrayOf(
arrayOf(1, "I"),
arrayOf(2, "II")
)
}The third test: 10 ⇒ X
I knew a test for 3 ⇒ III would pass, but 4 ⇒ IV would fail. I could’t think how I’d deal with the “subtracting” digits (I before V = subtract I from V) yet, and for some reason I did’t want to get into the 5 scenario yet (it doesn’t follow the same addition rules as 1). So, I decided to handle 10 next.
private fun parametersForTestIntToRomanConversion() =
arrayOf(
arrayOf(1, "I"),
arrayOf(2, "II"),
arrayOf(10, "X")
)I reckon I succeeded in keeping the implementation as simple as possible:
fun Int.toRoman(): String {
if (this < 10) {
return "I".repeat(this)
} else {
return "X"
}
}Onward!
The fourth test: 20 ⇒ XX
I now knew how to add ones, and reasoned that I would be able to add tens in a similar way. I added this case to my test data function:
arrayOf(20, "XX")and did a little bit of arithmetic to work out how many tens were in the number being converted:
fun Int.toRoman(): String {
if (this < 10) {
return "I".repeat(this)
} else {
return "X".repeat(this / 10)
}
}I can’t remember exactly why, but thinking ahead a bit about how the numbers would later be combined, I decided I was likely to want to handle the values from larger to smaller, so I reversed the order of the conditional:
fun Int.toRoman(): String {
if (this >= 10) {
return "X".repeat(this / 10)
} else {
return "I".repeat(this)
}
}Tests 5–8: converting 100, 200, 1000, 2000
By this point I had a rhythm going for the first two powers of ten and their simple repeats. I zipped through the same steps with 100, 200, 1000 and 2000:
fun Int.toRoman(): String {
if (this >= 1000) {
return "M".repeat(this / 1000)
} else if (this >= 100) {
return "C".repeat(this / 100)
} else if (this >= 10) {
return "X".repeat(this / 10)
} else {
return "I".repeat(this)
}
}Refactoring
A clear pattern had emerged, a kind of duplication. It seemed wise to deal with it. First I wanted a mapping from each power of ten to its Roman digit:
fun symbolFor(unit: Int): String {
return when(unit) {
1000 -> "M"
100 -> "C"
10 -> "X"
1 -> "I"
else -> throw RomanNumeralException(
"No mapping to symbol for ${unit}")
}
}
class RomanNumeralException(message: String) : RuntimeException(message)(This demonstrates a when expression, Kotlin’s version of a switch statement.)
Then I converted my previous series of if conditions into a loop over the descending powers of ten from 1000 down to 1. As soon as I found a match I looked up the symbol and repeated it the correct number of times.
fun Int.toRoman(): String {
val powersOfTen = listOf(1000, 100, 10, 1)
powersOfTen.forEach { unit ->
if (this >= unit) {
return symbolFor(unit).repeat(this / unit)
}
}
throw RomanNumeralException(
"Can't yet convert ${this} to Roman numerals")
}Tests were still green. I wasn’t entirely happy – it seemed less readable than before – but, impatient, I pressed on.
Place values
Still ignoring the fives and subtraction-based numerals, I decided my next task was to turn 11 into 10+1 ⇒ XI. I wrote the test and started to consider the solution.
Until now, my toRoman function returned a value as soon as it found a power of ten that fit the number being converted. I could have used a local, mutable variable to build up the numeral, something like this:
fun Int.toRoman(): String {
val powersOfTen = listOf(1000, 100, 10, 1)
var roman = ""
var number = this
powersOfTen.forEach { unit ->
val howManyTimes = number / unit
number = number % unit
roman = roman + symbolFor(unit).repeat(howManyTimes)
}
return roman
}I wanted to find a more functional style, though. I thought about the way these longer numerals are composed and realised that if I could convert a number into how many each of thousands, hundreds, tens and ones were in it, I could map across those values and join the results. For example:
3012 = 3000 + 10 + 2
= 3×1000 + 1×10 + 2×1
⇒ 3×M + 1×X + 2×I
⇒ MMMXIIThis reminded me of learning about numbers at primary school, we would talk about “hundreds, tens and units”. I googled around a bit and found that this is known as positional notation or place-value notation.
So I needed to decompose an integer such as 2013 into its component “place values”. Then I could map across the list of place values and convert each one into its Roman numeral representation, then just concatenate them.
I deleted my test for 11 ⇒ XI while I worked on this new toDecimalPlaceValues function.
First, then, I would need a test for this function.
@Test
fun testPlaceValues() {
val placeValues: List<Int> = toDecimalPlaceValues(14)
assertEquals("10+4", placeValues.joinToString("+"))
}I chose to test against this 10+4 representation because it was highly readable (actually, would be more so once I parameterised the test).
To implement toDecimalPlaceValues I actually used some very similar logic to my possible solution shown earlier in this section) but applying recursion rather than mutating local variables:
private val powersOfTen = listOf(1000, 100, 10, 1)
fun toDecimalPlaceValues(number: Int): List<Int> {
val largestPowerNeeded = powersOfTen.find { number > it } ?: 1
if (largestPowerNeeded == 1) {
return listOf(number)
} else {
val multiplier = number / largestPowerNeeded
val remainder = number % largestPowerNeeded
val placeValueForThisPower = multiplier * largestPowerNeeded
return listOf(placeValueForThisPower) +
toDecimalPlaceValues(remainder)
}
}By the time I was done I had the following tests:
@Test
@Parameters
fun testPlaceValues(number: Int, placeValueRepresentation: String) {
assertEquals(formatPlaceValues(toDecimalPlaceValues(number)), placeValueRepresentation)
}
private fun parametersForTestPlaceValues() =
arrayOf(
arrayOf(9, "9"),
arrayOf(14, "10+4"),
arrayOf(4025, "4000+20+5")
)
private fun formatPlaceValues(placeValues: List<Int>) =
placeValues.joinToString(separator = "+")Based on my reading about place values and the terminology associated with numeric notation systems, I decided that my symbolFor(Int) function name was not specific enough. It gives a Roman digit for an integer. So I renamed it toRomanDigit and made it an extension function on Int instead, which read more nicely (left-to-right):
return unit.toRomanDigit().repeat(this / unit)Place Values: refinement
I reinstated the test for toRoman with 11 ⇒ XI but quickly realised that having calculated the place values as integers (e.g. 3000 as the first place value in 3012) I would have to divide them again to determine how many times to repeat the digit. Perhaps I should preserve the two factors (3 and 1000) separately.
Again I deleted the test for 11 ⇒ XI and rewrote my toDecimalPlaceValues function to construct a list of PlaceValue classes:
class PlaceValue(val multiplier: Int, val unit: Int) {
override fun toString() = (multiplier * unit).toString()
}
fun toDecimalPlaceValues(number: Int): List<PlaceValue> {
val largestPowerNeeded = powersOfTen.find { number > it } ?: 1
if (largestPowerNeeded == 1) {
return listOf(PlaceValue(number, 1))
} else {
val multiplier = number / largestPowerNeeded
val remainder = number % largestPowerNeeded
return listOf(PlaceValue(multiplier, largestPowerNeeded))
+ toDecimalPlaceValues(remainder)
}
}(In fact I made it a data class but that wasn’t necessary.)
Overconfidence
I thought I was ready to plug toDecimalPlaceValues into toRoman and I’d finally solve 11 ⇒ XI.
fun Int.toRoman(): String {
val placeValues = toDecimalPlaceValues(this)
return placeValues.map {
it.unit.toRomanDigit().repeat(it.multiplier)
}.joinToString(separator = "")
}I ran my tests… oh dear! Three tests failed:
java.lang.AssertionError: Incorrect conversion of 10 to Roman numerals. Expected <X>, actual <IIIIIIIIII>.
java.lang.AssertionError: Incorrect conversion of 100 to Roman numerals. Expected <C>, actual <XXXXXXXXXX>.
java.lang.AssertionError: Incorrect conversion of 1000 to Roman numerals. Expected <M>, actual <CCCCCCCCCC>.It turned out that my toDecimalPlaceValues function really didn’t like being given a simple value which should translate to 1 of a power of ten. Instead of 10 being converted to PlaceValue(multiplier = 1, unit = 10) it was producing PlaceValue(multiplier = 10, unit = 1).
The way I had constructed my expected result in my tests meant that this bug hadn’t shown up.
I reverted my toRoman changes again, and changed the PlaceValue’s string representation to be more revealing:
TEST:
private fun parametersForTestPlaceValues() =
arrayOf(
arrayOf(9, "9*1"),
arrayOf(14, "1*10 + 4*1"),
arrayOf(4025, "4*1000 + 2*10 + 5*1"),
arrayOf(10, "1*10")
)
private fun formatPlaceValues(placeValues: List<PlaceValue>) =
placeValues.joinToString(separator = " + ")
IMPLEMENTATION:
data class PlaceValue(val multiplier: Int, val unit: Int) {
override fun toString() = "$multiplier*$unit"
}Now I could see how toDecimalPlaces(10) fails:
java.lang.AssertionError: Expected <1*10>, actual <10*1>.Aha! When trying to work out the largest power needed to represent a number, I was finding the largest power of 10 greater than the number. I should have used greater than or equal to:
fun toDecimalPlaceValues(number: Int): List<PlaceValue> {
val largestPowerNeeded = powersOfTen.find { number >= it } ?: 1
...
}Almost. Test still failing, but for a different reason:
java.lang.AssertionError: Expected <1*10>, actual <1*10 + 0*1>.The recursive call for the base case (when largestPowerNeeded == 1) was returning a PlaceValue(0, 1).
The simplest fix for this was just to insert a check for zero at the top of the function:
fun toDecimalPlaceValues(number: Int): List<PlaceValue> {
if (number == 0) {
return emptyList()
}
...
}Tests all passing again! Hooray!
11 ⇒ XI, at last!
I finally got to add my ninth test case for the toRoman function.
My implementation was as I’d tried before, and this time it worked:
fun Int.toRoman(): String {
val placeValues = toDecimalPlaceValues(this)
return placeValues.map {
it.unit.toRomanDigit().repeat(it.multiplier)
}.joinToString(separator = "")
}Testing
In TDD, you write a test that you expect to fail. In testing, you write or perform tests that you expect to pass.
I thought I’d nailed this place values stuff, at least for numbers containing (decimal) digits 0–3. I wanted to add a more complex number, though, just to reassure myself. I chose 3012 ⇒ MMMXII and was pleased to see that it passed.
To be continued…
I don’t think I’m consistently good at choosing the simplest thing required to make a test pass. However, I think I did introduce an appropriate domain model with the PlaceValue at a good point, which will help me complete the solution.
The key realisation was that each digit in the decimal representation of an integer could be independently mapped to a (possibly empty) string of Roman digits, and those strings simply concatenated in the same order to give the final Roman numeral representation. The mapping of a decimal digit works in exactly the same way but the Roman digits used vary depending upon the magnitude.
Hmm… writing that has made me think that magnitude may be a better name than unit in PlaceValue, like this:
toDecimalPlaceValues(230) ==
listOf(PlaceValue(multiplier = 2, magnitude = 100),
PlaceValue(multiplier = 3, magnitude = 10))Thanks, rubber ducks! Until next time… your comments are welcome!
Continue to Roman Numerals: part II
Image credit: photograph of Cleveland Bridge plaque, Bath by Jaggery is licensed for reuse under CC BY-SA 2.0