1. Overview
In this article, we’ll work through the problem of converting a number to a Roman numeral. This is a commonly used coding task in Scala, to improve or test our abilities in the functional language.
We’ll start by discussing best practices when approaching a problem such as this one. Then explore the different options when trying to solve this problem.
2. The Problem
Roman numerals use specific letters to represent numbers e.g. 1 = “I”, 5 = “V”, 10 = “X” and so on. These letters are ordered from largest to smallest with the sum of all the letters in the sequence giving us the total represented by the sequence.
For example “XVI” would be 10+5+1 giving us a total of 16. For this task, we’ll be writing an algorithm that will return the correct sequence of Roman numeral letters. Representing the value of an Int passed into a function.
2.1. Approaching The Problem
Before attempting to solve a logic problem like this, it’s advisable to use test-driven development to ensure our final solution works as expected. It can also be beneficial to write the tests first to help consider some of the edge cases in the problem to be solved.
For converting numbers to Roman numerals, we can define a list of numbers and their expected Roman numerals equivalent. While we could start from zero and test every single number up to 1000, it’s less time-consuming yet equally as beneficial to ensure our tests include all edge cases.
For this problem, the following set of numbers to Roman numerals should suffice:
val testValuesWithResults: List[(Int, String)] = List(
(0, ""),
(1, "I"),
(4, "IV"),
(5, "V"),
(6, "VI"),
(9, "IX"),
(10, "X"),
(14, "XIV"),
(15, "XV"),
(17, "XVII"),
(19, "XIX"),
(20, "XX"),
(40, "XL"),
(44, "XLIV"),
(49, "XLIX"),
(50, "L"),
(90, "XC"),
(100, "C"),
(400, "CD"),
(500, "D"),
(900, "CM"),
(1000, "M"),
(1949, "MCMXLIX")
)
This List should be more than enough for us to be confident that our final solution works correctly. It’s also got us thinking about the problem at hand and some edge cases we should consider when writing our code.
Firstly, we need to handle zero, which should return an empty string. Also, 4 is represented by “IV” rather than “IIII”. We should consider all these things when writing code to solve the problem.
3. Matching Numbers to Letters
The first part of this problem is to convert a numeric value to the first and largest letter in the sequence. We have to determine whether the numeric value of a Roman numeral letter fits into the number we’re trying to convert. We could use a long list of if statements to do this; however, that’s quite cumbersome and not very DRY.
If we created a List[(Int, String)] to hold all Roman numerals letters and the value they represent. This allows us to iterate through the List until we find the largest value that fits into the number we’re trying to convert:
val numbersToRomansList = List(
(1000, "M"),
(900, "CM"),
(500, "D"),
(400, "CD"),
(100, "C"),
(90, "XC"),
(50, "L"),
(40, "XL"),
(10, "X"),
(9, "IX"),
(5, "V"),
(4, "IV"),
(1, "I")
)
Defining this list in descending order means we can iterate through and encounter the largest Roman numeral that can fit into our number first. The simplest way to do this is to use the .find() function available on List:
def numToRomans(num: Int) = {
numbersToRomansList.find((n, _) => {
num - n >= 0
})
...
This code snippet iterates through numbersToRomansList and returns the first element where the Int part of the Tuple can be subtracted from num without the result being negative. Therefore giving us the first letter in our Roman numeral sequence.
4. Using Recursion
The code written so far gives us the first letter in the Roman numeral sequence. To get the rest we’ll have to apply the same logic a certain number of times. The natural solution to this is to use recursion.
Let’s start off thinking about our base case; when we want our function to stop calling itself. When num is zero, we’ve fully converted the value originally held in num into the Roman numeral. At which point our function must return:
def numToRomans(num: Int): String = {
numbersToRomansList.find((n, _) => {
num - n >= 0
}) match
case Some((n, r)) => ???
case None => ""
}
Here, we’re using the result of find() to know when we’ve reached our base case. This works because testValuesWithResults contains an Int of one. So, if a number can’t be found that fits into num, then num must be zero (or potentially negative). Meaning it’s time for the numToRomans function to return.
Now we need to implement the code to call numToRomans recursively. At this point in our code, we’ve found the largest number that fits into num and we have the equivalent Roman numeric letter.
From here we just need to return the letter, plus the result of a call the numToRomans passing in num minus the value of n:
def numToRomans(num: Int): String = {
numbersToRomansList.find((n, _) => {
num - n >= 0
}) match
case Some((n, r)) => ?r + usingRecursion(num - n)?
case None => ""
}
This is a fully working solution. If we run the unit tests previously discussed. We should find that all the test numbers within testValuesWithResults match their expected Roman numeral Strings.
5. Using Tail Recursion
While the solution in the previous section is fully functional, it isn’t tail-recursive. Which could result in a stack overflow error if a large enough number is passed in.
Luckily, we can easily fix this with an adjustment to our recursive function:
def numToRomans(num: Int): String = {
@tailrec
def recursiveFn(remaining: Int, acc: String): String = {
numbersToRomansList.find((n, _) => {
remaining - n >= 0
}) match
case Some((n, r)) => recursiveFn(remaining - n, acc+r)
case None => acc
}
recursiveFn(num, "")
}
In the code above we have created an inner function to be used as the recursive function, ensuring the signature of numToRomans remains the same. In addition to taking num, recursiveFn also takes an accumulator. Which holds the value of the Roman numeral String so far. This means that the recursive calls don’t have to return up the call stack once the base case is reached. Therefore the frames can be dropped. Once the full Roman numeral String has been found, acc is directly returned from the frame we’re in.
Adding the @tailrec annotation to recursiveFn ensures that any future changes made to the function remain tail-recursive. Otherwise, the compile would produce an error.
6. Using foldLeft()
Another way to tackle this problem could be to use the foldLeft() function available on Lists in Scala. While the overall principle remains the same, we have to solve one complication; as we fold through numbersToRomansList, we will only iterate over each element once.
Whereas in our recursion examples, we’d go through the list as many times as required until the function had completed. This means we need to evaluate how many times a value in numbersToRomansList can fit into num in a single pass. We can do this using division:
def numToRomans(num: Int): String = {
numbersToRomans
.foldLeft((num, ""))((remainingAndAcc, numAndRoman) => {
val (remaining, acc) = remainingAndAcc
if (remaining == 0) remainingAndAcc
else {
val (n, r) = numAndRoman
(remaining % n, acc + r * (remaining / n))
}
})._2
}
In this snippet, we’re checking if remaining is zero and if so the full Roman numeral sequence has been found and the current value of the accumulator is carried forward in the evaluation of foldLeft(). Otherwise, we continue into the function where the new value of remaining will be the remainder after dividing by n.
Then we add the Roman numeric letter to the accumulator, multiplied by how many times n fits into remaining. This gives us the same results in a fixed number of iterations, regardless of the value of num. As a result, this function is a lot more efficient than the recursive solutions previously discussed.
7. Conclusion
In this article, we have defined the problem of converting a number to a Roman numeral and discussed the benefits of taking a test-driven approach when tackling this coding problem. We then explored how to solve this problem with code, starting with recursion. Then moved on to refine the function to make it stack-safe. Finally, we implemented a more efficient solution using foldLeft() on List.
As always, the sample code used in this article is available over on GitHub.