Die katalanischen Zahlen ( OEIS ) sind eine Folge natürlicher Zahlen, die häufig in der Kombinatorik vorkommen.
Die n-te katalanische Zahl ist die Anzahl der Dyck-Wörter (ausgeglichene Zeichenfolgen in Klammern oder Klammern wie [[][]]
; formal definiert als Zeichenfolge mit zwei Zeichen a und b, sodass jede Teilzeichenfolge, die am Anfang beginnt, die Nummer eines Zeichens hat, das größer oder gleich der Zahl ist von b Zeichen, und die gesamte Zeichenfolge hat die gleiche Anzahl von a und b Zeichen) mit der Länge 2n. Die n-te katalanische Zahl (für n> = 0) ist auch explizit definiert als:
Ab n = 0 lauten die ersten 20 katalanischen Zahlen:
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190...
Herausforderung
Schreiben Sie ein vollständiges Programm oder eine Funktion, die eine nicht negative ganze Zahl n über STDIN oder eine akzeptable Alternative annimmt und die n-te katalanische Zahl ausgibt. Ihr Programm muss mindestens für die Eingänge 0-19 funktionieren.
I / O
Eingang
Ihr Programm muss Eingaben von STDIN, Funktionsargumenten oder einer der akzeptablen Alternativen für diesen Meta-Post erhalten. Sie können die eingegebene Zahl als Standard-Dezimalrepräsentation, unäre Repräsentation oder Byte lesen.
- Wenn (und nur wenn) Ihre Sprache keine Eingabe von STDIN oder einer akzeptablen Alternative annehmen kann, kann sie Eingabe von einer fest codierten Variablen oder einem geeigneten Äquivalent im Programm annehmen.
Ausgabe
Ihr Programm muss die n-te katalanische Nummer für STDOUT, Funktionsergebnis oder eine der zulässigen Alternativen gemäß diesem Metapost ausgeben . Sie können die katalanische Zahl in ihrer Standarddarstellung als Dezimalzahl, als unäre Darstellung oder in Bytes ausgeben.
Die Ausgabe sollte aus der entsprechenden katalanischen Zahl bestehen, optional gefolgt von einer oder mehreren Zeilenumbrüchen. Es kann keine andere Ausgabe generiert werden, mit Ausnahme der konstanten Ausgabe des Interpreters Ihrer Sprache, die nicht unterdrückt werden kann (z. B. eine Begrüßung, ANSI-Farbcodes oder Einrückungen).
Es geht nicht darum, die Sprache zu finden, die am kürzesten ist. Hier geht es darum, das kürzeste Programm in jeder Sprache zu finden. Daher werde ich keine Antwort annehmen.
Bei dieser Herausforderung sind Sprachen, die neuer sind als die Herausforderung, akzeptabel , solange sie implementiert sind. Es ist erlaubt (und sogar empfohlen), diesen Dolmetscher für eine zuvor nicht implementierte Sprache selbst zu schreiben. Ansonsten müssen alle Standardregeln des Code-Golfs eingehalten werden. Einsendungen in den meisten Sprachen werden in Bytes in einer geeigneten, bereits vorhandenen Codierung (normalerweise UTF-8) bewertet. Beachten Sie auch, dass integrierte Funktionen zur Berechnung der n-ten katalanischen Nummer zulässig sind.
Katalog
Das Stapel-Snippet am Ende dieses Beitrags generiert den Katalog aus den Antworten a) als Liste der kürzesten Lösungen pro Sprache und b) als Gesamt-Bestenliste.
Um sicherzustellen, dass Ihre Antwort angezeigt wird, beginnen Sie Ihre Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:
## Language Name, N bytes
Wo N
ist die Größe Ihres Beitrags? Wenn Sie Ihren Score zu verbessern, Sie können alte Rechnungen in der Überschrift halten, indem man sich durch das Anschlagen. Zum Beispiel:
## Ruby, <s>104</s> <s>101</s> 96 bytes
Wenn Sie mehrere Zahlen in Ihre Kopfzeile aufnehmen möchten (z. B. weil Ihre Punktzahl die Summe von zwei Dateien ist oder wenn Sie die Strafen für Interpreter-Flags separat auflisten möchten), stellen Sie sicher, dass die tatsächliche Punktzahl die letzte Zahl in der Kopfzeile ist:
## Perl, 43 + 2 (-p flag) = 45 bytes
Sie können den Namen der Sprache auch als Link festlegen, der dann im Snippet angezeigt wird:
## [><>](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>
Antworten:
C
7852393433 BytesNoch mehr C-Magie (danke xsot):
?:
ist eine GNU-Erweiterung .Diesmal durch Erweitern der folgenden Wiederholung (danke an xnor und Thomas Kwa):
-(n+1)
wird durch ersetzt~n
, was im Zweierkomplement äquivalent ist und 4 Bytes einspart.Wieder als Funktion, aber dieses Mal unter Ausnutzung der folgenden Wiederholung:
c(n)
gibt eine unendliche Rekursion für das Negative einn
, obwohl dies für diese Herausforderung nicht relevant ist.Da der Aufruf einer Funktion eine akzeptable Alternative zu Konsolen-E / A darstellt:
c(n)
nimmt einint
und gibt ein zurückint
.Originaleintrag:
Anstatt die Definition direkt zu berechnen, wird die Formel wie folgt umgeschrieben:
Die Formel geht davon aus
n >= 2
, aber der Code berücksichtigtn = 0
undn = 1
auch.In der C-Mess oben
n
undk
haben die gleiche Rolle wie in der Formel, währendc
das Produkt akkumuliert. Alle Berechnungen werden in Gleitkommazahlen ausgeführtdouble
, was fast immer eine schlechte Idee ist, aber in diesem Fall sind die Ergebnisse mindestens bis n = 19 korrekt, also ist es in Ordnung.float
hätte 1 Byte gespart, leider ist es nicht genau genug.quelle
c(n){return!n?:(4+6./~n)*c(n-1);}
?:
! Anscheinend ist es eine GNU C-Erweiterung, aber ich denke, dass sie noch qualifiziert ist.Gelee , 4 Bytes
Probieren Sie es online!
Wie es funktioniert
quelle
c
Erhalten2z
undz
als Argument?CJam, 12 Bytes
Probieren Sie es online aus.
Nach Eingabe von 11 müssen Sie Ihrer Java-VM mitteilen, dass sie mehr Arbeitsspeicher verwenden soll. Und ich würde eigentlich nicht empfehlen, über 11 hinauszugehen. Theoretisch funktioniert es jedoch für jedes N, da CJam Ganzzahlen mit beliebiger Genauigkeit verwendet.
Erläuterung
CJam hat keine eingebauten Binomialkoeffizienten, und die Berechnung aus drei Fakultäten erfordert viele Bytes. Wir müssen also etwas Besseres tun. :)
quelle
ri_2*m!1$m!_*/\)/
In meiner Implementierung wurden immer noch 17 Byte ( ) verwendet. Das einzig gute ist, dass es viel schneller ist. :)Mathematica,
1613 BytesEingebaute Amiriten: /
Nicht eingebaute Version (21 Bytes):
Eine binomiallose Version (25 Bytes):
quelle
TI-BASIC, 11 Bytes
Seltsamerweise hat nCr eine höhere Priorität als die Multiplikation.
quelle
Python 3, 33 Bytes
Verwendet die Wiederholung
Der Basisfall von 0 wird als behandelt
0**n or
, der als1
wannn==0
endet und ansonsten den rekursiven Ausdruck auf der rechten Seite auswertet. Der bitweise Operator~n==-n-1
verkürzt den Nenner und spart Parens.Python 3 wird für die Float-Division verwendet. Python 2 könnte dasselbe mit einem weiteren zu schreibenden Byte tun
6.
.quelle
n<1
lieber als0**n
?True
fürn==0
statt1
. Natürlich,True == 1
aberTrue is not 1
und es druckt anders. Ich würde erwarten, dass dies nicht erlaubt ist. Wissen Sie, ob wir diesbezüglich eine Entscheidung treffen?isinstance(True, int) is True
Nach alldem.J, 8 Bytes
Dies ist ein monadischer Zug; es wird die Formel (2x nCr x) / (x + 1) verwendet. Probieren Sie es hier aus .
quelle
pl, 4 Bytes
Probieren Sie es online aus.
Erläuterung
In pl nehmen Funktionen ihre Argumente vom Stapel und verschieben das Ergebnis zurück auf den Stapel. Normalerweise schlägt die Funktion im Hintergrund fehl, wenn nicht genügend Argumente auf dem Stapel vorhanden sind. Etwas Besonderes passiert jedoch, wenn die Anzahl der Argumente auf dem Stapel nicht der Arität der Funktion entspricht - die Eingabevariable
_
wird der Argumentliste hinzugefügt:In der Tat ist dies der Pseudocode:
quelle
Sesos ,
948668 Bytes8 Bytes durch Ändern des Faktors er von Version 1 auf Version 2.
18 Bytes durch Rechnen
n!(n+1)!
in einem Schritt. Weitgehend inspiriert von Dennis 'Primalitätstest-Algorithmus .Hexdump:
Probieren Sie es online!
Verwendet die Formel
a(n) = (2n)! / (n!(n+1)!)
.Assembler
Brainfuck-Äquivalent
Dieses Retina-Skript wird verwendet, um das Brainfuck-Äquivalent zu generieren. Beachten Sie, dass es nur eine Ziffer als Befehlsargument akzeptiert und nicht prüft, ob ein Befehl in den Kommentaren enthalten ist.
quelle
Pyth, 8
Probieren Sie es online aus oder führen Sie die Test Suite aus
Erläuterung
quelle
Im Ernst, 9 Bytes
Hex Dump:
Probieren Sie es online aus
Erläuterung:
quelle
2n
dritten Zeile istC(2n,n)
. Also:,;u@τ╣║/
für 8 Bytes.║
undM
würde funktionieren.JavaScript (ES6), 24 Byte
Basierend auf der Python-Antwort .
Wie es funktioniert
Ich denke, das ist die kürzeste, die es geben kann, aber Vorschläge sind willkommen!
quelle
Julia, 23 Bytes
Dies ist eine anonyme Funktion, die eine Ganzzahl akzeptiert und einen Gleitkommawert zurückgibt. Es wird die grundlegende Binomialformel verwendet. Um es zu nennen, geben Sie ihm einen Namen, z
f=n->...
.quelle
Matlab,
3525 BytesOktave, 23 Bytes
quelle
@(n)
anstelle von Funktion auch anonyme Funktionen verwenden.n
:@(n)nchoosek(2*n,n++)/n
.../++n
auch nicht. : /𝔼𝕊𝕄𝕚𝕟 3 Zeichen / 6 Bytes
Try it here (Firefox only).
Builtins ftw! Ich bin froh, dass ich math.js früh implementiert habe.
Bonuslösung, 12 Zeichen / 19 Bytes
Try it here (Firefox only).
Ja! 19. Byte!
Bewertet zu Pseudo-ES6 als:
quelle
Haskell, 27 Bytes
Eine rekursive Formel. Es muss einen Weg geben, um bei den Eltern zu sparen ...
Direkt unter dem Produkt war 2 Bytes länger:
quelle
g(n-1)
=>g$n-1
spart ein Byte. Bearbeiten: eigentlich funktioniert das nicht, da dann die Formel als interpretiert wird(...*g) (n-1)
.Dyalog APL, 9 Bytes
Dies ist ein monadischer Zug; es wird die Formel (2x nCr x) / (x + 1) verwendet. Probieren Sie es hier online aus .
quelle
C,
122121119108 BytesIch habe gcc (GCC) 3.4.4 (cygming special, gdc 0.12, mit dmd 0.125) verwendet, um in einer Windows-Cygwin-Umgebung zu kompilieren. Die Eingabe erfolgt über die Befehlszeile. Es ähnelt der Python-Lösung von Sherlock9, aber die Schleifen sind zu einer zusammengefasst, um einen Überlauf zu vermeiden und eine Ausgabe bis zur 20. katalanischen Zahl (n = 19) zu erhalten.
quelle
main
Definition entfernen , um ein Byte zu speichern.char**v
anstatt 2 weitere Bytes speichernchar *v[]
. (Der Platz vorher*
wird nicht benötigt, und die Typen sind gleichwertig.)n
.Javagony , 223 Bytes
Voll ausgebaut:
quelle
Japt, 16 Bytes
Sogar Mathematica ist kürzer.
:-/
Probieren Sie es online!
Ungolfed und Erklärung
Alternative Version, basierend auf der rekursiven Formel:
quelle
Vitsy , 13 Bytes
Dies ist eine Funktion in Vitsy . Wie macht man ein Programm, das das macht? Verketten
N
. c:Probieren Sie es online!
quelle
Milchstraße 1.5.14 , 14 Bytes
Erläuterung
oder alternativ die wesentlich effizientere Version:
Milchstraße 1.5.14 , 22 Bytes
Erläuterung
Verwendung
quelle
Clojure / ClojureScript, 53 Byte
Clojure kann beim Golfen ziemlich frustrierend sein. Es ist zwar sehr prägnant, aber immer noch gut lesbar, aber einige der raffinierteren Funktionen sind sehr ausführlich.
(inc x)
ist idiomatischer als(+ x 1)
und "fühlt" sich prägnanter an, speichert jedoch keine Zeichen. Und Ketten von Operationen zu schreiben ist schöner als(->> x inc (/ 6) (- 4))
, aber es ist tatsächlich länger, als es nur auf hässliche Weise zu tun.quelle
Prolog, 42 Bytes
Die Verwendung von Rekursion ist bei Prolog fast immer der richtige Weg.
Code:
Beispiel:
Probieren Sie es hier online aus
quelle
*
Symbol hier neu?Oktave, 22 Bytes
quelle
Ceylon, 60 Bytes
Dies funktioniert bis C 30 , da Ceylons Ganzzahlen mit 64-Bit-Zahlen signiert sind (C 31 hat einen Überlauf und wird als -4050872099593203 berechnet).
Ich weiß nicht, ob Ceylon über integrierte höhere mathematische Funktionen verfügt, aber der Import des richtigen Pakets würde wahrscheinlich länger dauern, als dies nur zu Fuß zu berechnen.
quelle
R
352816 BytesBearbeiten: Verwenden Sie das integrierte Zahlenpaket.
quelle
MATL , 8 Bytes
Probieren Sie es online!
Erläuterung
quelle
05AB1E , 6 Bytes
Erläuterung:
quelle
R, 28 Bytes
Kein Paket verwenden, also etwas länger als eine vorherige Antwort
quelle