Konwertuj zaszyfrowane cyfry rzymskie na dziesiętne cyfry arabskie

16

Napisz algorytm interpretujący ciąg liter jako cyfrę rzymską. (patrz reguły cyfr rzymskich poniżej)

Każda odrębna litera ma pasującą arabską wartość dziesiętną, bez wartości maksymalnej. Ale nie masz klucza wcześniej, więc {A=10, I=1, X=5, ... Z=1000000}decyduje o tym twoja interpretacja.

Wyzwanie

  1. Odczytaj dane wejściowe przez STDINlub równoważne i napisz dane wyjściowe przez STDOUTlub równoważne
  2. Prawidłowe dane wejściowe to kombinacje wielkich i małych liter, tj. Dopasowanie \[a-zA-Z]+\
  3. Dane wejściowe należy sprawdzić, aby sprawdzić, czy sekwencję liter można interpretować jako prawidłową liczbę rzymską
  4. Jeśli dane wejściowe przejdą walidację, prawidłową wartością wyjściową powinna być najniższa arabska interpretacja dziesiętna, a użyty klucz, tzn. AaInterpretowany jako 4 {a=5, A=1} nie 6 {A=5, a=1} lub 9 {a=10, a=1}

Reguły liczb rzymskich

  1. Tylko litery reprezentujące moc dziesięciu mogą być powtarzane, maksymalnie trzy razy kolejno i łącznie cztery razy, np II III XXXIX

  2. Jeśli jedna lub więcej liter jest umieszczonych po innej literze o większej wartości, dodaj tę kwotę

    AAaa   => 22 {A=10, a=1}          (20 + 2 = 22)  
    bbAAaa => 222 {b=100, A=10, a=1}  (200 + 20 + 2 = 222)   
    
  3. Jeśli litera zostanie umieszczona przed inną literą o większej wartości, odejmij tę kwotę

    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)  
    

    Odejmowanie kwot od cyfr rzymskich ma kilka zasad:

    • Odejmuj tylko potęgi dziesięciu, czyli 1, 10, 100... nie 5, 50, 500...
    • Dlatego podwójne odejmowanie nie 18jest zapisane jako XVIII nie IIXX (10 + 10 - 1 - 1)
    • Nie odejmuj liczby od liczby większej niż dziesięć razy.
      Można odjąć 1od 5 lub 10 ale nie od50, 100, 500...

Przykład

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
źródło
3
@IamOgbz stało się to świetnym pytaniem, ale po drodze przyciągnęło wiele pytań. Teraz, gdy masz wystarczającą reputację, polecam piaskownicę . Uważam, że jest to bardzo przydatne w zadawaniu pytań tuż przed opublikowaniem.
trichoplax
Czy CCCLXVII nie byłby interpretowany jako CCCXLVII, dając 347?
Skyler,
@ Skyler masz absolutną rację, zaktualizuje się teraz! dzięki.
iamogbz,
Nie widzę żadnych ograniczeń co do wartości, jakie mogą mieć poszczególne litery (i rzeczywiście wspominasz o 20, co nie jest wartością standardowej cyfry rzymskiej). Czy chcesz powiedzieć, że każda dodatnia liczba całkowita może być reprezentowana przez cyfrę rzymską? W takim przypadku Aama wartość 1 (A = 1, a = 2).
msh210,
@ msh210, ponieważ litery można interpretować tylko jako cyfry rzymskie, wynika z tego, że poszczególne wartości liter mogą być potęgami 10 lub 5 razy potęgami 10. 10. 20 wspomniano tylko w odniesieniu do łączenia dwóch cyfr rzymskich (i aby podkreślić, że IXX = 19 nie jest prawidłowym odejmowaniem). Mam nadzieję, że to ci wyjaśni.
iamogbz

Odpowiedzi:

1

Python 2, 415 444 440 419 416 bajtów

W końcu nie ma tylu cyfr rzymskich. Ten skrypt tworzy je wszystkie i sprawdza wszystkie permutacje danych wejściowych, a następnie zwraca najmniejsze dopasowanie.

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
źródło
To dobra odpowiedź na obecne wyzwanie. Ale w rozmowie dotyczącej komentarza, która została wcześniej usunięta, zasugerowano, że ten (nie prawdziwy) system działa po M = 1000, mając symbole dla 5k, 10k i tak dalej. Spójrz na pierwszy przykład u góry: {A = 10, I = 1, X = 5, ... Z = 1000000} zależy od twojej interpretacji
edc65
.. i ostatni przykład, a = 5000 ...
edc65
Zaktualizowałem go, aby obsługiwał wszystkie podane przypadki testowe. Wątpię, by to podejście mogło zostać przedłużone do 10.000, ponieważ zajmuje O (n!) Czas na liczbę cyfr rzymskich.
Skyler
@ Skyler przypadki testowe nie są wyczerpujące. Program powinien obsługiwać wszystkie możliwe kombinacje prawidłowych danych wejściowych, które mogą być interpretowane zgodnie z regułami cyfr rzymskich, z pierwszeństwem dla mniejszych liczb w niejednoznacznych przypadkach. Również twój kod nie mógł obsłużyć linku
iamogbz
Nie jest, import itertools as ia potem jest i.permutationskrótszy?
kot