Month: August 2013

Posted on

Números Romanos – Parte I

Durante una entrevista de trabajo, me plantearon el siguiente problema:
Dado un número decimal, conviértelo a notación romana.

Es decir, convertir:

  • 42 en XLII
  • 1000 en M
  • 2013 en MMXIII
  • 69 en XXX :P, etc.
Pequeño recordatorio de cómo funciona dicho sistema…
Los dígitos romanos pueden ser vistos como una dupla (magnitud, potencia), donde la magnitud puede ser 1 o 5, y la potencia varía de 0 a 3.
De este modo, los dígitos romanos y su valor se componen como sigue:
Dígito Valor
I 1 * 100
V 5 * 100
X 1 * 101
L 5 * 101
C 1 * 102
D 5 * 102
M 1 * 103
Posteriormente, como recordamos (y si no recordamos, ¡a recursar la primaria!), los valores (independientemente de su potencia) del 2 al 4 y del 6 al 9 se componen combinando aditivamente a la derecha o substractivamente a la izquierda los dígitos para 1 y 5. Ejemplos:

Decimal Romano
2 II
3 III
4 IV
6 VI
8 VIII
9 IX

Dado este patrón, una solución común suele involucrar el tomar los dígitos base y generar las combinaciones dinámicamente. Véase el siguiente código:
http://discuss.leetcode.com/questions/194/integer-to-roman?page=1&focusedAnswerId=380#380

La implementación es correcta, pero redundante. ¿Qué necesidad hay de ensamblar manualmente cada número romano, cuando las combinaciones pueden ser mapeadas directamente a cada dígito decimal del número a convertir? Es decir:
1985 = 1*103 + 9*102 + 8*101 + 5*0, se representa como: {“M”, “CM”, “LXXX”, “V” } = “MCMLXXXV”.
Para 101 = 1*102 + 0*101 + 1 *100, tenemos {“C”, “”, “I”} = “CI”.

Para mi fortuna, noté ese patrón polinomial mientras analizaba el problema en la entrevista, y me di cuenta que hay una solución totalmente lineal. En lugar de almacenar únicamente los dígitos como constantes en un vector, podemos almacenar todos los posibles números representables por un dígito decimal. Por suerte, los numerales romanos sólo representan del 1 al 3999 (Wikipedia dice que 4999, pero para fines de este artículo da lo mismo). De este modo, podemos utilizar la siguiente tabla:

Magnitud 100 101 102 103
0
1 I X C M
2 II XX CC MM
3 III XXX CCC MMM
4 IV XL CD
5 V L D
6 VI LX DC
7 VII LXX DCC
8 VIII LXXX DCCC
9 IX XC CM

De este modo, la implementación queda como sigue:

package net.rochsquadron.blog;

public class Romans {
        
        public static int MIN_VALUE = 0;
        public static int MAX_VALUE = 3999;
        
        private static String[][] DIGITS = {
            { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" }, // 10^0
            { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" }, // 10^1
            { "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" }, // 10^2
            { "", "M", "MM", "MMM" },    // 10^3
        };
        
        public static String valueOf(int input) {
                // Validate boundaries
                if (input < MIN_VALUE || input > MAX_VALUE )
                        throw new IndexOutOfBoundsException(
                                String.format("Number out of range: %d", input)
                        );
                
                // For each power (0 to 3), locate and add the corresponding number:
                // [power][digit]
                String value = "";
                for(int i = 0; i < DIGITS.length; i++) {
                        value = DIGITS[i][input % 10] + value;
                        input /= 10;
                }
                
                return value;
        }
        
        public static void main(String... args) throws Exception {
                for(String s : args) {
                        int number = Integer.parseInt(s);
                        String roman = valueOf(number);
                        System.out.println(roman);
                }
        }
}

Supuestamente, el entrevistador no había visto este tipo de respuesta antes (que tampoco es tan innovadora; aparece en los primeros resultados de StackOverflow) y esta solución me ayudó a ganar bastantes puntos.