Convert ciphered Roman numerals to Arabic decimals

Question

Write an algorithm to interpret a sequence of letters as a Roman numeral. (see roman numeral rules below)

Each distinct letter has a matching Arabic decimal value, no maximum. But you don't have the key beforehand, so {A=10, I=1, X=5, ... Z=1000000} is decided by your interpretation.

Challenge

1. Read input via STDIN or equivalent and write output via STDOUT or equivalent
2. Valid inputs are combinations of uppercase and lowercase letters i.e. matching \[a-zA-Z]+\
3. Input should be validated to see if the letter sequence can be interpreted as valid Roman numeral
4. If the input passes validation, valid output should be the lowest Arabic decimal interpretation and the key used i.e. Aa is interpreted as 4 {a=5, A=1} not 6 {A=5, a=1} or 9 {a=10, a=1}

Roman Numeral Rules

1. Only letters representing powers of ten can be repeated, maximum of three times successively and four times in total e.g. II III XXXIX

2. If one or more letters are placed after another letter of greater value, add that amount

   AAaa   => 22 {A=10, a=1}          (20 + 2 = 22)  
   bbAAaa => 222 {b=100, A=10, a=1}  (200 + 20 + 2 = 222)   
   

3. If a letter is placed before another letter of greater value, subtract that amount

   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)  
   

   Several rules apply for subtracting amounts from Roman numerals:

   • Only subtract powers of ten i.e. 1, 10, 100... not 5, 50, 500...
   • No double subtraction therefore 18 is written as XVIII not IIXX (10 + 10 - 1 - 1)
   • Do not subtract a number from one that is more than ten times greater.
     You can subtract 1 from 5 or 10 but not from 50, 100, 500...

Example

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}  

Answer 1

Python 2, 415 444 440 419 416 bytes

There aren't all that many Roman numerals, after all. This script creates all of them and checks all permutations of the input, then returns the smallest match.

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