Convierta números romanos cifrados a decimales árabes

16

Escribe un algoritmo para interpretar una secuencia de letras como un número romano. (ver las reglas del número romano a continuación)

Cada letra distinta tiene un valor decimal árabe coincidente, sin máximo. Pero no tiene la clave de antemano, {A=10, I=1, X=5, ... Z=1000000}por lo que su interpretación lo decide.

Desafío

  1. Leer entrada vía STDINo equivalente y escribir salida vía STDOUTo equivalente
  2. Las entradas válidas son combinaciones de letras mayúsculas y minúsculas, es decir, coincidencia \[a-zA-Z]+\
  3. La entrada debe validarse para ver si la secuencia de letras puede interpretarse como un número romano válido
  4. Si la entrada pasa la validación, la salida válida debe ser la interpretación decimal más baja en árabe y la clave utilizada, Aaes decir, se interpreta como 4 {a=5, A=1} no 6 {A=5, a=1} o 9 {a=10, a=1}

Reglas de números romanos

  1. Solo se pueden repetir letras que representen potencias de diez, máximo tres veces seguidas y cuatro veces en total, por ejemplo II III XXXIX

  2. Si se colocan una o más letras después de otra letra de mayor valor, agregue esa cantidad

    AAaa   => 22 {A=10, a=1}          (20 + 2 = 22)  
    bbAAaa => 222 {b=100, A=10, a=1}  (200 + 20 + 2 = 222)   
    
  3. Si se coloca una letra antes de otra letra de mayor valor, reste esa cantidad

    Aa    => 4 {a=5, A=1}                 (5 – 1 = 4)  
    AaA   => 19 {A=10, a=1}               (10 + 10 – 1 = 19)  
    BbBaA => 194 {B=100, b=10, A=5, a=1}  (100 + 100 - 10 + 5 - 1 = 194)  
    

    Se aplican varias reglas para restar cantidades de números romanos:

    • Solo resta potencias de diez, es decir, 1, 10, 100... no 5, 50, 500...
    • Por lo tanto, no hay doble substracción 18se escribe como XVIII no IIXX (10 + 10 - 1 - 1)
    • No reste un número de uno que sea más de diez veces mayor.
      Puede restar 1de 5 o 10 , pero no de50, 100, 500...

Ejemplo

Input:

Aa  
BAa  
CCCXLVII   
MMMCDVII  
ABADDF  
XVVX  
FAASGSH  
DXCCDA  
AaBbcDEf   

Output:

4 {a=5, A=1}  
14 {B=10, a=5, A=1}  
347 {C=100, L=50, X=10, V=5, I=1}  
347 {M=100, D=50, C=10, V=5, I=1}  
1921 {A=1000, B=100, D=10, F=1}  
'XVVX' failed Roman numeral test  
7191 {F=5000, A=1000, S=100, G=10, H=1}  
'DXCCDA' failed Roman numeral test
4444 {a=5000, A=1000, b=500, B=100, D=50, c=10, f=5, E=1}  
iamogbz
fuente
3
@IamOgbz esto se ha convertido en una gran pregunta, pero atrajo muchas preguntas en los comentarios en el camino. Ahora que tiene suficiente reputación, le recomiendo el sandbox . Me resulta muy útil para obtener preguntas justo antes de publicar.
trichoplax
¿No se interpretaría CCCLXVII como CCCXLVII, dando 347?
Skyler
@Skyler tienes toda la razón, ¡se actualizará ahora! Gracias.
iamogbz
No veo ninguna restricción sobre qué valores pueden tener las letras individuales (y de hecho mencionas 20, que no es el valor de un número romano estándar). ¿Quiere decir que cualquier número entero positivo puede ser representado por un número romano? En ese caso, Aatiene un valor de 1 (A = 1, a = 2).
msh210
@ msh210 ya que las letras solo pueden interpretarse como números romanos, se deduce que los valores de letras individuales solo pueden ser potencias de 10 o 5 veces potencias de 10. 20 solo se mencionó en relación con la combinación de dos números romanos (y enfatizar que IXX = 19 no es una resta válida). Espero que te lo aclare.
iamogbz

Respuestas:

1

Python 2, 415 444 440 419 416 bytes

No hay tantos números romanos, después de todo. Este script los crea a todos y verifica todas las permutaciones de la entrada, luego devuelve la coincidencia más pequeña.

a=raw_input()
g=range
b=list(set(a))+[' ']*9
from itertools import*
c=[]
s={}
u=1000
for i in g(10*u):
 t,f=(10*u,9*u,5*u,4*u,u,900,500,400,100,90,50,40,10,9,5,4,1),i;r=""
 for j in g(17):k=i/t[j];r+=('W MW Q MQ M CM D CD C XC L XL X IX V IV I').split()[j]*k;i-=t[j]*k
 s[r]=f
for i in permutations(b[:9]):
 r=''
 for j in a:r+='IVXLCMQWE'[i.index(j)]
 if r in s:c+=[s[r]]
print c and min(c)or'%s failed Roman numeral test'%a
Skyler
fuente
Esa es una buena respuesta al desafío tal como es ahora. Pero en la conversación de comentarios que fue eliminada temprano, se insinuó que este sistema (no real) continúa después de M = 1000, que tiene símbolos para 5k, 10k y así sucesivamente. Mire el primer ejemplo en la parte superior: {A = 10, I = 1, X = 5, ... Z = 1000000} es decidido por su interpretación
edc65
.., y el último ejemplo, a = 5000 ...
edc65
Lo actualicé para manejar todos los casos de prueba dados. Dudo que este enfoque pueda extenderse más allá de 10,000, ya que toma O (n) tiempo en el número de dígitos romanos.
Skyler
@Skyler los casos de prueba no son exhaustivos. El programa debe manejar todas las permutaciones posibles de las entradas válidas que se pueden interpretar según las reglas del número romano, con preferencia a los números más bajos en casos ambiguos. Además, su código no pudo manejar el último enlace del
iamogbz
¿No es import itertools as iy luego i.permutationsmás corto?
gato