Преобразование зашифрованных римских цифр в арабские десятичные дроби

16

Напишите алгоритм для интерпретации последовательности букв как римской цифры. (см. правила римских цифр ниже)

Каждая отдельная буква имеет соответствующее арабское десятичное значение, но не максимальное. Но у вас нет ключа заранее, поэтому это {A=10, I=1, X=5, ... Z=1000000}зависит от вашей интерпретации.

Вызов

  1. Прочитать ввод через STDINили эквивалентный и записать вывод через STDOUTили эквивалентный
  2. Допустимые значения - это комбинации прописных и строчных букв, т.е. \[a-zA-Z]+\
  3. Ввод должен быть проверен, чтобы увидеть, может ли буквенная последовательность интерпретироваться как действительная римская цифра
  4. Если входные данные проходят проверку, допустимым выходным значением должна быть самая низкая арабская десятичная интерпретация, а используемый ключ, т. AaЕ. Интерпретируется как 4 {a=5, A=1} нет 6 {A=5, a=1} или 9 {a=10, a=1}

Римские числовые правила

  1. Только буквы, представляющие степени десяти, могут повторяться, максимум три раза подряд и всего четыре раза, например II III XXXIX

  2. Если одна или несколько букв ставятся после другой буквы большего значения, добавьте эту сумму

    AAaa   => 22 {A=10, a=1}          (20 + 2 = 22)  
    bbAAaa => 222 {b=100, A=10, a=1}  (200 + 20 + 2 = 222)   
    
  3. Если буква помещена перед другой буквой большей стоимости, вычтите эту сумму

    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)  
    

    Несколько правил применяются для вычитания сумм из римских цифр:

    • Вычтите только десять степеней, т.е. 1, 10, 100... не 5, 50, 500...
    • Поэтому двойное вычитание 18не записывается как XVIII не IIXX (10 + 10 - 1 - 1)
    • Не вычитайте число из числа, которое больше чем в десять раз.
      Вы можете вычесть 1из 5 или, 10 но не из50, 100, 500...

пример

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
источник
3
@IamOgbz это превратилось в большой вопрос, но по пути привлекло много вопросов в комментариях. Теперь, когда у вас достаточно репутации, я рекомендую песочницу . Я нахожу это очень полезным для получения вопросов прямо перед публикацией.
Трихоплакс
Разве CCCLXVII не будет интерпретирован как CCCXLVII, давая 347?
Скайлер
@Skyler, вы абсолютно правы, обновите сейчас! Благодарю.
iamogbz
Я не вижу каких-либо ограничений в отношении того, какие значения могут иметь отдельные буквы (и действительно, вы упоминаете 20, что не является значением стандартной римской цифры). Вы хотите сказать, что любое положительное целое число может быть представлено римской цифрой? В этом случае Aaимеет значение 1 (A = 1, a = 2).
msh210
@ msh210, так как буквы могут быть интерпретированы только как римские цифры, из этого следует, что отдельные буквенные значения могут быть степенями, кратными 10 или 5, умноженным на 10. 20 было упомянуто только в отношении объединения двух римских цифр (и подчеркнуть, что IXX = 19 не является действительным вычитанием). Надеюсь, это прояснит для вас.
iamogbz

Ответы:

1

Python 2, 415 444 440 419 416 байт

В конце концов, римских цифр не так много. Этот скрипт создает их все и проверяет все перестановки ввода, а затем возвращает наименьшее совпадение.

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
Скайлер
источник
Это хороший ответ на вызов, как сейчас. Но в разговоре с комментариями, который был уничтожен рано, намекнули, что эта (не настоящая) система продолжается после M = 1000, имея символы для 5k, 10k и так далее. Посмотрите на первый пример сверху: {A = 10, I = 1, X = 5, ... Z = 1000000} определяется вашей интерпретацией
edc65
.. и последний пример, а = 5000 ...
edc65
Я обновил его, чтобы обработать все данные тесты. Я сомневаюсь, что этот подход может быть расширен за 10 000, так как на количество римских цифр уходит O (n!) Время.
Скайлер
@Skyler тестовые случаи не являются исчерпывающими. Программа должна обрабатывать все возможные перестановки действительных входных данных, которые могут быть интерпретированы в соответствии с правилами римских цифр, причем предпочтение отдается меньшим числам в неоднозначных случаях. Также ваш код не может обработать последнюю ссылку
iamogbz
Не , import itertools as iа затем i.permutationsкороче?
кот