Prototypes Better Than Production

As a take-home technical test as part of a job interview process, I was asked to write a function to convert a number into a string containing its representation in Roman numerals. This is an interesting little puzzle and worth a try, so consider writing or pondering your own solution before reading mine.

The precise specification follows:

• “M” = 1000 “D” = 500 “C” = 100 “L” = 50 “X” = 10 “V” = 5 “I” = 1
• To find the value of a set of roman numerals you add up the value of the characters.
• A power of ten can only be repeated three times i.e., XXX = 30, XXXX is not valid.
• Those that are not powers of ten can only appear once, i.e. VV is not valid.
• The numbers must read highest-lowest from the left to the right.
• If a letter of a smaller value appears before a number of a higher value, then the smaller number is to be subtracted from the higher value. ex: IX = 9.
• You can subtract only powers of ten i.e., I, X, C
• Only one character can be used to subtract from a larger character. eg IIX = 8 is not allowed.
• You can’t subtract a number from one that is more than 10 times greater. That is, you can only subtract I from V or X, X from L or C, etc. For e.g., IC can not be used for 99. It must be XCIX.

I began writing a solution in Java, but then found that the mechanics of writing it in Java were obscuring my thinking about the algorithm. I moved to Haskell to prototype my solution. This proved an effective move, allowing me to stop worrying about whether I’m using a String or StringBuffer, and to allow the use of tuples instead of separate classes.

My Haskell solution follows:

module Main where
import System.IO

-- one element per order of magnitude, with the ones value,
--  and the Roman numeral for 1, 5 and 9 on this order.
romans = [(1000, ("M", "" , ""  ))
         ,(100 , ("C", "D", "CM"))
         ,(10  , ("X", "L", "XC"))
         ,(1   , ("I", "V", "IX"))
         ]

-- utility function for converting at 
-- each order of magnitude
multiples 0 _       = ""
multiples 9 (_,_,z) = z
multiples 4 (x,y,_) = x ++ y
multiples 5 (_,y,_) = y
multiples n (x,y,_) | n > 5     = y ++ concat (replicate (n-5) x)  
                    | otherwise = concat $ replicate n x

-- the main work: iterate through the orders of 
-- magnitude, accumulating the result.
romanize x = fst $ foldl step ("", x) romans

step (r,n) (v,s) = (r ++ multiples d s , m)    
    where (d,m) = n `divMod` v 

-- print the (Arabic, Roman) pairs for 1..200
main = mapM_ (print . (\x -> (x , romanize x))) [1..200]

This solution is based on a left fold, working over a list containing the Roman numeral info for each order of magnitude. In romans each list element is a pair containing the order of magnitude (descending order) and a triple with Strings with the Roman numeral representations of 1, 5, and 9 of that order.

I think the code is probably clearer than a further English description, really. I might be wrong, especially since I wrote it, but I’m going to stop narrating the code.

So that was my rapid prototyping in Haskell. It took a short time to write, a very short time to debug. It exposed a couple of little mistakes in my initial algorithm, which I corrected quickly. Exactly what rapid prototyping is supposed to give you.

Now comes the curious part. I rewrote the algorithm in Java. The tuples in romans became an inner class with those four values as member variables, that’s fairly natural. It had two member functions essentially implementing step and multiples. I think the Java code is fairly idiomatic, clear, efficient and generally good. It follows:

import java.io.*;

public class RomanNumerals {

    // for testing, print out (Arabic, Roman) for 1..200.    
    public static void main (String[] args) {
       new RomanNumerals();
    }

    public RomanNumerals () { 
        for (int i = 1; i <= 200; i++ ) {
            System.out.println("("+ i + ",\"" + toRoman(i) +"\")");
        } 
    }

    // one element per order of magnitude,
    // recording the ones value, and the Roman
    // numeral for multiples of 1, 5 and 9.
    Power[] powers = { new Power (1000, "M", "", ""),
                       new Power (100 , "C", "D", "CM"),
                       new Power (10  , "X", "L", "XC"),
                       new Power (1   , "I", "V", "IX")};
    // 0 < num <= 3999, the maximum by the rules
    // (without a numeral for 5000)    
    private String toRoman (int num) {
        StringBuffer buf = new StringBuffer("");
        int power = 0;
        // loop through the orders of magnitude,
        // appending the representation for this order
        // to the running Roman representation.
        while ( num > 0 && power < powers.length ) {
            buf.append( powers[power].convert(num) );
            num = powers[power].remainder(num);
            power++;
        }

        return buf.toString();
    }

    // container for an order of magnitude, knows how to
    // find the representation given the running number.
    class Power {
        private String one, five, nine;        
        private int value;

        public Power (int v, String o, String f, String n) {
            value = v;
            one   = o;
            five  = f; 
            nine  = n;
        }

        // calculates the representation for this order
        public String convert (int num){
            num /= value; // truncate
            // now a few special cases
            if ( num == 0 )                return "";
            if ( num == 9 )                return nine;
            if ( num == 4 )                return one + five;
            if ( num == 5 )                return five;

            // handling of 1-3 and 6-8            
            String base = "";
            if ( num > 5 ) {
                num -= 5;
                base = five;
            }
            // I could do this in a loop, appending.
            // but this unrolled form is more efficient,
            // and it's only 3 cases.
            switch(num) {
                case 1: return base + one;
                case 2: return base + one + one;
                case 3: return base + one + one + one;
                default: return ""; // can't happen            
            }
        }

        // calculates the remainder, the lower-order
        // number left after calculating this order.
        public int remainder (int num){
            return num % value;
        }
    } // class Power
} // class RomanNumerals

But what did I gain by rewriting it in Java? I only did it because that’s what the potential employer needs (I’m sending the Haskell solution too, for fun). Removing that artificial constraint, was there any reason to?

Let’s compare the two implementations:

	Lines	Characters	Binary size (B)	Runtime (s)
Java	111	2406	1448+1170	0.177
Haskell (ghc)	34	947	434156	0.052
Haskell (ghc -O2)	34	947	393531	0.052

Runtimes are measuring the time required to print from 1 to 200, using time.

So by pretty much all of the usual metrics, the Haskell versions are better. They require fewer lines of code, fewer characters, less execution time. Their binaries are considerably heavier, but on the other hand the Java 6 runtime isn’t being counted here. The same source code will run on any platform supported by Java 6 Standard Edition and GHC respectively, though the Haskell binaries are platform-dependent.

Most vitally, the Haskell version is more type-safe, less likely to cause a runtime exception, is source-portable, executes faster and took less time to write (even though I wrote the Haskell from scratch, and translated into Java!).

The only advantage to the Java version that I can see is that my interviewer reads Java but not Haskell. But I consider that a loss for the company, not for Haskell.