"Skema sajak" adalah serangkaian huruf a
untuk z
, sehingga kemunculan karakter pertama dalam urutan menaik (tanpa celah), dimulai dari a
. Misalnya (dengan kejadian pertama ditandai):
abccdbebdcfa
^^^ ^ ^ ^
Jumlah skema sajak panjang N
diberikan oleh nomor Bell B(N)
. ( OEIS A000110 )
Tantangan
Tugas Anda adalah mengimplementasikan enumerasi skema sajak ini, yaitu pemetaan bijective dari integer ke skema sajak. Anda diberi bilangan bulat positif N <= 26
, dan juga bilangan bulat non-negatif 0 <= i < B(N)
. Atau, Anda dapat menggunakan rentang 1 <= i <= B(N)
. Anda harus menampilkan skema sajak panjang N
, sehingga setiap i
menghasilkan string yang berbeda.
Anda dapat menulis sebuah program atau fungsi, mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi dan mengeluarkan hasilnya melalui STDOUT (atau alternatif terdekat), nilai pengembalian fungsi atau parameter function (out).
Anda dapat menggunakan huruf besar atau kecil (secara konsisten).
Kode Anda harus dapat menangani input yang valid dalam jumlah waktu yang wajar (mis. Tidak lebih dari beberapa jam untuk N = 26
, kasus terburuk i
). Ini harus memungkinkan solusi berskala eksponensial dengan N
(untuk pangkalan kecil), bahkan dalam bahasa yang lambat tetapi melarang solusi yang berskala linier dengan i
(yaitu B(N)
). Secara khusus, itu berarti Anda tidak bisa hanya mengulangi semua skema panjang sajak yang valid N
sampai Anda membuang i
skema.
Aturan standar kode-golf berlaku.
Contohnya
Penugasan yang tepat i
untuk skema to (yaitu urutan skema untuk suatu yang diberikan N
) terserah Anda. Tetapi katakanlah Anda memilih pemesanan leksikografis, solusi Anda harus sesuai dengan tabel berikut (dengan -
menunjukkan input yang tidak valid):
N\i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 a - - - - - - - - - - - - - -
2 aa ab - - - - - - - - - - - - -
3 aaa aab aba abb abc - - - - - - - - - -
4 aaaa aaab aaba aabb aabc abaa abab abac abba abbb abbc abca abcb abcc abcd
Berikut ini adalah skrip CJam pendek yang menghasilkan semua skema sajak yang valid untuk jangka waktu tertentu (tetapi jangan mencoba lebih dari 10 atau Anda akan menunggu beberapa saat).
Tantangan Terkait
sumber
N
), asalkan tidak berubah menjadi cukup sepele dan saya terlalu bodoh untuk menemukannya.Jawaban:
CJam,
6866 byteCobalah online.
Ini adalah program CJam pertama saya. Ini mulai hidup sebagai port solusi Perl saya dan awalnya lebih dari 130 byte. Saran golf lebih lanjut dipersilakan.
Seperti halnya program Perl saya, program ini ada dalam dua bagian.
Untuk debug array yang dibuat oleh Bagian 1 add
]_`o~
antara Bagian 1 & 2. Jika n adalah5
, array akan terlihat seperti ini:[[1 1 1 1 1 1] [1 2 3 4 5] [2 5 10 17] [5 15 37] [15 52]]
. Indeks 0 dari setiap array tidak digunakan, mereka hanya membuatnya lebih mudah dengan tidak harus menghitung offset. Array dihitung seperti ini:Itu menyimpan salinan dari array yang lama sambil menghitung yang berikutnya. Array dibaca dan dibuang dalam urutan terbalik oleh Bagian 2.
sumber
Python 2, 153
Ini menggunakan urutan abjad dan pengindeksan berbasis 0.
Biarkan
l
menunjukkan panjang akhiran huruf dana
menunjukkan jumlah huruf berbeda yang digunakan di bagian sebelumnya. Kemudian fungsip(l,a)
yang menghitung jumlah cara untuk memilih huruf yang tersisa bisa menjadi 40 byte:Namun, ini terlalu lambat untuk tantangan, jadi alih-alih nilai-nilai yang diperlukan dihitung sebelumnya dan disimpan dalam
u
array. Pada setiap tahap perhitungan, jika huruf berikutnya adalah salah satu yanga
sudah digunakan, n = k * p (l - 1, a) + n 'di mana k adalah huruf 0 yang diindeks dari alfabet dan n' adalah nilain
untuk panggilan fungsi berikutnya, yang berisi informasi tentang surat-surat yang tersisa. Jika huruf baru digunakan, maka n = a * p (l - 1, a) + n ' .sumber
Haskell (GHC 7.10), 150 byte
Operator
n # i
menghitungi
skema panjang sajak th (zero-indexed)n
. Ini berjalan dalam operasi O (n²) (bilangan bulat besar), mengambil keuntungan dari daftar malas tak terbatas Haskell untuk memoisasi otomatis. Sampel berjalan:(Jika maksimum N adalah 25 bukannya 26,
.fromEnum
bisa dihapus, karena B (25) cocok dalam 64-bitInt
.)sumber
Perl 257 + 1 (-p flag) = 258Perl 182 + 10 (flag -pMbignum) = 192
Terima kasih kepada dev-nul karena telah menghemat banyak byte! Saya sekarang telah menulis ulang berdasarkan apa yang saya pelajari dari melakukan versi CJam.
Menghitung sajak dalam urutan abjad naik, 0 diindeks.
Dua bagian: Bagian 1 adalah
12890 byte dan menghitung matriks untuk Bagian 2. Bagian 2 adalah12992 byte dan melakukan beberapa matematika sederhana untuk menghitung setiap huruf.Jika saya bisa menyingkirkan matriks dan menggantinya dengan dua angka sederhana, saya bisa menghitung jalur tunggal melalui matriks untuk setiap angka dan menyimpan banyak byte!Tampaknya, gagasan itu tidak berhasil!Sayangnya, itu tidak menghasilkan rima yang tepat untuk nilai yangi
lebih tinggi dari 9007199254740992, tetapi bekerja dengan indah untuk nilai yang rendah!Saya telah menambahkan perpustakaan Bignum dengan biaya 11 byte.Dijalankan dari baris perintah denganperl -pMbignum bell-rhyme.pl
.-pMbignum
= 10 byte. Ini juga sangat cepat untuk nilai input apa pun.sumber
Oracle SQL 11.2,
412284283 byteSayangnya hanya berjalan hingga panjang 8. Nilai hasil yang lebih besar di: ORA-01489: hasil penggabungan string terlalu panjang
Tidak bermain golf
Tampilan menghasilkan: huruf i pada kolom a dan nilainya dalam b.
Tampilan rekursif v mengambil string yang dibangun sebagai parameter v, nilai huruf terakhir yang digunakan dalam c dan nilai huruf terbesar yang digunakan dalam n. Parameter n sama dengan panjang string tanpa huruf duplikat, itulah gunanya regex.
Sebuah huruf valid jika nilainya <= nilai huruf terbesar yang sudah digunakan atau huruf berikutnya yang digunakan.
Entah bagaimana permintaan membutuhkan PANJANG (s) <: n bagian untuk dijalankan, saya harus kehilangan sesuatu dalam cara kerja kueri.
SELECT utama menangani penyaringan input yang tidak valid dan string yang lebih pendek dibangun sebelum panjang yang ditargetkan tercapai.
Versi 412 byte
Jangan coba kueri 412 byte dengan 26. Ini menempatkan database dalam mode terbatas, setidaknya pada versi xe saya berjalan dalam wadah buruh pelabuhan di macbook. Saya bisa mencoba exadata di tempat kerja, tetapi sayangnya saya masih perlu bekerja untuk mencari nafkah.
sumber
Mathematica, 136 byte
Untuk kelengkapan, berikut adalah implementasi referensi golf saya. Berbeda dengan jawaban yang ada ini tidak berjalan dalam waktu polinomial (itu eksponensial
N
dengan basis 2) tetapi memenuhi batasan waktu (kasus terburuk masih berjalan di bawah setengah jam).Idenya adalah ini:
Untuk setiap skema sajak kita dapat mengidentifikasi posisi di mana karakter maksimum sejauh ini meningkat:
Kita dapat memperlakukan tanda-tanda itu sebagai angka biner yang membuatnya mudah untuk diulangi pada semua struktur tersebut. Kita perlu beralih dari 2 n-1 ke 2 n (atau sebaliknya) dari mana kompleksitas waktu eksponensial berasal.
i
, kita kurangi darii
. Kalau tidak, kami telah menemukan struktur skema sajak yang diminta.i
(atau apa yang tersisa dari itu) sebagai angka basa campuran, di mana bobot digit ditentukan oleh jumlah karakter yang diperbolehkan di posisi yang tersisa.Saya bertanya-tanya apakah ini akan memungkinkan solusi yang lebih pendek dalam beberapa bahasa lain yang diajukan karena tidak memerlukan memoisasi atau perhitungan.
sumber