Converter números romanos cifrados em decimais árabes

16

Escreva um algoritmo para interpretar uma sequência de letras como um número romano. (veja as regras dos números romanos abaixo)

Cada letra distinta tem um valor decimal em árabe correspondente, no máximo. Mas você não tem a chave de antemão, por isso {A=10, I=1, X=5, ... Z=1000000}é decidido pela sua interpretação.

Desafio

  1. Leia a entrada via STDINou equivalente e grave a saída via STDOUTou equivalente
  2. Entradas válidas são combinações de letras maiúsculas e minúsculas, ou seja, \[a-zA-Z]+\
  3. A entrada deve ser validada para verificar se a sequência de letras pode ser interpretada como um número romano válido
  4. Se a entrada for aprovada na validação, a saída válida deve ser a menor interpretação decimal árabe e a chave usada, ou seja, Aaé interpretada como 4 {a=5, A=1} não 6 {A=5, a=1} ou 9 {a=10, a=1}

Regras dos Números Romanos

  1. Somente letras representando potências de dez podem ser repetidas, no máximo três vezes sucessivas e quatro vezes no total, por exemplo II III XXXIX

  2. Se uma ou mais letras forem colocadas após outra letra de maior valor, adicione esse valor

    AAaa   => 22 {A=10, a=1}          (20 + 2 = 22)  
    bbAAaa => 222 {b=100, A=10, a=1}  (200 + 20 + 2 = 222)   
    
  3. Se uma carta for colocada antes de outra letra de maior valor, subtraia esse valor

    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)  
    

    Várias regras se aplicam para subtrair valores de algarismos romanos:

    • Subtraia apenas poderes de dez, ou seja, 1, 10, 100... não 5, 50, 500...
    • Portanto, nenhuma subtração dupla 18é escrita como XVIII não IIXX (10 + 10 - 1 - 1)
    • Não subtraia um número de um que seja dez vezes maior.
      Você pode subtrair 1a partir de 5 ou 10 , mas não de50, 100, 500...

Exemplo

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
fonte
3
@IamOgbz, isso se transformou em uma ótima pergunta, mas atraiu muitas perguntas nos comentários ao longo do caminho. Agora que você tem reputação suficiente, recomendo a sandbox . Acho muito útil para obter perguntas logo antes de postar.
Trichoplax
CCCLXVII não seria interpretado como CCCXLVII, fornecendo 347?
Skyler #
@ Skyler, você está absolutamente certo, atualizará agora! obrigado.
Iamogbz 15/10/2015
Não vejo nenhuma restrição sobre quais valores as letras individuais podem ter (e, de fato, você menciona 20, que não é o valor de um número romano padrão). Você quer dizer que qualquer número inteiro positivo pode ser representado por um número romano? Nesse caso, Aatem um valor de 1 (A = 1, a = 2).
Msh210 26/10/2015
@ msh210 como as letras só podem ser interpretadas como algarismos romanos, segue-se que os valores das letras individuais podem ser apenas potências de 10 ou 5 vezes potências de 10. 20 foi mencionado apenas em relação à combinação de dois algarismos romanos (e para enfatizar que IXX = 19 não é uma subtração válida). Espero que isso esclareça tudo para você.
Izogbz 27/10/2015

Respostas:

1

Python 2, 415 444 440 419 416 bytes

Afinal, não existem tantos números romanos. Este script cria todos eles e verifica todas as permutações da entrada e, em seguida, retorna a menor correspondência.

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
fonte
Essa é uma boa resposta para o desafio como é agora. Mas na conversa de comentários que foi eliminada mais cedo, foi sugerido que esse sistema (não real) continua após M = 1000, com símbolos para 5k, 10k e assim por diante. Veja o primeiro exemplo no topo: {A = 10, I = 1, X = 5, ... Z = 1000000} é decidido por sua interpretação
edc65 15/10/2015
.., e o último exemplo, a = 5000 ...
edc65 15/10
Eu o atualizei para lidar com todos os casos de teste fornecidos. Duvido que essa abordagem possa ser estendida além de 10.000, pois leva tempo O (n!) No número de dígitos romanos.
Skyler #
@ Skyler, os casos de teste não são exaustivos. O programa deve lidar com todas as permutações possíveis das entradas válidas que podem ser interpretadas de acordo com as regras dos números romanos, com preferência a números mais baixos em casos ambíguos. Também o seu código não poderia lidar com o último caso de teste ligação
iamogbz
Não é import itertools as ie depois i.permutationsmais curto?
gato