Mengonversi angka Romawi yang disandikan menjadi desimal Arab

16

Tulis algoritma untuk menafsirkan urutan huruf sebagai angka Romawi. (lihat aturan angka romawi di bawah)

Setiap huruf berbeda memiliki nilai desimal Arab yang cocok, tidak maksimal. Tetapi Anda tidak memiliki kunci sebelumnya, jadi {A=10, I=1, X=5, ... Z=1000000}putuskan dengan interpretasi Anda.

Tantangan

  1. Baca input melalui STDINatau setara dan tulis output melalui STDOUTatau setara
  2. Input yang valid adalah kombinasi huruf besar dan kecil yaitu pencocokan \[a-zA-Z]+\
  3. Masukan harus divalidasi untuk melihat apakah urutan huruf dapat diartikan sebagai angka Romawi yang valid
  4. Jika input melewati validasi, output yang valid harus menjadi interpretasi desimal Arab terendah dan kunci yang digunakan yaitu Aaditafsirkan sebagai 4 {a=5, A=1} tidak 6 {A=5, a=1} atau 9 {a=10, a=1}

Aturan Angka Romawi

  1. Hanya huruf yang mewakili kekuatan sepuluh yang dapat diulang, maksimal tiga kali berturut-turut dan total empat kali misalnya II III XXXIX

  2. Jika satu atau lebih huruf ditempatkan setelah huruf lain yang nilainya lebih besar, tambahkan jumlah itu

    AAaa   => 22 {A=10, a=1}          (20 + 2 = 22)  
    bbAAaa => 222 {b=100, A=10, a=1}  (200 + 20 + 2 = 222)   
    
  3. Jika suatu huruf diletakkan di depan huruf lain yang nilainya lebih besar, kurangi jumlah itu

    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)  
    

    Beberapa aturan berlaku untuk mengurangi jumlah dari angka Romawi:

    • Hanya kurangi sepuluh kekuatan yaitu 1, 10, 100... tidak 5, 50, 500...
    • Tidak ada pengurangan ganda 18yang ditulis sebagai XVIII tidak IIXX (10 + 10 - 1 - 1)
    • Jangan kurangi angka dari yang lebih dari sepuluh kali lebih besar.
      Anda dapat mengurangi 1dari 5 atau 10 tetapi tidak dari50, 100, 500...

Contoh

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
sumber
3
@IamOgbz ini telah berubah menjadi pertanyaan besar tetapi menarik banyak pertanyaan di komentar sepanjang jalan. Sekarang setelah Anda memiliki reputasi yang cukup, saya sarankan kotak pasir . Saya merasa sangat berguna untuk mendapatkan pertanyaan tepat sebelum memposting.
trichoplax
Bukankah CCCLXVII dapat diartikan sebagai CCCXLVII, memberi 347?
Skyler
@ Skyler Anda benar sekali, akan memperbarui sekarang! Terima kasih.
iamogbz
Saya tidak melihat batasan pada nilai apa yang dapat dimiliki masing-masing huruf (dan memang Anda menyebutkan 20, yang bukan nilai angka Romawi standar). Apakah Anda bermaksud mengatakan bahwa setiap bilangan bulat positif dapat diwakili oleh angka Romawi? Dalam hal ini, Aamemiliki nilai 1 (A = 1, a = 2).
msh210
@ msh210 karena huruf-huruf hanya dapat diartikan sebagai Angka Romawi, maka nilai-nilai huruf individu hanya dapat kekuatan 10 atau 5 kali kekuatan 10. 20 hanya disebutkan dalam kaitannya dengan menggabungkan dua angka romawi (dan menekankan bahwa IXX = 19 bukan pengurangan yang valid). Semoga itu jelas bagi Anda.
iamogbz

Jawaban:

1

Python 2, 415 444 440 419 416 byte

Lagipula tidak ada banyak angka Romawi. Script ini membuat semuanya dan memeriksa semua permutasi input, lalu mengembalikan kecocokan terkecil.

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
sumber
Itu jawaban yang bagus untuk tantangan seperti sekarang. Tetapi dalam percakapan komentar yang terhapus lebih awal, itu mengisyaratkan bahwa sistem (tidak nyata) ini berjalan setelah M = 1000, memiliki simbol untuk 5k, 10k dan seterusnya. Lihatlah contoh pertama di atas: {A = 10, I = 1, X = 5, ... Z = 1000000} ditentukan oleh interpretasi Anda
edc65
.., dan contoh terakhir, a = 5000 ...
edc65
Saya memperbaruinya untuk menangani semua kasus uji yang diberikan. Saya ragu pendekatan ini dapat diperpanjang 10.000 melewati karena dibutuhkan O (n!) Waktu pada jumlah angka Romawi.
Skyler
@ Skyler kasus uji tidak lengkap. Program harus menangani semua kemungkinan permutasi dari input yang valid yang dapat ditafsirkan sesuai dengan aturan angka romawi, dengan preferensi diberikan ke angka yang lebih rendah dalam kasus yang ambigu. Juga kode Anda tidak bisa menangani terakhir ujian Link
iamogbz
Tidak import itertools as idan kemudian i.permutationslebih pendek?
kucing