Kapan di Roma, Hitung seperti orang Romawi?

20

Latar Belakang

Tantangan ini terinspirasi oleh situs web ini , yang menerbitkan diagram berikut:

masukkan deskripsi gambar di sini

Diagram ini menunjukkan kepada kita bahwa ekspresi Angka Romawi terpanjang di bawah 250 adalah ekspresi 188, yang membutuhkan 9 angka untuk diekspresikan.

Tantangan

Simbol standar yang digunakan untuk mengekspresikan Angka paling Romawi adalah sebagai berikut: { I, V, X, L, C, D, M}, di mana nilai-nilai numerik karakter yang M= 1000, D= 500, C= 100, L= 50, X= 10, V= 5, I= 1.

Dalam tantangan ini, tujuan Anda adalah, diberi bilangan bulat positif n , menghitung jumlah representasi Angka Romawi yang valid yang dapat dikomposisikan melalui n gabungan simbol-simbol standar.

Kemudian, program Anda harus menampilkan hasil perhitungan ini!

Input : Bilangan bulat positif n .

Output : Jumlah panjang angka romawi yang valid n .

Aturan untuk Ekspresi Angka Romawi

Angka Romawi pada awalnya hanya memiliki pasangan "aditif", artinya angka selalu ditulis dalam urutan menurun, dan jumlah nilai semua angka adalah nilai angka.

Kemudian, pasangan subtraktif, penggunaan menempatkan angka yang lebih kecil di depan yang lebih besar untuk mengurangi yang lebih kecil dari yang lebih besar, menjadi hal biasa untuk mempersingkat ekspresi Angka Romawi. Pasang subtraktif tidak dapat dirantai, seperti dalam ekspresi tidak valid berikut: IXL.

Berikut ini adalah aturan modern untuk pasangan aditif dan subtraktif.

  1. Hanya satu I, X, dan C yang dapat digunakan sebagai angka utama dalam bagian dari pasangan yang mengurangi.
  2. Saya hanya bisa ditempatkan sebelum V atau X dalam pasangan subtraktif.
  3. X hanya dapat ditempatkan sebelum L atau C dalam pasangan subtraktif.
  4. C hanya dapat ditempatkan sebelum D atau M dalam pasangan subtraktif.
  5. Selain pasangan subtraktif, angka harus dalam urutan menurun (artinya jika Anda menjatuhkan angka terkemuka dari setiap pasangan subtraktif, maka angka akan berada dalam urutan menurun).
  6. M, C, dan X tidak dapat disamakan atau dilampaui oleh denominasi yang lebih kecil.
  7. D, L, dan V masing-masing hanya dapat muncul sekali.
  8. Hanya M yang dapat diulang 4 kali atau lebih.

Catatan selanjutnya

  • Kami tidak akan menggunakan notasi bar ; alih-alih, kami hanya akan menambahkan lebih banyak M untuk mengekspresikan angka apa pun.

  • Ini adalah satu - satunya aturan yang akan kami ikuti untuk angka romawi kami. Itu berarti bahwa ekspresi aneh, seperti IVI, juga akan dianggap valid dalam sistem kami.

  • Juga ingat bahwa kami tidak menghitung jumlah angka yang memiliki panjang ekspresi n , karena beberapa angka memiliki banyak ekspresi. Sebagai gantinya, kami hanya menghitung jumlah ekspresi yang valid.

Uji Kasus

17

231

3105

Saya memeriksa di atas dengan tangan, jadi pastikan untuk memeriksa kembali kasus uji, dan menambahkan lebih banyak jika Anda bisa!

Kriteria Menang

Ini adalah tantangan , jadi bersenang-senanglah! Saya hanya akan menerima solusi yang dapat menangani setidaknya input dari 1 hingga 9. Lagi adalah bonus!

Edit

Seperti yang diminta oleh komentator, temukan di bawah ini, atau di tautan pastebin ini, 105 kombo yang saya hitung untuk n = 3

III IVI IXI IXV IXX VII XII XIV XIX XVI XXI XXV XXX XLI XLV XLX XCI XCV XCX XCL XCC LII LIV LIX LVI LXI LXV CII CIV CIX CVI CXI CXV CXX CXL CXC CLI CLV CLX CLX CLI CLV CLI CLV CLI CLV CLI CLV CMI CMV CMX CML CMC CMD CMM DII DIV DIX DVI DXI DXV DXX DXXL DLL DLI DLV DLX DCI DCV DCL DCL DCL DCC MII MIV MIX MVI MXI MXI MXI MXI MXI MXI MXI MXI MXI MXI MCV MCX MCX MCB MCB MC MD MD MD MD MD MMX MML MMC MMD MMM

Edit 2:

Gunakan kode non-golf berikut ini , milik Jonathan Allan untuk memeriksa hasil Anda.

Edit 3:

Saya minta maaf atas semua kesalahan dalam tantangan ini. Saya akan memastikan untuk melakukan pekerjaan yang lebih baik lain kali!

Don Thousand
sumber
Komentar bukan untuk diskusi panjang; percakapan ini telah dipindahkan ke obrolan .
Mego

Jawaban:

3

Retina , 111 byte

~(`.+
*$(CM)CDXCXCXCXLIXIXIXIVII
.(.)
.+¶$$&$¶$$&$1$¶$$&$&¶L`.{0,$+}\b¶D`¶
¶$
¶.+¶$$&$¶$$&I¶L`[A-Z]{$+}\b¶D`¶.+

Cobalah online! Ini adalah penulisan ulang yang lengkap karena saya salah memahami aturan 1. yang berarti bahwa Anda hanya dapat menggunakan satu dari masing-masing subtraktif I, Xdan C. Penjelasan: Bagian pertama dari skrip memperluas input menjadi serangkaian CMpasangan diikuti oleh pasangan subtraktif yang mungkin lainnya. Setiap pasangan adalah opsional, dan karakter pertama dari setiap pasangan juga opsional dalam pasangan tersebut. Tahap ketiga kemudian memperluas daftar pasangan menjadi daftar perintah Retina yang mengambil input dan membuat tiga salinan dengan opsi karakter kedua atau kedua dari pasangan, kemudian memotong dan menduplikasi hasil. Tahap akhir kemudian menambahkan kode untuk melakukan tugas akhir: pertama untuk memperluas input untuk mungkin menambahkan finalI, lalu untuk memfilter hasil dengan panjang yang salah, lalu untuk menduplikasi hasil, dan akhirnya menghitung hasilnya. Script Retina yang dihasilkan kemudian dievaluasi.

Catatan: Secara teori 15 byte dapat disimpan dari akhir baris ke-4 tetapi ini membuat skrip terlalu lambat untuk ditunjukkan pada TIO bahkan untuk n=1.

Neil
sumber
@ Jonathan Allan Ah, maka Anda termasuk beberapa pasangan kurang menarik dengan angka utama yang sama, yang salah.
Neil
2
@JonathanAllan Menulis ulang baru, secara kebetulan untuk jumlah byte yang sama persis!
Neil
5

Python 2 , 177 168 162 byte

import re,itertools as q
f=lambda n:sum(None!=re.match("^M*(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})$",(''.join(m)))for m in q.product('MDCLXVI',repeat=n))

Cobalah online!

Saya cukup baru, bantu saya bermain golf ini! Ini memeriksa angka romawi yang sebenarnya, regex perlu disesuaikan untuk memperhitungkan kasus aneh sepertiIVI

-9 byte berkat @Dead Possum!

-6 byte terima kasih kepada @ovs

Easton Bornemeier
sumber
Ya saya pikir kasus n = 3 mungkin salah dalam contoh. Saya awalnya mendapatkan 93 dengan^M*(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})$
Easton Bornemeier
171 byte
Dead Possum
1
@ Jonathan Allan Saya menghabiskan sekitar dua hari bertanya-tanya tentang stackexchange Math mencoba memastikan aturan ini masuk akal. Kira saya tidak cukup melakukan :(
Don Thousand
1
@RushabhMehta Ini adalah tantangan yang diformat dengan sangat baik dan menyenangkan untuk diprogram, jangan merasa buruk tentang nuansa malang dalam seluk-beluk definisi angka romawi. Ini adalah tantangan Anda, tentukan sesuai keinginan Anda. itu bisa diterapkan dalam arti lain, hanya lebih sulit
Easton Bornemeier
1
Ini sepertinya tidak memberikan jawaban yang tepat untuk 3. 93alih-alih105
Jo King
3

JavaScript (ES7), 133 byte

Sunting : Diperbaiki untuk mencocokkan hasil yang dikembalikan oleh kode Jonathan Allan , yang diberikan sebagai implementasi referensi oleh OP.


n=>[...Array(m=k=7**n)].reduce(s=>s+/^1*5?4{0,3}3?2{0,3}6?0{0,3}$/.test((--k+m).toString(7).replace(/0[62]|2[34]|4[51]/g,s=>s[1])),0)

Cobalah online!

Bagaimana?

N1 :

[...Array(m = k = 7 ** n)].reduce(s => … (--k + m).toString(7) …, 0)

Mulai sekarang, setiap digit akan ditafsirkan sebagai simbol angka Romawi:

0I,1M,2X,3L,4C,5D,6V

2) Kami mengganti semua pasangan subtraktif valid bentuk ABdenganB :

.replace(/0[62]|2[34]|4[51]/g, s => s[1]))  // in the code
.replace(/I[VX]|X[LC]|C[DM]/g, s => s[1]))  // with Roman symbols

Contoh:

  • XLIXIV menjadi LXV
  • XIIVmenjadi XIV, meninggalkan Iyang akan membuat tes berikutnya gagal
  • ICtetap tidak berubah, yang juga membuat tidak valid Idi tempat

3) Kami memeriksa bahwa simbol yang tersisa berada dalam urutan yang benar dan tidak muncul lebih dari yang diizinkan:

/^1*5?4{0,3}3?2{0,3}6?0{0,3}$/.test(…)  // in the code
/^M*D?C{0,3}L?X{0,3}V?I{0,3}$/.test(…)  // with Roman symbols
Arnauld
sumber
Astaga, saya tidak berharap ini dilakukan dalam waktu kurang dari 200 byte dalam bahasa non-esoterik! Pikiran menjelaskan bagaimana ini bekerja?
Don Thousand
Namun, saya perhatikan bahwa ini tidak bekerja untuk * n *> 4 di TIO, yang agak disayangkan.
Don Thousand
@RushabhMehta Saya telah menambahkan versi non-rekursif untuk menguji nilai yang lebih tinggi. Saya akan menambahkan penjelasan ketika saya selesai bermain golf ini.
Arnauld
0

C, 150 123 byte

Saya tidak cukup membaca deskripsi, jadi ini menghasilkan angka angka Romawi standar (di mana ekspresi seperti IVItidak dihitung). Karena saya berusaha keras untuk itu, saya pikir saya akan tetap berbagi.

#define F(X) for(X=10;X--;)
x[]={0,1,2,3,2,1,2,3,4,2};f(i,o,a,b,c){for(i++;i--;)F(a)F(b)F(c)o+=i==x[a]+x[b]+x[c];return o;}

Asli (150 byte):

#define F(X) for(X=10;X--;)
i,o,a,b,c,x[]={0,1,2,3,2,1,2,3,4,2};main(){scanf("%i",&i);for(i++;i--;)F(a)F(b)F(c)o+=i==x[a]+x[b]+x[c];printf("%i\n",o);}
Curtis Bechtel
sumber
1
Anda hanya diperbolehkan memposting kiriman yang valid.
Okx
@CurtisBechtel Anda dapat menyimpan solusinya di sini saya kira, tetapi saya akan mencoba memodifikasinya untuk memenuhi aturan tantangan.
Don Thousand
1
Saya pikir Anda dapat menghapus ruang antara F(X)danfor(X=10;X--;)
Zacharý