Angka Catalan ( OEIS ) adalah urutan bilangan alami yang sering muncul dalam kombinatorik.
Angka Catalan ke-n adalah jumlah kata-kata Dyck (string kurung kurung atau kurung seimbang seperti [[][]]
; secara resmi didefinisikan sebagai string menggunakan dua karakter a dan b sehingga setiap substring mulai dari awal memiliki jumlah karakter lebih besar atau sama dengan angka dari b karakter, dan seluruh string memiliki jumlah a dan b karakter yang sama) dengan panjang 2n. Angka Catalan ke-n (untuk n> = 0) juga secara eksplisit didefinisikan sebagai:
Mulai dari n = 0, 20 angka Catalan pertama adalah:
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190...
Tantangan
Tulis program atau fungsi lengkap yang mengambil bilangan bulat n-negatif melalui STDIN atau alternatif yang dapat diterima, dan menampilkan angka Catalan ke-n. Program Anda harus bekerja minimal untuk input 0-19.
I / O
Memasukkan
Program Anda harus mengambil input dari STDIN, argumen fungsi atau salah satu alternatif yang dapat diterima per pos meta ini. Anda dapat membaca nomor yang dimasukkan sebagai representasi desimal standar, representasi unary, atau byte.
- Jika (dan hanya jika) bahasa Anda tidak dapat mengambil input dari STDIN atau alternatif lain yang dapat diterima, itu mungkin mengambil input dari variabel hardcoded atau setara yang sesuai dalam program.
Keluaran
Program Anda harus menampilkan nomor Catalan ke STDOUT, hasil fungsi atau salah satu alternatif yang dapat diterima per pos meta ini. Anda dapat menampilkan nomor Catalan dalam representasi desimal standar, representasi unary, atau byte.
Output harus terdiri dari angka Catalan yang sesuai, secara opsional diikuti oleh satu atau lebih baris baru. Tidak ada output lain yang dapat dihasilkan, kecuali output konstan dari juru bahasa Anda yang tidak dapat ditekan (seperti salam, kode warna ANSI atau lekukan).
Ini bukan tentang menemukan bahasa yang terpendek. Ini tentang menemukan program terpendek dalam setiap bahasa. Karena itu, saya tidak akan menerima jawaban.
Dalam tantangan ini, bahasa yang lebih baru daripada tantangan dapat diterima selama mereka memiliki implementasi. Diperbolehkan (dan bahkan dianjurkan) untuk menulis sendiri penerjemah ini untuk bahasa yang sebelumnya tidak diterapkan. Selain itu, semua aturan standar kode-golf harus dipatuhi. Kiriman dalam kebanyakan bahasa akan dinilai dalam byte dalam pengkodean yang sudah ada sebelumnya (biasanya UTF-8). Perhatikan juga bahwa built-in untuk menghitung angka Catalan ke-n diizinkan.
Katalog
Cuplikan Stack di bagian bawah posting ini menghasilkan katalog dari jawaban a) sebagai daftar solusi terpendek per bahasa dan b) sebagai leaderboard keseluruhan.
Untuk memastikan bahwa jawaban Anda muncul, silakan mulai jawaban Anda dengan tajuk utama, menggunakan templat Penurunan harga berikut:
## Language Name, N bytes
di mana N
ukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda dapat menyimpan skor lama di headline, dengan mencoretnya. Contohnya:
## Ruby, <s>104</s> <s>101</s> 96 bytes
Jika Anda ingin memasukkan beberapa angka dalam tajuk Anda (mis. Karena skor Anda adalah jumlah dari dua file atau Anda ingin membuat daftar hukuman penterjemah secara terpisah), pastikan bahwa skor sebenarnya adalah angka terakhir di tajuk:
## Perl, 43 + 2 (-p flag) = 45 bytes
Anda juga dapat membuat nama bahasa menjadi tautan yang kemudian akan muncul di cuplikan:
## [><>](http://esolangs.org/wiki/Fish), 121 bytes
<style>body { text-align: left !important} #answer-list { padding: 10px; width: 290px; float: left; } #language-list { padding: 10px; width: 290px; float: left; } table thead { font-weight: bold; } table td { padding: 5px; }</style><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table><script>var QUESTION_ID = 66127; var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe"; var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk"; var OVERRIDE_USER = 12012; var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page; function answersUrl(index) { return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER; } function commentUrl(index, answers) { return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER; } function getAnswers() { jQuery.ajax({ url: answersUrl(answer_page++), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { answers.push.apply(answers, data.items); answers_hash = []; answer_ids = []; data.items.forEach(function(a) { a.comments = []; var id = +a.share_link.match(/\d+/); answer_ids.push(id); answers_hash[id] = a; }); if (!data.has_more) more_answers = false; comment_page = 1; getComments(); } }); } function getComments() { jQuery.ajax({ url: commentUrl(comment_page++, answer_ids), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { data.items.forEach(function(c) { if (c.owner.user_id === OVERRIDE_USER) answers_hash[c.post_id].comments.push(c); }); if (data.has_more) getComments(); else if (more_answers) getAnswers(); else process(); } }); } getAnswers(); var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/; var OVERRIDE_REG = /^Override\s*header:\s*/i; function getAuthorName(a) { return a.owner.display_name; } function process() { var valid = []; answers.forEach(function(a) { var body = a.body; a.comments.forEach(function(c) { if(OVERRIDE_REG.test(c.body)) body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>'; }); var match = body.match(SCORE_REG); if (match) valid.push({ user: getAuthorName(a), size: +match[2], language: match[1], link: a.share_link, }); else console.log(body); }); valid.sort(function (a, b) { var aB = a.size, bB = b.size; return aB - bB }); var languages = {}; var place = 1; var lastSize = null; var lastPlace = 1; valid.forEach(function (a) { if (a.size != lastSize) lastPlace = place; lastSize = a.size; ++place; var answer = jQuery("#answer-template").html(); answer = answer.replace("{{PLACE}}", lastPlace + ".") .replace("{{NAME}}", a.user) .replace("{{LANGUAGE}}", a.language) .replace("{{SIZE}}", a.size) .replace("{{LINK}}", a.link); answer = jQuery(answer); jQuery("#answers").append(answer); var lang = a.language; lang = jQuery('<a>'+lang+'</a>').text(); languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang.toLowerCase(), user: a.user, size: a.size, link: a.link}; }); var langs = []; for (var lang in languages) if (languages.hasOwnProperty(lang)) langs.push(languages[lang]); langs.sort(function (a, b) { if (a.lang_raw > b.lang_raw) return 1; if (a.lang_raw < b.lang_raw) return -1; return 0; }); for (var i = 0; i < langs.length; ++i) { var language = jQuery("#language-template").html(); var lang = langs[i]; language = language.replace("{{LANGUAGE}}", lang.lang) .replace("{{NAME}}", lang.user) .replace("{{SIZE}}", lang.size) .replace("{{LINK}}", lang.link); language = jQuery(language); jQuery("#languages").append(language); } }</script>
Jawaban:
C,
7852393433 byteLebih banyak keajaiban C (terima kasih xsot):
?:
adalah ekstensi GNU .Kali ini dengan memperluas perulangan di bawah ini (terima kasih xnor dan Thomas Kwa):
-(n+1)
digantikan oleh~n
, yang setara dalam komplemen dua dan menyimpan 4 byte.Sekali lagi sebagai fungsi, tetapi kali ini memanfaatkan perulangan berikut:
c(n)
memasuki rekursi tak terbatas untuk negatifn
, meskipun itu tidak relevan untuk tantangan ini.Karena memanggil fungsi tampaknya merupakan alternatif yang dapat diterima untuk konsol I / O:
c(n)
mengambilint
dan mengembalikan sebuahint
.Entri asli:
Alih-alih langsung menghitung definisi, rumus ditulis ulang sebagai:
Rumus mengasumsikan
n >= 2
, tetapi kode bertanggung jawab untukn = 0
dann = 1
juga.Dalam kekacauan C di atas,
n
dank
memiliki peran yang sama seperti dalam formula, saatc
mengakumulasi produk. Semua perhitungan dilakukan dalam floating point menggunakandouble
, yang hampir selalu merupakan ide yang buruk, tetapi dalam kasus ini hasilnya benar hingga n = 19 setidaknya, jadi tidak apa-apa.float
akan menghemat 1 byte, sayangnya itu tidak cukup tepat.sumber
c(n){return!n?:(4+6./~n)*c(n-1);}
?:
! Rupanya, itu adalah ekstensi GNU C tapi saya pikir itu masih memenuhi syarat.Jelly , 4 byte
Cobalah online!
Bagaimana itu bekerja
sumber
c
mendapatkan2z
danz
sebagai argumennya?CJam, 12 byte
Cobalah online.
Di luar input 11, Anda harus memberi tahu Java VM Anda untuk menggunakan lebih banyak memori. Dan saya tidak akan benar-benar merekomendasikan melampaui 11. Secara teori, ini bekerja untuk N apa pun, karena CJam menggunakan bilangan bulat presisi arbitrer.
Penjelasan
CJam tidak memiliki built-in untuk koefisien binomial, dan menghitung mereka dari tiga faktorial membutuhkan banyak byte ... jadi kita harus melakukan sesuatu yang lebih baik dari itu. :)
sumber
ri_2*m!1$m!_*/\)/
) dalam implementasi saya. Satu-satunya hal yang baik adalah bahwa itu jauh lebih cepat. :)Mathematica,
1613 byteBuilt-in, amirite fellas: /
Versi non-builtin (21 byte):
Versi binomial-kurang (25 byte):
sumber
TI-BASIC, 11 byte
Anehnya, nCr memiliki prioritas lebih tinggi daripada multiplikasi.
sumber
Python 3, 33 byte
Menggunakan pengulangan
Kasing dasar 0 ditangani sebagai
0**n or
, yang berhenti seperti1
kapann==0
dan sebaliknya mengevaluasi ekspresi rekursif di sebelah kanan. Operator bitwise~n==-n-1
memperpendek penyebut dan menghemat parens.Python 3 digunakan untuk divisi float-nya. Python 2 dapat melakukan hal yang sama dengan satu byte lagi untuk ditulis
6.
.sumber
n<1
bukan0**n
?True
untukn==0
bukan1
. Tentu saja,True == 1
tetapiTrue is not 1
dan hasilnya berbeda. Saya berharap ini tidak diizinkan. Apakah Anda tahu jika kami memiliki keputusan tentang ini?isinstance(True, int) is True
Lagipula.J, 8 byte
Ini adalah kereta monadik; menggunakan rumus (2x nCr x) / (x + 1). Coba di sini .
sumber
pl, 4 byte
Cobalah online.
Penjelasan
Dalam pl, fungsi mengeluarkan argumennya dari stack dan mendorong hasilnya kembali ke stack. Biasanya ketika tidak ada cukup argumen di stack, fungsi tersebut gagal secara diam-diam. Namun, sesuatu yang istimewa terjadi ketika jumlah argumen pada stack adalah salah satu dari arity fungsi - variabel input
_
ditambahkan ke daftar argumen:Akibatnya, ini adalah kodesemu:
sumber
Sesos ,
948668 byte8 byte dengan mengubah faktorial dari versi 1 ke versi 2.
18 byte dengan komputasi
n!(n+1)!
dalam satu langkah. Sangat terinspirasi oleh algoritma uji keutamaan Dennis .Hexdump:
Cobalah online!
Menggunakan formula
a(n) = (2n)! / (n!(n+1)!)
.Assembler
Setara dengan Brainfuck
Script Retina ini digunakan untuk menghasilkan setara dengan brainfuck. Perhatikan bahwa itu hanya menerima satu digit sebagai argumen perintah, dan tidak memeriksa apakah perintah ada di komentar.
sumber
Pyth, 8
Cobalah secara online atau jalankan Test Suite
Penjelasan
sumber
Serius, 9 byte
Hex Dump:
Cobalah online
Penjelasan:
sumber
2n
baris ke - t adalahC(2n,n)
. Jadi:,;u@τ╣║/
selama 8 byte.║
danM
akan bekerja.JavaScript (ES6), 24 byte
Berdasarkan jawaban Python .
Bagaimana itu bekerja
Saya pikir ini adalah yang terpendek, tetapi saran dipersilahkan!
sumber
Julia, 23 byte
Ini adalah fungsi anonim yang menerima integer dan mengembalikan float. Ini menggunakan rumus binomial dasar. Untuk menyebutnya, berikan nama, mis
f=n->...
.sumber
Matlab,
3525 byteOktaf, 23 byte
sumber
@(n)
alih-alih fungsi, fungsi anonim ok.n
:@(n)nchoosek(2*n,n++)/n
.../++n
tidak berhasil juga. : /𝔼𝕊𝕄𝕚𝕟, 3 karakter / 6 byte
Try it here (Firefox only).
Dibangun ftw! Sangat senang saya menerapkan math.js sejak dini.
Solusi bonus, 12 karakter / 19 byte
Try it here (Firefox only).
Ay! Byte 19!
Mengevaluasi ke pseudo-ES6 sebagai:
sumber
Haskell, 27 byte
Formula rekursif. Pasti ada cara untuk menghemat orangtua ...
Langsung mengambil produk itu 2 byte lebih lama:
sumber
g(n-1)
=>g$n-1
menyimpan satu byte. Sunting: sebenarnya ini tidak berfungsi karena rumus diartikan sebagai(...*g) (n-1)
.Dyalog APL, 9 byte
Ini adalah kereta monadik; menggunakan rumus (2x nCr x) / (x + 1). Cobalah online di sini .
sumber
C,
122121119108 byteSaya menggunakan gcc (GCC) 3.4.4 (cygming special, gdc 0.12, menggunakan dmd 0.125) untuk dikompilasi di lingkungan windows cygwin. Input masuk pada baris perintah. Ini mirip dengan solusi Python Sherlock9 tetapi loop digabungkan menjadi satu untuk menghindari overflow dan mendapatkan output hingga angka Catalan ke-20 (n = 19).
sumber
main
definisi untuk menyimpan byte.char**v
daripadachar *v[]
. (Ruang sebelumnya*
tidak diperlukan, dan jenisnya setara.)n
.Javagony , 223 byte
Sepenuhnya diperluas:
sumber
Japt, 16 byte
Bahkan Mathematica lebih pendek.
:-/
Cobalah online!
Tanpa penjelasan dan penjelasan
Versi alternatif, berdasarkan pada rumus rekursif:
sumber
Vitsy , 13 Bytes
Ini adalah fungsi di Vitsy . Bagaimana cara menjadikannya program yang melakukan ini, Anda bertanya? Gabungkan
N
. c:Cobalah online!
sumber
Milky Way 1.5.14 , 14 byte
Penjelasan
atau, sebagai alternatif, versi yang jauh lebih efisien:
Milky Way 1.5.14 , 22 byte
Penjelasan
Pemakaian
sumber
Clojure / ClojureScript, 53 byte
Clojure bisa membuat frustasi bermain golf. Ini sangat bernasib sementara masih sangat mudah dibaca, tetapi beberapa fitur bagus benar-benar bertele-tele.
(inc x)
lebih idiomatis daripada(+ x 1)
dan "terasa" lebih ringkas, tetapi sebenarnya tidak menyimpan karakter. Dan menulis rantai operasi lebih baik(->> x inc (/ 6) (- 4))
, tetapi sebenarnya lebih lama dari sekadar melakukannya dengan cara yang jelek.sumber
Prolog, 42 byte
Menggunakan rekursi hampir selalu merupakan cara untuk menggunakan Prolog.
Kode:
Contoh:
Cobalah online di sini
sumber
*
simbol di sini?Oktaf, 22 byte
sumber
Ceylon, 60 byte
Ini berfungsi hingga C 30 , karena Ceylon's Integers menandatangani angka 64-bit (C 31 mengalami overflow, akan dihitung sebagai -4050872099593203).
Saya tidak tahu apakah Ceylon memiliki fungsi matematika yang lebih tinggi built-in, tetapi kemudian mengimpor paket yang tepat mungkin akan lebih lama dari hanya menghitung ini dengan berjalan kaki.
sumber
R,
352816 byteSunting: Gunakan paket nomor bawaan.
sumber
MATL , 8 byte
Cobalah online!
Penjelasan
sumber
05AB1E , 6 byte
Penjelasan:
sumber
R, 28 byte
Tidak menggunakan paket, jadi sedikit lebih lama dari jawaban sebelumnya
sumber