I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Roman Numeral Conversion

08.15.2012
| 9330 views |
  • submit to reddit

Thursday is code puzzler day here at DZone. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Do you have code puzzlers that you'd like to share with the DZone community?  If so, please submit here. 

Roman Numeral Conversion

In today's challenge, create a method that accepts a String parameter representing a Roman numeral, and return the decimal equivalent of it. Just in case you need it, here is a chart of Roman numeral values.

Catch up on all our previous puzzlers here.

Comments

Andreas Kaubisch replied on Thu, 2012/08/16 - 1:00am

One Java solution

 public class RomanConverter {
    private class Literal {
        public char literal;
        public int value;
        
        public Literal(char literal, int value) {
            this.literal = literal;
            this.value = value;
        }
    }
    
    private final Literal[] ROMAN_LITERALS = new Literal[] {
        new Literal('I', 1),
        new Literal('V', 5),
        new Literal('X', 10),
        new Literal('L', 50),
        new Literal('C', 100),
        new Literal('D', 500),
        new Literal('M', 1000)
    };
    
    public int getNumber(String roman) {
        int decimal = 0;
        int lastPosition = 0;
        for(int i = roman.length()-1 ; i >= 0; i--) {
            char c = roman.charAt(i);
            Literal foundLiteral = null;
            int j = 0;
            for(j = 0; j < ROMAN_LITERALS.length; j++) {
                if(c == ROMAN_LITERALS[j].literal) {
                    foundLiteral = ROMAN_LITERALS[j];
                    break;
                }
            }
            if(lastPosition <= j) {
                decimal += foundLiteral.value;
                lastPosition = j; 
            } else {
                decimal -= foundLiteral.value;
            }
        }
        
        return decimal;
    }
    
    public static void main(String[] args) {
        RomanConverter converter = new RomanConverter();
        System.out.println(converter.getNumber("DCCCXC"));
        System.out.println(converter.getNumber("MDCCC"));
        System.out.println(converter.getNumber("LXXXIV"));
    }
}

T Vosse replied on Thu, 2012/08/16 - 2:31am

This is a solution in Javascript. I'm not claiming points for legibility. If you mind about the recursion: it's a tail recursion, so the compiler should be able to rewrite it to a loop, although it will probably not remove the superfluous creation of the extra array.

var syms = "IVXLCDM";
var vals = [1, 5, 10, 50, 100, 500, 1000];

function romana2int(rArr) {
    if (rArr.length === 0) {
        return 0;
    } else {
        var first = syms.indexOf(rArr[0]);
        var rest = rArr.slice(1)
        var higherFollows = rest.some(function (elt) {
            return syms.indexOf(elt) > first;
        });
        return (higherFollows? -vals[first]: vals[first]) +
              romana2int(rest);
    }
}

function roman2int(rStr) {
    return romana2int(rStr.split(""));
}

var examples = [ "I", "II", "IV", "VI", "XI", "XLII", "DCCCXC", "MD" ];

for (var ei in examples) {
    console.log(ei + ". " + examples[ei] + " = " + roman2int(examples[ei]));
}

 

Shahzada Hatim replied on Thu, 2012/08/16 - 3:03am

I am interested in solving the opposite problem: finding roman numeral given an integer.

Vijay Nathani replied on Fri, 2012/08/17 - 2:03am in response to: Andreas Kaubisch

Good work Andreas Kaubisch. Your solution rewritten in Groovy.

def toNumber(roman) {
	def ROMAN_LITERALS = ['I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000]
	def positions = ROMAN_LITERALS.keySet().toList()
	def lastPosition = 0
	(roman.reverse().collect { romanChar ->
		def subtractOrAdd = (lastPosition > positions.indexOf(romanChar))?-1:1
		lastPosition = Math.max(lastPosition, positions.indexOf(romanChar)) 
		ROMAN_LITERALS[romanChar] * subtractOrAdd
	}).sum()
}

[ "DCCCXC", "MDCCC", "LXXXIV" ].each { println toNumber(it) } //prints 890,1800,84  

Mihai Dinca - P... replied on Thu, 2012/08/16 - 6:55am

Another solution (similar to that of Andreas Kaubisch) will be to consider the following:

private final Symbol[] ROMAN_SYMBOLS = new Symbol[] {
        new Symbol('I', 1), 
        new Symbol('IV', 4),
        new Symboll('V', 5),
        new Symbol('IX', 9),
        new Symbol('X', 10),
        new Symbol('XL', 40),
        new Symbol('L', 50),
        new Symbol('XC', 90),
        new Symbol('C', 100),
        new Symbol('CD', 400),
        new Symbol('D', 500),
        new Symbol('CM', 900)
        new Symbol('M', 1000)
    }; 

public static int getNumber(String roman) { int start = 0, value = 0; for (int i = 0; i < ROMAN_SYMBOLS.length; i++) { while (roman.startsWith(ROMAN_SYMBOLS[i].symbol, start)) { value += ROMAN_SYMBOLS[i].value; start += ROMAN_SYMBOLS[i].symbol.length(); } } return start == roman.length() ? value : -1; }

 

T Vosse replied on Thu, 2012/08/16 - 7:19am in response to: Mihai Dinca - Panaitescu

I'm not completely sure about the roman numeral syntax, but your solution won't do IIM; you would have to write DCCCCLXXXXVIII.

Also, now that I look at it: it would turn IV into 6, doesn't it?

Carl Manson replied on Thu, 2012/08/16 - 7:40am

A quick java option (seems to work, would make the Lists static in a class somewhere though I guess):

public int getValueOfRomanNumeral(String input) {
	List<Character> numerals = Arrays.asList('I', 'V', 'X', 'L', 'C', 'D', 'M');
	List<Integer> values = Arrays.asList(1, 5, 10, 50, 100, 500, 1000);

	int totalValue = 0;
	
	char[] chars = input.toUpperCase().toCharArray();
	
	for (int idx = 0; idx < chars.length; idx++) {
		int idxOfNumeral = numerals.indexOf(chars[idx]);
		
		if (idxOfNumeral > -1) {
			int valueOfNumeral = values.get(idxOfNumeral);
			if (idx < chars.length - 1) { 
				int indexOfNext = numerals.indexOf(chars[idx + 1]);
				if (indexOfNext > idxOfNumeral) {
					valueOfNumeral = values.get(indexOfNext) - valueOfNumeral;
					idx++;
				}
			}
			totalValue += valueOfNumeral;
		}
	}
	return totalValue;
}

Carl Manson replied on Thu, 2012/08/16 - 7:43am in response to: T Vosse

I don't think IIM is a valid roman numeral.  I assume you are meaning 998?  I think 998 should be written as DCDLXLVIII.

T Vosse replied on Thu, 2012/08/16 - 8:12am in response to: Carl Manson

There are no hard rules, apart from not repeating more than three identical symbols in a row. MIM isn't forbidden, even writing IIIV isn't forbidden. If the function would throw an exception or something when it fails, that might be a solution.

Carl Manson replied on Thu, 2012/08/16 - 8:22am in response to: T Vosse

I do believe there are rules with roman numerals and your examples are in fact forbidden:  http://www.factmonster.com/ipka/A0769547.html

However, the routine I created relies on a valid roman numeral being supplied, so would fail if passed invalid Strings (puzzle didn't say to validate though).

 

Mihai Dinca - P... replied on Thu, 2012/08/16 - 8:37am in response to: T Vosse

Yes. The array must be written in reverse like :

private final Symbol[] ROMAN_SYMBOLS = new Symbol[] {
        new Symbol('M', 1000),
        new Symbol('CM', 900),
        new Symbol('D', 500),
        new Symbol('CD', 400),
        new Symbol('C', 100),
        new Symbol('XC', 90),
        new Symbol('L', 50),
        new Symbol('XL', 40),
        new Symbol('X', 10),
        new Symbol('IX', 9),
        new Symboll('V', 5),
        new Symbol('IV', 4),
        new Symbol('I', 1)
    }; 

 and IIM is not a valid numeral. You can create a method to verify if a String is a valid roman numeral and test it to throw an IllegalArgumentException.

T Vosse replied on Thu, 2012/08/16 - 8:44am in response to: Carl Manson

That's what you when the requirements are underspecified: solutions that cannot be compared completely. And my comment was initially directed to the solution above yours, BTW, which matches string onset with a few fixed strings.

Anyway, I'll repeat: there are no hard rules for Roman numbers, just conventions. AFAIK there is no authorative document that laid down the rules, just a whole bunch of examples from different ages.

James Sugrue replied on Thu, 2012/08/16 - 10:25am in response to: Shahzada Hatim

Sounds like another interesting challenge - go for it :) 


James

 

Earnest Dyke replied on Thu, 2012/08/16 - 11:43am

Decided to take a little different tact and implemented as a set of Drools rules. Maybe not as "short" as some solutions but illustrates another way of doing it.

Earnie! 

package com.ferguson.codepuzzler;

import static org.junit.Assert.assertEquals;

import java.io.File;
import java.io.FileInputStream;
import java.io.InputStream;

import org.drools.KnowledgeBase;
import org.drools.KnowledgeBaseFactory;
import org.drools.builder.KnowledgeBuilder;
import org.drools.builder.KnowledgeBuilderError;
import org.drools.builder.KnowledgeBuilderErrors;
import org.drools.builder.KnowledgeBuilderFactory;
import org.drools.builder.ResourceType;
import org.drools.io.ResourceFactory;
import org.drools.runtime.StatefulKnowledgeSession;
import org.drools.runtime.rule.FactHandle;
import org.junit.BeforeClass;
import org.junit.Test;

public class RomanNumerals {
	private static KnowledgeBase kbase = null;

	@BeforeClass
	public static void setup() {
		KnowledgeBuilder kbuilder = KnowledgeBuilderFactory
				.newKnowledgeBuilder();
		try {
			InputStream rulesIs = new FileInputStream(
					new File(
							"c:\\workspaces\\wonderings\\src\\com\\ferguson\\codepuzzler\\RomanNumeral.drl"));
			kbuilder.add(ResourceFactory.newInputStreamResource(rulesIs),
					ResourceType.DRL);
		} catch (Exception e) {
			System.out.println(e.getMessage());
			throw new RuntimeException(e);
		}
		KnowledgeBuilderErrors errors = kbuilder.getErrors();
		if (errors.size() > 0) {
			for (KnowledgeBuilderError error : errors) {
				System.out.println(error);
			}
			throw new IllegalArgumentException("Rules contained errors");
		}
		System.out.println("Rules compiled successfully");
		kbase = KnowledgeBaseFactory.newKnowledgeBase();
		kbase.addKnowledgePackages(kbuilder.getKnowledgePackages());

	}

	@Test
	public void convertRoman() throws Exception {
		StatefulKnowledgeSession ksession = kbase.newStatefulKnowledgeSession();
		RomanNumeralConversion rnc = null;
		FactHandle fh = null;
		
		rnc = new RomanNumeralConversion("DCCCXC");
		fh = ksession.insert(rnc);
		ksession.fireAllRules();
		ksession.retract(fh);
		assertEquals(new Integer(890), rnc.getNumber());
		System.out.println(rnc.getRomanNumber() + " = " + rnc.getNumber());

		rnc = new RomanNumeralConversion("MDCCC");
		fh = ksession.insert(rnc);
		ksession.fireAllRules();
		ksession.retract(fh);
		assertEquals(new Integer(1800), rnc.getNumber());
		System.out.println(rnc.getRomanNumber() + " = " + rnc.getNumber());

		rnc = new RomanNumeralConversion("LXXXIV");
		fh = ksession.insert(rnc);
		ksession.fireAllRules();
		ksession.retract(fh);
		assertEquals(new Integer(84), rnc.getNumber());
		System.out.println(rnc.getRomanNumber() + " = " + rnc.getNumber());

	}
}


package com.ferguson.codepuzzler;

public class RomanNumeralConversion {
	private String romanNumber;
	private Integer number = 0;
	private int nextChar;
	private int last = -1;

	public RomanNumeralConversion(String romanNumber) {
		this.romanNumber = romanNumber;
		nextChar = this.romanNumber.length() - 1;
	}

	public String getRomanNumber() {
		return romanNumber;
	}

	public void setRomanNumber(String romanNumber) {
		this.romanNumber = romanNumber;
	}

	public Integer getNumber() {
		return number;
	}

	public void setNumber(Integer number) {
		this.number = number;
	}

	public char getNext() {
		if (nextChar < 0) {
			return 'Z';
		}
		return romanNumber.charAt(nextChar);
	}

	public int getLast() {
		return last;
	}

	public void increment(int inc) {
		number += inc;
		nextChar--;
		last = inc;
	}

	public void decrement(int dec) {
		number -= dec;
		nextChar--;
		last = dec;
	}
} 

 And the rules:

package com.ferguson.codepuzzler;

rule "I pre"
	when 
		$rnc : RomanNumeralConversion(next == 'I' && last <= 1)
	then
		modify($rnc) { 
			increment(1); 
		}
end

rule "I post"
	when 
		$rnc : RomanNumeralConversion(next == 'I' && last > 1)
	then
		modify($rnc) { 
			decrement(1); 
		}
end

rule "V pre"
	when 
		$rnc : RomanNumeralConversion(next == 'V' && last <= 5)
	then
		modify($rnc) { 
			increment(5); 
		}
end

rule "V post"
	when 
		$rnc : RomanNumeralConversion(next == 'V' && last > 5)
	then
		modify($rnc) { 
			decrement(5); 
		}
end

rule "X pre"
	when 
		$rnc : RomanNumeralConversion(next == 'X' && last <= 10)
	then
		modify($rnc) { 
			increment(10); 
		}
end

rule "X post"
	when 
		$rnc : RomanNumeralConversion(next == 'X' && last > 10)
	then
		modify($rnc) { 
			decrement(10); 
		}
end


rule "L post"
	when 
		$rnc : RomanNumeralConversion(next == 'L' && last > 50)
	then
		modify($rnc) { 
			decrement(50); 
		}
end


rule "L pre"
	when 
		$rnc : RomanNumeralConversion(next == 'L' && last <= 50)
	then
		modify($rnc) { 
			increment(50); 
		}
end

rule "C pre"
	when 
		$rnc : RomanNumeralConversion(next == 'C' && last <= 100)
	then
		modify($rnc) { 
			increment(100); 
		}
end

rule "C post"
	when 
		$rnc : RomanNumeralConversion(next == 'C' && last > 100)
	then
		modify($rnc) { 
			decrement(100); 
		}
end

rule "D pre"
	when 
		$rnc : RomanNumeralConversion(next == 'D' && last <= 500)
	then
		modify($rnc) { 
			increment(500); 
		}

end
rule "D post"
	when 
		$rnc : RomanNumeralConversion(next == 'D' && last > 500)
	then
		modify($rnc) { 
			decrement(500); 
		}
end

rule "M pre"
	when 
		$rnc : RomanNumeralConversion(next == 'M' && last <= 1000)
	then
		modify($rnc) { 
			increment(1000); 
		}

end
rule "M post"
	when 
		$rnc : RomanNumeralConversion(next == 'M' && last > 1000)
	then
		modify($rnc) { 
			decrement(1000); 
		}
end 

 Earnie!

 

 

Rafał Rębacz replied on Thu, 2012/08/16 - 4:52pm

Some improvemens guys?:)

public class RomanNumbersConverter {

	Map<Character, Integer> container;
	
	public RomanNumbersConverter() {
		container = new HashMap<Character, Integer>();
		container.put('I', 1);
		container.put('V', 5);
		container.put('X', 10);
		container.put('L', 50);
		container.put('C', 100);
		container.put('D', 500);
		container.put('M', 1000);
	}
	
	public int roman(String roman) {
		int prevNum = 0;
		int currNum = 0;
		int sum = 0;
		char [] romanChars = roman.toCharArray();
		
		for(int i = romanChars.length - 1; i >= 0 ; i--) {
			currNum = container.get(romanChars[i]);
			
			if (currNum == prevNum || currNum > prevNum) {
				sum += currNum ;
			} else if (currNum < prevNum) {
				sum -= currNum;
			}

			prevNum = currNum;
		}
		
		return sum;
	}
}

 

Joel Buckley replied on Fri, 2012/08/17 - 12:58am

With error/syntax checking for non-RomanNumerals, >3 Repeats, and Invalid Subtract:
public class Roman {
    private static final String ROMAN = "IVXLCDM";
    private static final int[] VALUE = new int[] {1, 5, 10, 50, 100, 500, 1000};
    public static int valueOf(String roman) {
        int index, count = 0, last = -1, number = 0;
        for (int inx = 0; inx < roman.length(); ++inx) {
            index = ROMAN.indexOf(roman.charAt(inx));
            if (index == -1) {                          // e.g. "A"
                throw new IllegalArgumentException("Non-RomanNumeral:" + roman);
            } else if (index == last && count == 3) {   // e.g. "IIII"
                throw new IllegalArgumentException("Too Many Repeats:" + roman);
            } else if (last >= 0 && last - index < -2) { // e.g. "IL"
                throw new IllegalArgumentException("Illegal subtract:" + roman);
            } else if (last < 0) {                      // first value letter.
                count = 1;
                number = VALUE[index];
            } else if (index > last) {                  // higher value letter.
                count = 3;
                number += VALUE[index] - (VALUE[last] << 1);
            } else if (index == last) {                 // repeat value letter.
                count += 1;
                number += VALUE[index];
            } else {                                    // lower value letter.
                count = 1;
                number += VALUE[index];
            }
            last = index;
        }
        return number;
    }
    public static void main(String[] args) {
        for (String arg : args) {
            try {
                System.out.println(arg + "==" + Roman.valueOf(arg));
            } catch (IllegalArgumentException oops) {
                System.out.println(oops.getMessage());
            }
        }
    }
} /** End Class. */

sun east replied on Fri, 2012/08/17 - 4:08am

Scala 2.10

def r2i(str: String): Int = {
  val m = Map('I'->1, 'V'->5, 'X'->10, 'L'->50, 'C'->100, 'D'->500, 'M'->1000)
  val xs = str.map(m)
  val ys = (xs,xs.tail:+0).zipped.map{ case(a,b) => if(a<b) -1 else 1 }
  (xs,ys).zipped.map{ case(x,y) => x*y }.sum

Ugur Guney replied on Fri, 2012/08/17 - 9:59am

algorithm taken from Carl Manson (I have my own but I like comparing indexs. I think comparing values is better concept, so I compared values). I tried to improve readability. 21 lines (Carl Manson's code) increased to 63 lines. Do you think it's worthy?  
public int getRomanValue(String literal) {
		char[] chars = literal.trim().toUpperCase().toCharArray();
		int totalValue = 0;
		
		for (int i = 0; i < chars.length; i++) {
			RomanChar currentRomanChar = RomanChar.valueOf(chars[i]);
			int currentValue = 0;
			if (i < chars.length - 1) {
				currentValue = currentRomanChar.getValue();
				RomanChar nextRomanChar = RomanChar.valueOf(chars[i + 1]);
				if (RomanChar.isSmaller(currentRomanChar, nextRomanChar)) {
					currentValue = nextRomanChar.getValue() - currentRomanChar.getValue();
					i++;
				}
			}
			totalValue += currentValue;
		}
		return totalValue;
}

public enum RomanChar {
	I(1),
	V(5),
	X(10),
	L(50),
	C(100),
	D(500),
	M(100);
	
	private int value;
	
	public int getValue() {
		return value;
	}
	
	RomanChar(int value) {
		this.value = value;
	}
	
	public static RomanChar valueOf(char romanChar) {
		switch (String.valueOf(romanChar).toLowerCase().toCharArray()[0]) {
			case 'i': return RomanChar.I;
			case 'v': return RomanChar.V;
			case 'x': return RomanChar.X;
			case 'l': return RomanChar.L;
			case 'c': return RomanChar.C;
			case 'd': return RomanChar.D;
			case 'm': return RomanChar.M;
			default: return null;
		}
	}
	
	public static boolean isBigger(RomanChar roman1, RomanChar roman2) {
		return compareValues(roman1, roman2) == 1;
	}
	
	public static boolean isSmaller(RomanChar roman1, RomanChar roman2) {
		return compareValues(roman1, roman2) == -1;
	}
	
	private static int compareValues(RomanChar roman1, RomanChar roman2) {
		if (roman1.getValue() > roman2.getValue()) {
			return 1;
		}
		else if (roman1.getValue() == roman2.getValue()) {
			return 0;
		} else {
			return -1;
		}
	}
	
	@Override
	public String toString() {
		return String.valueOf(this.value);
        }

Piotr Szaranski replied on Fri, 2012/08/17 - 10:08am

	private static Map<Character, Integer> rm = new HashMap<Character, Integer>();
	
	static {
		rm.put('I', 1); rm.put('V', 5); rm.put('X', 10); rm.put('L', 50); rm.put('C', 100); rm.put('D', 500); rm.put('M', 1000);
	}
	
	private static int formatRoman(String in) {
		int ret = 0;
		for (int i = 0; i < in.length(); i++) {
			int val = rm.get(in.charAt(i));
			if (i + 1 < in.length()) {
				if (rm.get(in.charAt(i + 1)) > val) {
					val = -val;
				}
			}
			ret += val;
		}
		return ret;
	} 

Timothy Perrigo replied on Fri, 2012/08/17 - 12:13pm in response to: Ugur Guney

I think line 7 (int currentValue = 0) should be: int currentValue = currentRomanChar.getValue().  Otherwise, it will map "VI" to 5 (and "VII" to 6, etc).

Timothy Perrigo replied on Fri, 2012/08/17 - 12:38pm in response to: Timothy Perrigo

Sorry, this was meant to be a response to Ugur Guney's solution.

Ugur Guney replied on Fri, 2012/08/17 - 7:35pm

Thank you 

Timothy Perrigo. You're right. I focused on refactoring so i missed the algorithm.

Ebrahim Rajabzadeh replied on Mon, 2012/08/20 - 12:21pm

Recursive in Python:

symbols = "MDCLXVI"
values  = [1000, 500, 100, 50, 10, 5, 1]

def roman(s):
    for i, c in enumerate(symbols):
        j = s.find(c)
        if j >= 0:
            return -1*roman(s[0:j]) + values[i] + roman(s[(j+1):])
    return 0

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.