Scala Roman Numerals – different approaches
I have a couple of things I wanted to review, and decided to do it using a simple algorithm which most people will understand.
Roman numerals are as follows: I, II, III, IV, V, VI, VII, VIII, IX, X XI, XII, XIII, XIV, XV, XI, XII, XIII, XIX, XX, XXI….
Wikipedia can tell you how they work. But how could you do this in Scala, and what Scala features could be illustrated as we try out various ways?
The following examples are not the best way to do it, but they all work, and to prove it here is the unit test
package com.jgibbons.romannumerals
import org.scalatest.FlatSpec
import scala.collection.immutable.HashMap
class RomanNumeralsSpec extends FlatSpec {
behavior of "RomanNumerals"
it should "Convert Properly" in {
val mapped = HashMap[Int, String](
1->"I", 2->"II", 3->"III", 4->"IV", 5->"V", 6->"VI", 7->"VII", 8->"VIII", 9->"IX", 10->"X",
11->"XI", 12->"XII", 13->"XIII", 14->"XIV", 15->"XV", 16->"XVI", 17->"XVII", 18->"XVIII", 19->"XIX", 20->"XX",
41->"XLI", 42->"XLII", 43->"XLIII", 44->"XLIV", 45->"XLV", 46->"XLVI", 47->"XLVII", 48->"XLVIII", 49->"XLIX",
50->"L", 51->"LI", 60->"LX", 64->"LXIV", 68->"LXVIII", 69->"LXIX",
90->"XC", 91->"XCI", 94->"XCIV", 96->"XCVI", 99->"XCIX",
100->"C", 140->"CXL", 144->"CXLIV", 149->"CXLIX",
189->"CLXXXIX", 190->"CXC", 194->"CXCIV", 199->"CXCIX",
989->"CMLXXXIX", 990->"CMXC", 994->"CMXCIV", 999->"CMXCIX",
1194->"MCXCIV", 1199->"MCXCIX",
1989->"MCMLXXXIX", 1990->"MCMXC",
5989->"MMMMMCMLXXXIX", 5990->"MMMMMCMXC", 5994->"MMMMMCMXCIV", 5999->"MMMMMCMXCIX"
)
mapped.foreach { case (k:Int, v:String) =>
assert( RomanNumerals.convertLongImperative(k)==v, s"convertImperative failed for $k")
assert( RomanNumerals.convertFoldLeft(k)==v, s"convertFoldLeft failed for $k")
assert( RomanNumerals.convertStrs(k)==v, s"convertStrs failed for $k")
assert( RomanNumerals.convertMixed(k)==v, s"convertMixed failed for $k")
assert( RomanNumerals.convertTailRecursive(k)==v, s"convertTailRecursive failed for $k")
assert( RomanNumerals.convertFoldAgain(k)==v, s"convertFoldAgain failed for $k")
assert( RomanNumerals.convert(k)==v, s"convert failed for $k")
}
}
}Java Imperative style
The code below is obviously very long winded, but it shows how it could be done, without much thought, in a (bad) Java style implementation, but in Scala. It should be faily obvious how it works
def convertLongImperative(value: Int): String = {
var ret = ""
var remainder = value
val numM: Int = remainder / 1000
remainder = remainder - (numM * 1000)
for (cnt <- 0 until numM) ret += "M"
if (remainder >= 900) {
ret += "CM"
remainder = remainder - 900
} else {
if (remainder >= 500) {
ret += "D"
remainder -= 500
val numC = remainder / 100
for (cnt <- 0 until numC) ret += "C"
remainder -= numC * 100
} else {
if (remainder >= 400) {
ret += "CD"
remainder -= 400
} else {
val numC = remainder / 100
for (cnt <- 0 until numC) ret += "C"
remainder -= numC * 100
}
}
}
if (remainder >= 90) {
ret += "XC"
remainder = remainder - 90
} else {
if (remainder >= 50) {
ret += "L"
remainder -= 50
val numX = remainder / 10
for (cnt <- 0 until numX) ret += "X"
remainder -= numX * 10
} else {
if (remainder >= 40) {
ret += "XL"
remainder -= 40
} else {
val numX = remainder / 10
for (cnt <- 0 until numX) ret += "X"
remainder -= numX * 10
}
}
}
if (remainder == 9) {
ret += "IX"
} else {
if (remainder >= 5) {
ret += "V"
remainder -= 5
for (cnt <- 0 until remainder) ret += "I"
} else {
if (remainder == 4) {
ret += "IV"
} else {
for (cnt <- 0 until remainder) ret += "I"
}
}
}
ret
}Don’t do it that way, but it is a way…
Scala FoldLeft
I again hacked out a fold left solution, not because it is a good way to do it - the good ways come later, but because I was interested. Sadly, as an experiment it failed - it does work, but its mutable and ugly and the real version comes later. This version is included as part of the journey towards the final implementations which come later.
It does illustrate Scala type, Tuples and their access, and also uses a Tuple2 as an accumulator for the foldLeft.
/**
* This was a very quick attemt, but it is not refined and uses var's etc.
* A fold that looks like this are not the right approach
*/
type RomanInfo = Tuple4[Int, String, Int, String]
val romanNumeralRanges = List[RomanInfo]((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", 1, "I"))
def convertFoldLeft(value: Int): String = {
val result = romanNumeralRanges.foldLeft(("", value))((strRemainder: Tuple2[String, Int], info: RomanInfo) => {
var returnStr = strRemainder._1
var remainder = strRemainder._2
if (remainder < 1) strRemainder
else {
val num = remainder / info._1
for (i <- 0 until num) returnStr = returnStr + info._2
remainder = remainder - (num * info._1)
if (remainder >= info._3) {
remainder = remainder - info._3
returnStr = returnStr + info._4
}
(returnStr, remainder)
}
})
result._1
}Things of interest here, are initialisation of a Tuple by simply writing (“”, value). Using a type for Tuple4 and so on.
The boring way again
Going back to the traditional way to approach this, and keep it readable, perhaps we could have a similar approach to the imperative style, but with no mutable state.
Strings in Scala have some features, such as “M”*3 = “MMM”. Also, you can add expressions together to create the output string. So, playing with these features, and removing var’s we could still have a longhand version as below:
def convertStrs(value: Int): String = {
val valueUnderM = value % 1000
val valueUnderC = value % 100
val valueUnderX = value % 10
{if (value >= 1000) "M" * (value / 1000) else ""} +
{if (valueUnderM >= 900) "CM" else ""} +
{if (valueUnderM >= 500 && valueUnderM < 900) "D" else ""} +
{if (valueUnderM > 500 && valueUnderM < 900) "CCC".substring(0, (valueUnderM - 500) / 100) else ""} +
{if (valueUnderM >= 400 && valueUnderM < 500) "CD" else ""} +
{if (valueUnderM >= 100 && valueUnderM < 400) "CCC".substring(0, valueUnderM / 100) else ""} +
{if (valueUnderC >= 90) "XC" else ""} +
{if (valueUnderC >= 50 && valueUnderC < 90) "L" else ""} +
{if (valueUnderC > 50 && valueUnderC < 90) "XXX".substring(0, (valueUnderC - 50) / 10) else ""} +
{if (valueUnderC >= 40 && valueUnderC < 50) "XL" else ""} +
{if (valueUnderC >= 10 && valueUnderC < 40) "XXX".substring(0, valueUnderC / 10) else ""} +
{if (valueUnderX == 9) "IX" else ""} +
{if (valueUnderX >= 5 && valueUnderX < 9) "V" else ""} +
{if (valueUnderX > 5 && valueUnderX < 9) "III".substring(0, valueUnderX - 5) else ""} +
{if (valueUnderX == 4) "IV" else ""} +
{if (valueUnderX >= 1 && valueUnderX < 4) "III".substring(0, valueUnderX) else ""}
}Less code, it’s Scala
Scala should not need nearly as many lines as above, niether should Java come to that, so lets try and be at least a little cleverer
def convertMixed(value: Int): String = {
val numeralsFor100s = List("C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM")
val numeralsFor10s = List("X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC")
val numeralsFor1s = List("I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX")
"M" * (value / 1000) + {
if (value % 1000 > 99) numeralsFor100s(value % 1000 / 100 - 1) else ""
} + {
if (value % 100 > 9) numeralsFor10s(value % 100 / 10 - 1) else ""
} + {
if (value % 10 > 0) numeralsFor1s(value % 10 - 1) else ""
}
}I again use “M”*3=”MMM” at the start, and now I also start to use a List of values, and index into the List based on 100’s, 10’s and 1’s.
Tail Recursion
I admit I did not think about this until I finally googled how other people implement the convert in Scala, and I came upon the following rather lovely implementation. I take no credit for it and hope the author is happy for me to show it below.
/**
* All credit to Andy Bowes for this one: https://gist.github.com/AndyBowes/3048075
*/
def convertTailRecursive(number: Int): String = {
toRomanNumerals(number, List(("M", 1000), ("CM", 900), ("D", 500), ("CD", 400), ("C", 100), ("XC", 90),
("L", 50), ("XL", 40), ("X", 10), ("IX", 9), ("V", 5), ("IV", 4), ("I", 1)))
}
private def toRomanNumerals(number: Int, digits: List[(String, Int)]): String = digits match {
case Nil => ""
case h :: t => h._1 * (number / h._2) + toRomanNumerals(number % h._2, t)
}Fold Left again
It would not be right to leave the bad foldLeft done previously as the only example, so here it is again.
def convertFoldAgain( value:Int) :String= {
val romanNumerals = 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")
romanNumerals.foldLeft(value, "") {( strVal:Tuple2[Int, String], mapped:Tuple2[Int,String])=>
if (value==0) strVal
else (strVal._1%mapped._1, strVal._2+(mapped._2* (strVal._1 / mapped._1)))
}._2
}A tuple2 as the accumulator again, and the trick which means no special handling for 9, 5 or 4.
Expressive or incomprehensible?
Some people like to make Scala short at the expense of the poor devs who come after them. So, here is an obfuscated version
def convertFoldTerse( value:Int) = {
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").foldLeft(value, "") {( strVal, mapped)=>
(strVal._1%mapped._1, strVal._2+(mapped._2* (strVal._1 / mapped._1)))
}._2
}Here we see a Tuple2 being created with a syntax of 1000->”M”, as an alternative to (1000,”M”).
A final Tuple10
During my experimentation I came up with a Tuple10 solution which I think is easier to understand. Reading code for something like this should not require much thought. Note I am not scoring any of these for speed, memory or anything else, I’m just showing some different ways of doing it in Scala, and it is the number of different ways which I find interesting.
def convert(value: Int): String = {
"M" * (value / 1000) +
("", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM").productElement(value % 1000 / 100) +
("", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC").productElement(value % 100 / 10) +
("", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX").productElement(value % 10)
}I just can’t stop
The Tuple10 could become the class below, it seems there is no end to the ways we can do this. Why make the changes, well, Arrays are mutable, so we use Lists in preference, and to access the nth element of a List is shorter to type than to access the nth element of a Tuple10.
object RomanNumerals {
private val N = List(
List("", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"),
List("", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"),
List("", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"))
def convert(v: Int): String = {
"M" * (v / 1000) + N(0)(v % 1000 / 100) + N(1)(v % 100 / 10) + N(2)(v % 10)
}
}Summary
Hopefully, if you are getting into Scala, you can see many different approaches above, some are flawed, some are lengthy and maybe a couple are desirable. The aim of this post was to do it as many ways as I could think of. I can think of more, but will stop.