Skip to content

Roman numerals

2012 April 10
by Richard Harrington

When anyone mentions a coding exercise they had to do for an interview or a class, I have a habit of getting it stuck in my mind and having to go home and work it out myself.

One of my co-workers, a reporter, has recently started to teach himself Ruby. He took a Java class in college and always had a kind of hankering to get back into programming, so when he and his girlfriend had a fight about chores, he decided to make a web app to help them figure out who was doing what, and to keep track of compliance and send email reminders. Everyone who’s looking for the motivation to re-learn programming needs some precipitating excuse, and that’s his, apparently. Certainly as good a reason as any. He’s been going through a Ruby book meant for the absolute beginner to programming, “Learn to Program,” by Chris Pine.

Yesterday he (my co-worker, not Chris Pine) mentioned that he was working on an exercise to convert Roman numerals into Arabic notation. He was having some trouble. I don’t know Ruby (it’s next on my list), but I went home that night and figured it out in Javascript.

My basic realization for the central algorithm was that all you need to know to add up Roman numerals (in their standardized modern variety anyway) is that the value of each letter is added to the total, unless it’s worth less than the one after it, in which case it gets subtracted from the total. That’s the simplest way to compute it, anyway.

Alternatively, you could go through the two-step process of identifying one- and two-letter sequences (like ‘X’ and ‘IV’) and then adding them. One could argue that that’s easier to read because the one- and two-letter sequences map very well conceptually to the Arabic notation that we think in.

Which would be an interesting question to ask an expert, but in the meantime, here are two solutions that are as concise as I could make them without getting into obnoxious trickiness for its own sake. The first one uses a classic ‘for’ loop, and the second one uses the more elegant functional programming methods map and reduce from the ECMAScript 5 spec, which you unfortunately can’t count on being available in every browser, but are pretty awesome:

The For Loop Version

var romanToArabic = function(romanNumeral) {
  var numberMap = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 },
      sum = 0,
      i, len, num, nextNum,
      romanNumeralArray = romanNumeral.split('');
 
  for (i = 0, len = romanNumeralArray.length; i < len; i++) {
    num = numberMap[romanNumeralArray[i].toUpperCase()];
 
    // Check to see if we're at the end of the array, and if so,
    // set it up so the last element will be compared to zero.
    nextNum = (i + 1 < len) 
      ? numberMap[romanNumeralArray[i + 1].toUpperCase()]
      : 0;
 
    // The value of a letter in a roman numeral gets added to the 
    // running total unless it's less than the value of the one 
    // after it, in which case it gets subtracted.
    sum += (num < nextNum)
      ? num * -1
      : num;
  }
  return sum;
}

The Functional Programming Version

var romanToArabicMoreConcise = function(romanNumeral) {
  var numberMap = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 };
 
  return romanNumeral
    .split('')
    .map(function(romanDigit) {
      return numberMap[romanDigit.toUpperCase()];
    })
    .reduceRight(function(sum, num, i, array) {
 
      // The value of each letter in a roman numeral gets added 
      // to the running total, unless it's less than the value 
      // of the one after it, in which case it gets subtracted. 
      // (If it's the last element, it gets compared to zero.)
 
      return sum += (num < (array[i + 1] || 0))
        ? num * -1
        : num;
    });
}

Explaining map and reduce is beyond the scope of this blog post (try here instead), but just notice that there are no local variables in the second version, except the number map itself, and the function arguments. I find that easier to read, personally. Fewer things to keep track of in my head.

After I completed this post, I noticed that there’s an entire website devoted to answering a wide range of simple programming exercises in like a thousand different languages. And yes, of course this one’s there. Check out the ones for JavaScript and CoffeeScript (a language that compiles down to JavaScript — see this post) and see how they differ from mine.

Then check out the Ruby version:

def fromRoman(roman)
  r = roman.dup.upcase
  n = 0
  until r.empty? do
    case
    when r.start_with?('M')  then v = 1000; len = 1
    when r.start_with?('CM') then v = 900;  len = 2
    when r.start_with?('D')  then v = 500;  len = 1
    when r.start_with?('CD') then v = 400;  len = 2
    when r.start_with?('C')  then v = 100;  len = 1
    when r.start_with?('XC') then v = 90;   len = 2
    when r.start_with?('L')  then v = 50;   len = 1
    when r.start_with?('XL') then v = 40;   len = 2
    when r.start_with?('X')  then v = 10;   len = 1
    when r.start_with?('IX') then v = 9;    len = 2
    when r.start_with?('V')  then v = 5;    len = 1
    when r.start_with?('IV') then v = 4;    len = 2
    when r.start_with?('I')  then v = 1;    len = 1
    else
      raise ArgumentError.new("invalid roman numerals: " + roman)
    end
    n += v
    r[0 .. len-1] = ""
  end
  n
end

Looks a little repetitive in the middle there. I bet it’s possible to write something a bit more succinct — Ruby people are always saying that you could write a fully-featured word-processing program in seven lines. I guess I’ll find out when I learn the language myself.

Leave a Reply

Note: You may use basic HTML in your comments. Your email address will not be published.

Subscribe to this comment feed via RSS