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
}

def answer = 0

new File("euler_p89_roman.txt").eachLine {
    answer += it.size() - toRoman(fromRoman(it)).size()
}

This runs in 0.14 seconds so well within the time allowed.

Conclusion

Groovy’s file handling and terse syntax was nice to use, but wouldn’t have been much more in Java. For the scale of the problem, performance wasn’t an issue at all.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: