Dalam teori himpunan, bilangan biasanya dikodekan sebagai set murni , yaitu set yang hanya berisi set kosong atau set lainnya yang murni. Namun, tidak semua set murni mewakili bilangan asli. Tantangan ini adalah tentang memutuskan apakah suatu set murni yang diberikan mewakili pengkodean bilangan alami atau tidak.
Pengkodean bilangan asli bekerja dengan cara berikut 1 :
- Nol adalah set kosong:
- Untuk angka :
Jadi, penyandian beberapa bilangan asli pertama adalah
Tugas
- Diberikan string yang mewakili himpunan murni, tentukan apakah himpunan ini mengkodekan angka alami sesuai dengan konstruksi di atas.
- Namun, perhatikan bahwa elemen-elemen set tidak dipesan, jadi bukan satu-satunya representasi yang valid dari seperti misalnya mewakili set yang sama.
- Anda dapat menggunakan
[]
,()
atau<>
bukannya{}
. - Anda dapat menganggap set diberikan tanpa
,
pemisah sebagai. - Anda dapat mengasumsikan tidak akan ada elemen duplikat dalam input, misalnya
{{},{}}
bukan input yang valid, dan bahwa input tersebut terbentuk dengan baik, misalnya tidak{{},
,{,{}}
atau serupa.
Uji Kasus
Benar:
{}
{{}}
{{},{{}}}
{{{}},{}}
{{},{{}},{{},{{}}}}
{{{},{{}}},{},{{}}}
{{{{}},{}},{{}},{}}
{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}
{{{{{}},{}},{{}},{}},{{}},{},{{},{{}}}}
{{},{{}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}},{{{}},{}},{{},{{}},{{},{{}}}}}
{{{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}}
Salah:
{{{}}}
{{{{}}}}
{{{{}},{}}}
{{},{{}},{{{}}}}
{{{},{{}}},{{}}}
{{{{{}}},{}},{{}},{}}
{{},{{}},{{},{{}}},{{},{{}},{{{}}}}}
{{{{{}},{}},{{{}}},{}},{{}},{},{{},{{}}}}
{{{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}}
Terkait: Konstruksi Alami (Keluaran pengodean himpunan angka alami yang diberikan.)
1 Lihat https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers
code-golf
decision-problem
set-theory
Laikoni
sumber
sumber
Jawaban:
JavaScript (Node.js) ,
534844 byteCobalah online! Kasus uji sebagian besar dicuri tanpa malu-malu dari jawaban @ Arnauld. Penjelasan: Jika suatu himpunan mewakili bilangan alami, maka bilangan alami yang diwakilinya harus sama dengan ukuran himpunan, dan (mengingat bahwa unsur-unsur dijamin berbeda), unsur-unsur harus merupakan representasi dari bilangan alami kurang dari itu, dan karenanya harus memiliki panjang yang lebih pendek. Ini sepele dari set kosong tentu saja. Sunting: Disimpan 5 byte berkat @Arnauld. Disimpan 4 byte berkat @Cowsquack.
sumber
!e[a.length-1]
harus menghemat 3 bytea[e.length]&&
selama 5 byte!g=(A,a=eval(A))=>a.every(e=>a[e.length]&&g(e))
akankah berhasil?Python 3 ,
695844 byte11 byte berkat Erik the Outgolfer.
14 byte terima kasih kepada Tn. Xcoder.
Cobalah online!
sumber
Bahasa Wolfram (Mathematica) ,
6059 byteCobalah online!
Inti dari solusi ini adalah fungsinya
yang mengubah daftar formulir
{0,1,2,...,n-1}
dalam urutan apa pun menjadi keluarann
(khususnya, dikonversi{}
ke0
), dan mengubah apa pun menjadi bilangan realE
.Panggil fungsi ini
f
. Diberikan input seperti"{{{}},{}}"
, kami melakukan hal berikut:f
di setiap level, dapatkanf[{f[{f[{}]}], f[{}]}]
.f
akan menghasilkan bilangan alami untuk input yang mewakilinya. Misalnya,f[{f[{f[{}]}], f[{}]}]
=f[{f[{0}], 0}]
=f[{1, 0}]
=2
. Yang lain akan menghasilkanE
.E
.sumber
Brachylog (v2), 9 byte
Cobalah online!
Seperti biasa untuk masalah keputusan , ini adalah program lengkap. Input dari input standar, menggunakan tanda kurung siku. Keluaran ke keluaran standar sebagai
true.
lawanfalse.
.Penjelasan
Meskipun saya katakan di atas bahwa ini adalah program lengkap, sebenarnya lebih menarik dari itu; itu baik program penuh dan fungsi. Ketika digunakan sebagai program lengkap, ia mencetak
true.
jika set adalah bilangan alami, ataufalse.
jika tidak. Ketika digunakan sebagai fungsi, ia "menormalkan" bilangan alami (yaitu menormalkan semua elemen dan mengurutkannya berdasarkan nilai; program ini menggunakan daftar secara internal, bukan set), atau "melempar pengecualian" (sebenarnya merupakan kegagalan, karena ini adalah Prolog) jika inputnya bukan bilangan asli.Perilaku program lengkap cukup mudah untuk dijelaskan: itu murni tersirat dalam perlakuan Brachylog terhadap program penuh yang tidak mengandung instruksi I / O. Perilaku yang dimaksud adalah "menjalankan fungsi, mengambil input dari input standar, dan menyatakan bahwa outputnya cocok dengan deskripsi yang diberikan oleh argumen baris perintah pertama; jika pernyataan gagal atau program melempar pengecualian, cetak
false.
, atau cetaktrue.
" . Dalam kasus ini, argumen baris perintah tidak ada (yaitu "apa pun berjalan"), sehingga perilaku pengecualian / tanpa pengecualian fungsi memberikan output.Adapun perilaku fungsi:
Bilangan alami didefinisikan sebagai mengandung dua bagian: unsur-unsur bilangan alami di bawah ini, disatukan dengan nomor itu sendiri. Dengan demikian, semua elemennya adalah bilangan asli. Kita dapat mengenali bilangan asli dengan a) memverifikasi bahwa semua elemennya adalah bilangan alami, b) memverifikasi bahwa elemen terbesar himpunan identik dengan himpunan tanpa elemen terbesarnya.
Ketika kita menggunakan daftar daripada set (dengan demikian tanda kurung siku), kita perlu menempatkannya dalam urutan yang konsisten agar perbandingan kesetaraan berfungsi (dalam hal ini, diurutkan berdasarkan "nilai"). Urutan sortir default Brachylog akan mengurutkan awalan daftar sebelum daftar itu sendiri, yang dengan mudah berarti bahwa ia akan mengurutkan angka alami dengan nilai numerik. Jadi kita bisa menyortir semua nomor kita secara rekursif untuk membuatnya menjadi urutan yang konsisten. Faktanya, melalui fungsi yang kita definisikan secara rekursif, kita dapat mencapai kedua hasil pada saat yang sama: menyortir elemen angka secara rekursif, dan memverifikasi bahwa itu adalah bilangan alami.
Dengan demikian fungsinya memiliki empat bagian utama.
↰ᵐ
adalah panggilan rekursif, memastikan bahwa setiap elemen adalah bilangan alami, dan mengubahnya setiap elemen menjadi bentuk normal.o
yang menormalkan angka itu sendiri (elemen-elemennya sudah dinormalisasi, jadi yang harus kita lakukan adalah mengurutkannya). Kemudian.t~k|
memastikan kita memiliki struktur yang kita inginkan dengan memeriksa bahwa elemen terbesar dan elemen lainnya sama. Daftar kosong (mis. 0) tidak memiliki elemen terakhir, sehingga akan mendapatkan kegagalan pernyataan dengant
; yang|Ė
menangani kasus ini, melalui memberi fallback eksplisit dalam kasus di mana daftar masukan kosong.sumber
K (ngn / k) ,
262427 byteCobalah online!
input adalah string json yang diuraikan oleh
`j@
(sintaks khusus untuk ngn / k){
}
adalah fungsi rekursif dengan argumenx
. itu mengembalikan nomor alami yang diwakili oleh setx
, atau null (0N
) jika tidak mewakili satu$[
;
;
]
adalah jika-maka-lagi. 0 adalah falsey, bilangan bulat lainnya benar!#x
bilangan bulat dari 0 (inklusif) hingga panjangx
(eksklusif)^
tanpao'x
rekursi (o
) pada setiap'
elemen ( ) darix
#
panjangnya^
adalah null?~
tidak@
bertindak sebagai kata kerja dummy terakhir sehingga~
dan^
dikomposisi dengan{
}
bukannya diterapkan padanyasumber
Jelly , 10 byte
Cobalah online!
sumber
Japt , 9 byte
Solusi JS Port of Neil . Harap pilih itu jika Anda membatalkan ini.
Cobalah atau jalankan semua test case
sumber
Merah , 81 byte
Cobalah online!
Mirip dengan jawaban Leaky Nun's Python 3
sumber
Jelly , 8 byte
Karena input harus berupa string, pengiriman ini hanya berlaku sebagai program lengkap.
Cobalah online! atau verifikasi semua kasus uji
Bagaimana itu bekerja
Ini menghasilkan representasi kanonik input, yang hanya terdiri dari array yang diurutkan.
sumber
Jelly , 7 byte
Ini adalah port jawaban Python Leaky Nun .
Karena input harus berupa string, pengiriman ini hanya berlaku sebagai program lengkap.
Cobalah online! atau verifikasi semua kasus uji
Bagaimana itu bekerja
sumber
Bahasa Wolfram (Mathematica) , 52 byte
Cobalah online!
sumber