Tantangannya sederhana: menulis sebuah program atau fungsi yang, ketika diberi bilangan bulat non-negatif terbatas, menghasilkan array bersarang.
Aturan
- Kode Anda harus menghasilkan array bertingkat valid unik untuk setiap bilangan bulat 0 ≤ n <2 31 .
- Setiap kemungkinan array bersarang dengan hingga 16 tanda kurung terbuka harus dikeluarkan dalam kisaran ini. (Ini tidak berarti bahwa kode Anda tidak pernah dapat menghasilkan array bersarang dengan lebih dari 16 tanda kurung terbuka.)
- Kode Anda dapat menampilkan representasi string dari array bersarang alih-alih array yang sebenarnya (dengan atau tanpa koma).
Satu pemetaan yang mungkin:
0 -> []
1 -> [[]]
2 -> [[[]]]
3 -> [[], []]
4 -> [[[[]]]]
5 -> [[[], []]]
6 -> [[[]], []]
7 -> [[], [[]]]
8 -> [[], [], []]
9 -> [[[[[]]]]]
etc.
Mencetak gol
Ini adalah kode-golf , jadi kode terpendek dalam byte menang.
code-golf
array-manipulation
balanced-string
Produksi ETH
sumber
sumber
Jawaban:
Python 2.7,
172 149 124118 bytePenjelasan:
Tentukan sebuah bijection oleh
[
↔1
dan]
↔0
. Pengaturan kurung kemudian dapat ditulis sebagai angka biner dan sebaliknya, misalnya[][]
↔1010
(10) dan[[][]]
↔110100
(52). Semua pengaturan yang valid hingga 15 tanda kurung terbuka (total tanda kurung 30) dicakup oleh angka hingga 30 bit (mengabaikan angka nol di depan), yang jumlahnya tepatnya kurang dari 2 31 .For-loop pertama memberikan kebalikan dari bijection ini, mengubah angka menjadi susunan kurung, sambil memeriksa bahwa susunan itu valid.
Pengaturan yang tidak valid diganti dalam pernyataan cetak dengan urutan kurung yang panjang untuk menghindari tabrakan. Misalnya
11
(3) ↔[[
tidak valid sehingga kami menggabungkan 3 + 16 tanda kurung. Ini memastikan semua pengaturan unik.Pengaturan yang dihasilkan ditempatkan dalam sepasang tanda kurung untuk membuat array bersarang, sehingga
1010
(10) menjadi[[][]]
dan110100
(52) menjadi[[[][]]]
. Braket ekstra terbuka berarti kita sekarang telah menutupi semua array dengan 16 tanda kurung terbuka.Program berikut dapat digunakan untuk mencari tahu angka untuk array yang diberikan hingga 16 tanda kurung.
sumber
Python,
153128 byteKami memetakan nomor n ke daftar bersarang dengan melihat angka binernya dari kiri ke kanan. Algoritma ini berfungsi untuk angka apa pun, tidak hanya di bawah angka 2 32 .
[
.][
.][
.]
.Akhirnya, kami menutup tanda kurung yang terbuka.
sumber
Sendok , 63 byte (501 bit)
Ini adalah program brainfuck berikut yang dikonversi menjadi sendok:
Membaca bilangan bulat dalam biner pada stdin, dan menampilkan daftar bersarang di stdin. Membutuhkan 0 menjadi input sebagai string kosong (tanpa digit), dan membutuhkan juru bahasa brainfuck dengan sel 8-bit. Algoritma yang sama dengan jawaban Python saya.
Versi yang dapat dibaca:
sumber
Jelly , 28 byte
Ini mengulangi semua string karakter
[
dan]
yang dimulai dengan a[
dan diakhiri dengan a]
, memverifikasi apakah tanda kurung cocok, dan mencetak kecocokan ke- n .Cobalah online!
sumber
Perl,
8079 byteSekali lagi menggunakan algoritma orlp , tapi kali ini saya pertama kali memeriksa apakah itu berfungsi ...
Termasuk +1 untuk
-p
Berikan nomor input pada STDIN
nest.pl
:Solusi Linus adalah 64 byte dalam perl:
Solusi Dennis adalah 59 byte dalam perl (semakin lambat untuk jumlah besar):
sumber
-p
dihitung sebagai 1 byte tambahanPython 3,
120114 byteCobalah Ideone .
Bagaimana itu bekerja
Fungsi yang didefinisikan f mengambil input n dan menginisialisasi k ke 0 . Kami akan terus meningkatkan k hingga n + 1 nilai k menghasilkan output yang valid. Setiap kali kita menemukan nilai k , n akan dikurangi begitu mencapai -1 ,
~n
menghasilkan 0 , dan daftar r yang sesuai dengan nilai terakhir k dicetak.Pemetaan parsial dari bilangan bulat positif ke daftar bersarang (yaitu, k ↦ r ) harus bijective, tetapi tidak ada kendala lain. Yang digunakan dalam jawaban ini beroperasi sebagai berikut.
Konversikan k ke representasi string biner, menatap dengan 0b .
Misalnya, 44 ↦ "0b101100" .
Ganti semua 0 (titik kode 48 ) dalam representasi string dengan string "]," dan semua 1 (titik kode 49 ) dengan [ .
Misalnya, "0b101100" ↦ "], b [], [[],]," .
Hapus tiga karakter pertama (sesuai dengan "0b" ) dan karakter trailing (semoga koma).
Misalnya, "], b [], [[],]," ↦ "[], [[],]" .
Coba evaluasi kode yang dihasilkan. Jika ini menghasilkan kesalahan, k tidak dipetakan ke daftar mana pun.
Misalnya, "[], [[],]" ↦ ([], [[]]) .
Gabungkan hasilnya (jika ada) dengan daftar kosong. Jika ini menghasilkan kesalahan, k tidak dipetakan ke daftar mana pun.
Misalnya, ([], [[]]) + [] kesalahan karena + tidak dapat menggabungkan daftar dan tupel.
sumber
Haskell, 71 byte
Fungsi utama pada baris terakhir mengindeks ke dalam daftar semua array bersarang, diurutkan berdasarkan ukuran (jumlah tanda kurung terbuka). Jadi, semua array ukuran paling banyak 16 terdaftar terlebih dahulu.
Pertama mari kita lihat kode yang lebih bagus dan lebih pendek, tetapi typechecker Haskell menolak untuk menerima.
Fungsi
p
pada inputn
memberikan daftar semua ukuran array bersarangn
(kurung terbuka). Ini dilakukan secara rekursif. Setiap array tersebut terdiri dari beberapa kepalah
(anggota pertama) ukurank
dan beberapa ekort
(anggota lainnya) ukurann-k
, keduanya ukuran nol. Atau, ini adalah array kosong untuk ukurann==1
.Ekspresi
p=<<[1..]
kemudian diratakanp(1), p(2), ...
menjadi daftar tak terbatas tunggal dari semua array yang diurutkan berdasarkan ukurandan indeks fungsi utama ke dalamnya.
... Atau, itu akan, jika Haskell tidak mengeluh tentang "membangun tipe tak terbatas: t ~ [t]". Haskell tidak dapat mewakili daftar tanpa batas di atas yang elemen-elemennya adalah array bersarang secara sewenang-wenang. Semua elemennya harus memiliki tipe yang sama, tetapi tipe t tidak boleh sama dengan daftar t. Padahal, fungsinya
p
itu sendiri tidak dapat ditetapkan sebagai tipe yang konsisten tanpa pengetikan dependen, yang tidak dimiliki Haskell.Jadi, alih-alih kami bekerja pada deretan tanda kurung, mensimulasikan operasi kontra dengan akting
[
dan]
karakter. Ini membutuhkan tambahan 9 byte. Bahaya bermain golf dalam bahasa yang aman.sumber
Haskell,
8782 byteOutput elemen array. Contoh penggunaan:
(([0..]>>= \y->y#y)!!) 3
->"[][]"
.Function
#
membangun semua array bersarang sebagai string untuk tanda kurungn
buka danm
tutup, dengan melacak jumlah masing-masing array yang tersisa. Selalu dimulai dengann == m
. Fungsi utama memanggily # y
setiapy <- [0,1,...]
dan mengambil elemen pada indeks yang diberikan oleh input.sumber
MATL , 31 byte
Cobalah online! Atau verifikasi beberapa kasus uji pertama (butuh beberapa detik).
Pemetaan yang dihasilkan adalah:
Penjelasan
Kode terus menguji peningkatan angka biner, dengan digit
0
digantikan oleh-1
; yaitu, menggunakan1
dan-1
sebagai digit. Digit1
akan mewakili'['
dan-1
akan mewakili']'
.Program menghitung sampai n +1 angka yang valid telah diperoleh. Angka valid jika dua kondisi berikut berlaku:
1
dan-1
)1
digit selalu melebihi dari-1
) kecuali pada akhirnya (di mana nol dengan kondisi 1).Setelah n +1 angka yang valid telah diperoleh, yang terakhir ditransliterasikan dengan mengubah
1
ke[
dan-1
ke]
, dan kemudian ditampilkan.Kode:
sumber