Konvertieren Sie verschlüsselte römische Ziffern in arabische Dezimalstellen

16

Schreiben Sie einen Algorithmus, um eine Folge von Buchstaben als römische Zahl zu interpretieren. (siehe Regeln für römische Ziffern weiter unten)

Jeder einzelne Buchstabe hat einen passenden arabischen Dezimalwert, kein Maximum. Aber Sie haben den Schlüssel nicht im Voraus, also {A=10, I=1, X=5, ... Z=1000000}entscheidet Ihre Interpretation.

Herausforderung

  1. Eingabe über STDINoder gleichwertig lesen und Ausgabe über STDOUToder gleichwertig schreiben
  2. Gültige Eingaben sind Kombinationen aus Groß- und Kleinbuchstaben, dh Übereinstimmungen \[a-zA-Z]+\
  3. Die Eingabe sollte überprüft werden, um festzustellen, ob die Buchstabenfolge als gültige römische Zahl interpretiert werden kann
  4. Wenn die Eingabe die Validierung besteht, sollte die gültige Ausgabe die niedrigste arabische Dezimalinterpretation sein und der verwendete Schlüssel wird Aaals 4 {a=5, A=1} nicht oder interpretiert6 {A=5, a=1} 9 {a=10, a=1}

Regeln für römische Ziffern

  1. Es können nur Buchstaben mit Zehnerpotenzen wiederholt werden, maximal dreimal hintereinander und insgesamt viermal, z II III XXXIX

  2. Wenn ein oder mehrere Buchstaben nach einem anderen Buchstaben von größerem Wert platziert werden, addieren Sie diesen Betrag

    AAaa   => 22 {A=10, a=1}          (20 + 2 = 22)  
    bbAAaa => 222 {b=100, A=10, a=1}  (200 + 20 + 2 = 222)   
    
  3. Wenn ein Buchstabe vor einem anderen Buchstaben von größerem Wert steht, subtrahieren Sie diesen Betrag

    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)  
    

    Für das Abziehen von Beträgen von römischen Ziffern gelten mehrere Regeln:

    • Subtrahieren Sie nur Zehnerpotenzen, dh 1, 10, 100... nicht 5, 50, 500...
    • Daher 18wird keine doppelte Subtraktion als XVIII nicht geschrieben IIXX (10 + 10 - 1 - 1)
    • Subtrahieren Sie keine Zahl von einer, die mehr als zehnmal größer ist.
      Sie können subtrahieren 1aus 5 oder 10 aber nicht aus50, 100, 500...

Beispiel

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
quelle
3
@IamOgbz das hat sich zu einer großartigen Frage entwickelt, hat aber auf dem Weg eine Menge Fragen in Kommentaren auf sich gezogen. Nun, da Sie genug Ruf haben, empfehle ich die Sandbox . Ich finde es sehr nützlich, um Fragen direkt vor dem Posten zu stellen.
Trichoplax
Würde CCCLXVII nicht als CCCXLVII interpretiert werden und 347 ergeben?
Skyler
@Skyler du hast absolut recht, wird jetzt aktualisiert! Vielen Dank.
iamogbz
Ich sehe keine Einschränkung, welche Werte die einzelnen Buchstaben haben können (und Sie erwähnen tatsächlich 20, was nicht der Wert einer normalen römischen Ziffer ist). Wollen Sie damit sagen, dass jede positive ganze Zahl durch eine römische Zahl dargestellt werden kann? In diesem Fall Aahat einen Wert von 1 (A = 1, a = 2).
msh210
@ msh210 da die buchstaben nur als römische ziffern interpretiert werden können, folgt, dass einzelne buchstaben nur 10er- oder 5er-potenzien sein können 19 ist keine gültige Subtraktion). Hoffe das klärt es für dich auf.
iamogbz

Antworten:

1

Python 2, 415 444 440 419 416 Bytes

Immerhin gibt es nicht allzu viele römische Ziffern. Dieses Skript erstellt alle und überprüft alle Permutationen der Eingabe. Anschließend wird die kleinste Übereinstimmung zurückgegeben.

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
quelle
Das ist eine gute Antwort auf die aktuelle Herausforderung. Aber in der Kommentar-Konversation, die vorzeitig gelöscht wurde, wurde angedeutet, dass dieses (nicht reale) System nach M = 1000 weiterläuft und Symbole für 5k, 10k und so weiter hat. Schauen Sie sich das erste Beispiel oben an: {A = 10, I = 1, X = 5, ... Z = 1000000} wird von Ihrer Interpretation bestimmt
edc65
.. und das letzte Beispiel: a = 5000 ...
edc65
Ich habe es aktualisiert, um alle gegebenen Testfälle zu behandeln. Ich bezweifle, dass dieser Ansatz über 10.000 hinaus verlängert werden kann, da die Anzahl der römischen Ziffern 0 (n!) Beträgt.
Skyler
@Skyler Die Testfälle sind nicht vollständig. Das Programm sollte alle möglichen Permutationen der gültigen Eingaben verarbeiten, die gemäß den Regeln für römische Zahlen interpretiert werden können, wobei in mehrdeutigen Fällen niedrigere Zahlen bevorzugt werden. Auch Ihr Code konnte den letzten Testfall- Link
iamogbz
Ist das nicht import itertools as iund dann i.permutationskürzer?
Katze