Project Euler Problem #89

May 14, 2010

Read the details of the problem here

Summary

Develop a method to express Roman numerals in minimal form.

Solution

A nice little programming problem rather than anything mathematical for this one. The FAQ gave some interesting background on Roman numerals too!

Looking at the input data, it did look like it might be possible to solve this just with straight textual substitution but, in the spirit of the site, I wrote a routine to parse the input Roman numeral sequences and then another to write them out in minimal form – the latter actually being more straightforward than the former as it just a case of considering the set of Roman character (including the subtractive combinations) as a sort of a working base and just dividing through and subtracting the multiples.

```def fromRoman(s) {

def romans = [ I:1, V:5, X:10, L:50, C:100, D:500, M:1000 ]
def ( lastChar, grpValue, sum ) = [ null, 0, 0 ]

s.toList().eachWithIndex { v, i ->

if (i == 0) {
lastChar = v
grpValue = romans[v]
}
else if (v == lastChar) {
grpValue += romans[v]
}
else {
if (romans[lastChar] < romans[v]) grpValue *= -1
sum += grpValue
grpValue = romans[v]
lastChar = v
}

if (i == s.size()-1) {
if (romans[lastChar] < romans[v]) grpValue *= -1
sum += grpValue
}
}

return sum
}

def toRoman(n) {

def s = ""

[ 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" ].each { k, v ->
def m = n.intdiv(k)
if (m > 0) {
s += v * m
n -= k * m
}
}
return s
}