Urutan lihat-dan-katakan: edisi angka romawi

20

Deskripsi tantangan

Kami memiliki beberapa tantangan yang melibatkan urutan Tampilan-dan-katakan . Pengingat cepat:

  • Urutan dimulai dengan 1,
  • Istilah selanjutnya dari urutan ini dihasilkan dengan menyebutkan setiap kelompok digit berulang dalam istilah sebelumnya,

Jadi beberapa istilah pertama adalah:

1        "one"
11       "one one" (we look at the previous term)
21       "two ones"
1211     "one two, one one"
111221   "one one, one two, two ones"
312211   "three ones, two twos, one one"

Sekarang mari kita lakukan hal yang sama, tetapi gunakan Angka Romawi sebagai gantinya. Kita mulai dengan Idan mengikuti aturan yang sama (alih-alih kita menerapkan aturan penghitungan angka pada karakter, jadi kita membaca IVXsebagai one one, one five, one tenganti one four, one tenatau dengan cara lain):

I           "one"
II          "one one"
III         "two ones" = "II" + "I"
IIII        "three ones" = "III" + "I"
IVI         "four ones" = "IV" + "I"
IIIVII      "one one, one five, one one"
IIIIIVIII   "three ones, one five, two ones" = ("III" + "I") + ("I" + "V") + ("II" + "I")

Diberikan bilangan bulat positif N, baik:

  • Keluarkan Nangka pertama dari urutan ini (juga pemisah yang masuk akal, juga["I", "II", "III", ...]
  • Keluarkan Nistilah th dari urutan ini (mungkin diindeks 0).

Ingatlah untuk membuat kode Anda sesingkat mungkin, karena ini adalah tantangan !

EDIT: Saya percaya bahwa selalu ada satu cara standar / disukai untuk mengekspresikan bilangan bulat sebagai angka romawi, (seperti 95-> XCValih-alih VC). Beberapa konverter angka Romawi yang saya temukan online menguatkan pendapat saya. Jika ragu, gunakan konverter online , karena mendaftar semua kasus tepi yang mungkin dan aturan khusus penulisan angka Romawi bukanlah titik tantangan ini.

EDIT2: @PeterTaylor dan @GregMartin menunjukkan bahwa hanya nomor kurang atau sama untuk 5muncul secara berurutan, sehingga Anda tidak perlu khawatir tentang ambiguitas angka Romawi (nomor 1- 8adalah I, II, III, IV, V, VI, VII, dan VIII)

shooqie
sumber
Tidak ada ekspresi angka Romawi yang unik untuk setiap bilangan bulat. Angka mana yang mungkin perlu diungkapkan, dan ekspresi mana dari angka-angka itu yang valid?
Peter Taylor
Apa yang Anda maksud dengan "tidak ada ekspresi angka Romawi yang unik untuk setiap bilangan bulat"? Suka 4/ IV/ IIII? Atau 95/ XCV/ VC? Mungkin tidak selalu ada cara unik untuk mengekspresikan bilangan bulat, tapi saya cukup yakin selalu ada yang lebih disukai (standar) - koreksi saya jika saya salah.
shooqie
1
seberapa jauh kita harus pergi dengan angka romawi kita?
Maltysen
Ya, kedua kasus itu. Dalam kasus kedua, saya pikir ini masalah pendapat yang lebih disukai.
Peter Taylor
9
@shooqie jika detail ini tidak diklarifikasi, bagaimana Anda membandingkan jawaban? Jika ada kasus tepi tertentu yang tersisa untuk interpretasi skor aktual menjadi tidak berarti karena mereka mungkin membuat perbedaan yang lebih besar daripada trik golf yang bisa Anda dapatkan.
Martin Ender

Jawaban:

17

Perl, 49 byte

Termasuk +1 untuk -p

Jalankan dengan indeks berbasis 0 pada STDIN, mis

ecce.pl <<< 14

ecce.pl:

#!/usr/bin/perl -p
s,(.)\1*,$&/$1%182 .$1,eg for($_=/$/)x$`;y;19;IV

Formula ajaib sangat ajaib.

Biasanya saya akan menggunakan ($_=//)x$'untuk membuat kontrol loop satu byte lebih pendek, tetapi penilaian di situs ini memberikan cacat 2 sehingga berakhir 1 byte lebih lama. Pada perl yang lebih lama, Anda dapat menjatuhkan ruang sebelumnya for. Beberapa versi perl memaksa Anda untuk menambahkan final ;untuk menutup transliterasi. Tetapi apa yang diberikan di atas adalah kode yang berfungsi pada sistem saya.

Penjelasan

Bekerja mundur dari solusi ke kode:

Transformasi string yang kita butuhkan:

I     -> II
II    -> III
III   -> IIII
IIII  -> IVI
IIIII -> VI

V     -> IV
VV    -> IIV

Setiap penggantian berakhir dengan karakter yang diulang. Saya akan mendapatkan urutan karakter yang sama menggunakan regex /(.)\1*/, jadi ini bisa dilakukan dengan menambahkan $1. Bagian sebelum ->di $&. Dengan itu saya masih membutuhkan:

I     -> I
II    -> II
III   -> III
IIII  -> IV
IIIII -> V

V     -> I
VV    -> II

Tulis Isebagai 1dan Vsebagai 9:

1     -> 1
11    -> 11
111   -> 111
1111  -> 19
11111 -> 9

9     -> 1
99    -> 11

Dengan membagi bagian sebelum ->dengan angka yang diulang ini menjadi:

1     -> 1
11    -> 11
111   -> 111
1111  -> 19
11111 -> 9

1     -> 1
11    -> 11

Jadi sekarang yang asli diulang Vbukan pengecualian lagi. Jadi saya ingin ekspresi yang membuat ini terjadi:

1     -> 1
11    -> 11
111   -> 111
1111  -> 19
11111 -> 9

Dan ini dapat dilakukan dengan modulo 182 sederhana:

1     % 182 = 1
11    % 182 = 11
111   % 182 = 111
1111  % 182 = 19
11111 % 182 = 9

(ini bahkan bisa IIIIIIke VIkanan meskipun tidak diperlukan di sini)

Yang tersisa adalah menginisialisasi variabel kerja untuk 1untuk indeks 0, ulangi transformasi ini dalam satu lingkaran dan pada akhirnya ganti 1dengan Idan 9olehV

1, 9dan 182merupakan satu-satunya kombinasi parameter yang digunakan rumus sederhana ini.

Ton Hospel
sumber
2
Ini jenius! :)
Lynn
10

Mathematica, 113 90 83 byte

Terima kasih kepada Martin Ender untuk saran yang mengurangi panjangnya lebih dari 25%!

Memamerkan perintah tingkat tinggi di Mathematica.

Nest[Flatten[Characters@{RomanNumeral@#,#2}&@@@Reverse@@@Tally/@Split@#]&,{"I"},#]&

Fungsi murni, mengambil argumen N dan mengeluarkan elemen ke-N dari urutan (diindeks 0) ini, sebagai daftar karakter. Sebarkan sedikit:

Nest[
  Flatten[
    Characters @ {RomanNumeral@#,#2}& @@@
      Reverse @@@ Tally /@ Split@ #
    ]& ,
  {"I"}, #]&

Bagian luar Nestmengulangi fungsi empat baris tengah, mulai dari {"I"}, N kali. Baris 4 membagi daftar karakter dari angka input Romawi ke dalam run karakter seperti, menghitung setiap run dengan Tally, dan menempatkan jumlah sebelum karakter yang mereka hitung. Baris 3 menjadikan penghitungan sebagai angka Romawi, lalu membagi angka Romawi tersebut ke dalam daftar karakter. The Flattenperintah mengurangi daftar-of-daftar keseluruhan untuk daftar satu dimensi.

Ini versi awalnya:

Nest[
  "" <> Flatten[{RomanNumeral@#[[1]], #[[2]]} & /@
    (Reverse@#[[1]] & /@ 
      Tally /@
        Split@Characters@#)] &,
  "I", #] &
Greg Martin
sumber
3
Grrr Mathematica;)
Beta Decay
Jika Anda menggunakan @@@alih-alih, /@Anda dapat menggunakan #dan #2bukannya #[[1]]dan #[[2]]. Selain itu, daftar karakter adalah tipe string yang dapat diterima, sehingga Anda dapat menggunakannya dan tidak menggunakannya Characters@.
Martin Ender
@ MartinEnder Aha, saya tahu pasti ada @@@jalan pintas seperti! Adapun daftar karakter yang menjadi tipe string yang dapat diterima (yang saya setuju akan mempersingkat kodenya): adakah posting di situs ini yang dapat Anda tunjukkan kepada saya yang menggambarkan standar komunitas?
Greg Martin
1
Beberapa penghematan lagi: Charactersutas secara otomatis sehingga Anda dapat menggunakan @, Reverse@#&tentu saja sama dengan polos Reverse, dalam hal ini Anda juga tidak memerlukan tanda kurung itu. Dan notasi awalan (dalam hal Flatten) tidak menyimpan apa pun jika Anda perlu menambahkan tanda kurung untuk membuatnya berfungsi. Menggabungkan semua itu:Nest[Flatten[Characters@{RomanNumeral@#,#2}&@@@Reverse@@@Tally/@Split@#]&,{"I"},#]&
Martin Ender
8

CJam ( 33 30 byte)

"I"{e`{(4md1$^'I*\'V*@}%e_}ri*

Demo online

Kunci kebenaran implementasi adalah teorema berikut:

Jika generasi pertama adalah I, tidak ada panjang run yang lebih besar dari lima

Lemma: jika generasi pertama adalah I, tidak ada string yang berisi VVV. Bukti adalah dengan kontradiksi. Misalkan ada indeks pertama nyang nberisi generasi th VVV. Jika itu VVVrusak karena (a)V VVkonversi dari generasi sebelumnya buruk: seharusnya (a+5)V. Jadi harus VV V(d), dan generasi sebelumnya terkandung VVVVV, bertentangan dengan pilihan n.

Sekarang, anggaplah ada indeks pertama myang mberisi generasi th ...IIIIII.... Perhatikan bahwa tidak boleh ada angka selain Idan Vdalam string, karena tidak ada generasi sebelumnya yang memiliki deretan sembilan Iatau sembilan V. Paling banyak empat dari Is berasal dari menjalankan Is di string sebelumnya, sehingga bagian yang sesuai dari string sebelumnya harus ...IIIVV...memberi ... IIII IIV .... Karena VVgenerasi in m-1tidak berasal dari VVVVV(lihat lemma), Vdigit kedua harus berupa run-length digit I, jadi dalam generasi yang m-1kita miliki ...IIIVVI.... Dan karena kita ingin inisial Imemberi IIIIdan tidak IVIatauVI, didahului oleh awal string atau oleh V.

Jika kita memiliki (...V)?IIIVVI...generasi m-1, apa yang kita miliki dalam generasi m-2? Kami sudah mengamati bahwa VVgen. m-1harus diurai sebagai (a)V V(I).

Misalkan kita mengambil a=2: (...V)?I IIV VI...Sebenarnya itu harus ...VI IIV VI..., meskipun pemimpin itu Vmungkin bagian dari IV; jadi pada generasi sebelumnya kita memiliki salah satu (...V)? IIII VV IIIII...atau (...V)? IIIII VV IIIII. Apa pun cara kita mengalami masalah dengan VVIIIII: yang kedua Vharus berupa run-length, tetapi kemudian ...VI IIII...membutuhkan pasangan (run-length, digit) berikut dengan digit yang sama.

Sehingga harus a=1: (...V)?II IV VI.... Karena generasi madalah yang pertama dengan rentang enam I, itu harus (...V)? II IV VI..., sehingga generasi m-2itu (...V)? I V IIIII.... ...VIVIIIII...tidak mungkin: namun kami memilih untuk menafsirkan yang kedua Vkami berakhir dengan dua pasangan (run-length, digit) berturut-turut dengan digit yang sama.

Oleh karena itu generasi m-2harus ^IVIIIII..., diuraikan sebagai ^IV IIII I(V)...atau ^IV III II(V).... Ini memberikan masing-masing generasi m-3sebagai ^V III V ...atau ^V II VV....

Tetapi jika kita melihat awal dari string yang dimulai dengan yang pertama dimulai V, kita mendapatkan sebuah siklus:

    VI IV I...
    IV III IV ...
    II IV IVI ...
    IIII IV II IV ...

dan karenanya tidak ada generasi yang memulai dengan salah satu VIIIVatau VIIVV. Kita harus menyimpulkan bahwa tidak ada yang seperti itu m.

Pembedahan

"I"          e# Initial generation
{            e# Loop...
  e`         e#   Run-length encode
  {          e#   Foreach [run-length char] pair...
    (        e#     Extract the run-length r
    4md1$^   e#     Get the number of Vs and the number of Is
             e#     The number of Vs is r/4 ; the number of Is is (r%4)^(r/4)
    'I*\'V*@ e#     Repeat strings the appropriate number of times and reorder
  }%
  e_         e#  Flatten to a simple string
}ri*         e# ... n times, where n is taken from stdin
Peter Taylor
sumber
6

Python 3, 195 byte

Ada banyak byte yang terbuang pada angka romawi, jadi ada kemungkinan golf dilakukan di sana.

Terima kasih kepada @ El'endiaStarman, @ Sherlock9 dan @Shooqie

import re
def f(x,r=""):
 for v,i in(5,"V"),(4,"IV"),(1,"I"):a,x=divmod(x,v);r+=i*a
 return r
s="I"
for i in[0]*int(input()):print(s);s=re.sub(r'(.)\1*',lambda m:f(len(m.group()))+m.group()[0],s)

Ide itu!

Peluruhan Beta
sumber
Anda dapat menghilangkan tanda kurung:for v,i in(5,"V"),(4,"IV"),(1,"I")
shooqie
@shooqie Saya tidak tahu Anda bisa melakukan itu: D
Beta Decay
for v,i in(5,"V"),(4,"IV"),(1,"I"):a,x=divmod(x,v);r+=i*amenghemat satu byte.
Sherlock9
@ βετѧΛєҫαγ: Juga, sepertinya Anda tidak menggunakan i(seperti pada for i in range(...)). Saya mencoba berkecimpung dengan exectetapi ini lolos 1dalam metode 'sub' tampaknya mengacaukan kode, saya belum dapat menemukan solusi.
shooqie
@shooqie Saya menyingkatnya sedikit dengan menyingkirkanrange
Beta Decay
4

R, 110 107 Bytes

as.romandikombinasikan dengan rlemembuatnya mudah. Pelingkupan pelecehan dan perilaku kucing <<-menghemat beberapa byte.

x="I"
replicate(scan(),{r=rle(strsplit(x,"")[[1]])
x<<-paste(rbind(paste(as.roman(r$l)),r$v),collapse="")})

Mengambil N dari konsol. Keluaran pertama dari 2 hingga N dalam hal urutan (yang saya yakin dalam spesifikasi ...)

 [1] "II"                                                                                                                                                                                                                                     
 [2] "III"                                                                                                                                                                                                                                    
 [3] "IIII"                                                                                                                                                                                                                                   
 [4] "IVI"                                                                                                                                                                                                                                    
 [5] "IIIVII"                                                                                                                                                                                                                                 
 [6] "IIIIIVIII"                                                                                                                                                                                                                              
 [7] "VIIVIIII"                                                                                                                                                                                                                               
 [8] "IVIIIIVIVI"                                                                                                                                                                                                                             
 [9] "IIIVIVIIVIIIVII"                                                                                                                                                                                                                        
[10] "IIIIIVIIIVIIIIVIIIIIVIII"                                                                                                                                                                                                               
[11] "VIIVIIIIIVIVIIVVIIVIIII"                                                                                                                                                                                                                
[12] "IVIIIIVVIIVIIIVIIIIIVIIIIVIVI"                                                                                                                                                                                                          
[13] "IIIVIVIIIVIIIIVIIIIIVVIIVIVIIVIIIVII"                                                                                                                                                                                                   
[14] "IIIIIVIIIVIIIIIVIVIIVVIIIVIIIIVIIIVIIIIVIIIIIVIII"                                                                                                                                                                                      
[15] "VIIVIIIIIVVIIVIIIVIIIIIVIIIIIVIVIIVIIIIIVIVIIVVIIVIIII"                                                                                                                                                                                 
[16] "IVIIIIVVIIIVIIIIVIIIIIVVIIVVIIVIIIVIIIIVVIIVIIIVIIIIIVIIIIVIVI"                                                                                                                                                                         
[17] "IIIVIVIIIVIIIIIVIVIIVVIIIVIIIIIVIIIIVIIIIIVIVIIIVIIIIVIIIIIVVIIVIVIIVIIIVII"                                                                                                                                                            
[18] "IIIIIVIIIVIIIIIVVIIVIIIVIIIIIVIIIIIVVIIVIVIIVVIIVIIIVIIIIIVIVIIVVIIIVIIIIVIIIVIIIIVIIIIIVIII"                                                                                                                                           
[19] "VIIVIIIIIVVIIIVIIIIVIIIIIVVIIVVIIIVIIIIVIIIVIIIIIVIIIIVIIIIIVVIIVIIIVIIIIIVIIIIIVIVIIVIIIIIVIVIIVVIIVIIII"                                                                                                                              
[20] "IVIIIIVVIIIVIIIIIVIVIIVVIIIVIIIIIVIIIIIVIVIIVIIIIIVVIIVIVIIVVIIIVIIIIVIIIIIVVIIVVIIVIIIVIIIIVVIIVIIIVIIIIIVIIIIVIVI"                                                                                                                    
[21] "IIIVIVIIIVIIIIIVVIIVIIIVIIIIIVIIIIIVVIIVVIIVIIIVIIIIVVIIIVIIIIVIIIVIIIIIVIIIIIVIVIIVVIIIVIIIIIVIIIIVIIIIIVIVIIIVIIIIVIIIIIVVIIVIVIIVIIIVII"                                                                                             
[22] "IIIIIVIIIVIIIIIVVIIIVIIIIVIIIIIVVIIVVIIIVIIIIIVIIIIVIIIIIVIVIIIVIIIIIVIVIIVIIIIIVVIIVVIIVIIIVIIIIIVIIIIIVVIIVIVIIVVIIVIIIVIIIIIVIVIIVVIIIVIIIIVIIIVIIIIVIIIIIVIII"                                                                      
[23] "VIIVIIIIIVVIIIVIIIIIVIVIIVVIIIVIIIIIVIIIIIVVIIVIVIIVVIIVIIIVIIIIIVVIIVIIIVIIIIVVIIIVIIIIIVIIIIVIIIIIVVIIVVIIIVIIIIVIIIVIIIIIVIIIIVIIIIIVVIIVIIIVIIIIIVIIIIIVIVIIVIIIIIVIVIIVVIIVIIII"                                                   
[24] "IVIIIIVVIIIVIIIIIVVIIVIIIVIIIIIVIIIIIVVIIVVIIIVIIIIVIIIVIIIIIVIIIIVIIIIIVVIIIVIIIIVIIIIIVIVIIIVIIIIIVVIIVIVIIVVIIIVIIIIIVIIIIIVIVIIVIIIIIVVIIVIVIIVVIIIVIIIIVIIIIIVVIIVVIIVIIIVIIIIVVIIVIIIVIIIIIVIIIIVIVI"                             
[25] "IIIVIVIIIVIIIIIVVIIIVIIIIVIIIIIVVIIVVIIIVIIIIIVIIIIIVIVIIVIIIIIVVIIVIVIIVVIIIVIIIIIVIVIIVVIIVIIIVIIIIIVVIIIVIIIIVIIIVIIIIIVIIIIIVVIIVVIIVIIIVIIIIVVIIIVIIIIVIIIVIIIIIVIIIIIVIVIIVVIIIVIIIIIVIIIIVIIIIIVIVIIIVIIIIVIIIIIVVIIVIVIIVIIIVII"
Vlo
sumber
1

JavaScript (ES6), 107

Fungsi rekursif mengembalikan istilah N 0 berdasarkan

f=(n,r='I')=>n?f(n-1,r.match(/I+|V+/g).map(x=>((n=x.length)-4?'VIII'.slice(n<5,1+n%5):'IV')+x[0]).join``):r

Uji

f=(n,r='I')=>n?f(n-1,r.match(/I+|V+/g).map(x=>((n=x.length)-4?'VIII'.slice(n<5,1+n%5):'IV')+x[0]).join``):r

function update() {
  O.textContent=f(I.value)
}

update()
<input id=I value=25 type=number oninput='update()'><pre id=O></pre>

edc65
sumber
1

Perl 6 , 62 byte

{("I",{S:g/(.)$0*/{<I II III IV V>[$/.chars-1]~$0}/}...*)[$_]}

Fungsi anonim yang menerima indeks berbasis nol.

Menggunakan fakta bahwa angka romawi lebih tinggi dari 5 tidak diperlukan, karena satu-satunya kelompok angka berulang yang dapat terjadi, adalah:

I     -> II
II    -> III
III   -> IIII
IIII  -> IVI
IIIII -> VI

V     -> IV
VV    -> IIV

( coba online )

seseorang
sumber