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}  

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