DEV Community

Roman Numeral Converter

Andy Pickle on February 16, 2019

My coding education journey has been a bit, disjointed to say the least. I've stop started on freeCodeCamp, CS50, other tutorials, books, and just ...

Read full post

Dian Fay • Feb 17 '19 • Edited

The last code test I took for an interview involved writing a calculator in Java:

    public Abacus() {
        numerals = new LinkedHashMap<String, Integer>();

        numerals.put("M", 1000);
        numerals.put("D", 500);
        numerals.put("C", 100);
        numerals.put("L", 50);
        numerals.put("X", 10);
        numerals.put("V", 5);
        numerals.put("I", 1);
    }

    /**
     * Find the appropriate divisor for a value, which, in the equation
     * (val - val / divisor) will resolve to the threshold at or above which
     * a subtractive maneuver is necessary to convert to Roman numerals.
     */
    private int getDivisor(int value) {
        while (value > 10) {
            value = value / 10;
        }

        return value;
    }

    public String convert(int arabic) {
        StringBuilder sb = new StringBuilder();

        // preserve a pointer to the last subtractable numeral
        Map.Entry<String, Integer> lastEntry = null;    

        for (Map.Entry<String, Integer> e : numerals.entrySet()) {
            if (lastEntry != null) {
                if (arabic >= 4 * e.getValue()) {
                    // we have a valid subtraction!
                    sb.append(e.getKey());
                    sb.append(lastEntry.getKey());

                    arabic -= (lastEntry.getValue() - e.getValue());
                } else {
                    // e isn't small enough for us to have a valid subtraction
                    // yet, keep going
                    continue;
                }
            }

            // basic additive calculation: as long as the number is bigger than
            // e, keep appending e
            while (arabic >= e.getValue()) {
                sb.append(e.getKey());

                arabic -= e.getValue();
            }

            if (arabic >= e.getValue() - (e.getValue() / getDivisor(e.getValue()))) {
                // the remaining number is close enough to e that we will need
                // to perform a subtractive maneuver with reversed numerals
                lastEntry = e;
            }
        }

        return sb.toString();
    }

pro:

the mapping only includes each Roman digit once
the algorithm is aesthetically pleasing (even if Java isn't the kindest to it)

con:

the algorithm is extremely complicated and the simpler mapping is absolutely not worth it
although it satisfied the battery of unit tests I was given, one of the interviewers had run an extra on it that demonstrated a bug. We all had fun picking it apart, but I don't recall what the exact problem is.

Andy Pickle • Feb 17 '19

Whew man, I don’t know Java at all, so this looks really complicated to me.

Dian Fay • Feb 17 '19

The way it works is by subtracting until you can add based only on the one-to-one mapping in descending order. So if you're trying to convert 1990, it goes like this:

1990, evaluate M (1000); 1990 > 1000 so we have an M, leaving 990 for the next iteration
990 is less than 1000 so MM is wrong, but it's more than 900 (1000 - (1000 / 10)), so we set the lastEntry pointer to M and proceed
Now we're evaluating C (100), but lastEntry is set. 990 > 900 which is CM, giving us MCM so far and leaving 90. I think this is where the bug is but it works in this case :)
90 > (100 - (100 / 10)) so lastEntry is now C
Evaluate L (50); lastEntry is set, but the calculation to test whether L can be subtracted fails, so we proceed
Evaluate X (10): the subtraction test succeeds, so 90 becomes XC and the full result is MCMXC.

Andy Pickle • Feb 17 '19

Nice that’s such a cool way of thinking about it!

ItsASine (Kayla) • Feb 17 '19

function solution(number){
  // todo: solve without defining middle values :(
  var translations = {
    '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
  };
  var answer = '';
  var value = 0;
  var thisPower = 0;

  Object.keys(translations).forEach(function(letter, index, array) {
    thisPower = translations[letter];
    value = Math.floor(number / thisPower);

    number -= value * thisPower;
    answer += letter.repeat(value);
  });

  return answer;
}

Mine works... but I every time I tried doing something clever to not have to define 900, 400, 90, 40, and 9, it wouldn't work on 4, so I gave up on that. I really liked the .repeat so I didn't have to define multiples, though.