Te numery Kataloński ( OEIS ) to sekwencja liczb naturalnych, często występujących w kombinatoryki.
N-ta liczba katalońska to liczba słów Dyck (zrównoważone ciągi nawiasów lub nawiasów, takie jak [[][]]
; formalnie zdefiniowane jako ciąg znaków przy użyciu dwóch znaków a i b tak, że dowolny ciąg znaków rozpoczynający się od początku ma liczbę znaków większą lub równą liczbie znaków b, a cały łańcuch ma taką samą liczbę znaków aib) o długości 2n. N-ta liczba katalońska (dla n> = 0) jest również wyraźnie zdefiniowana jako:
Począwszy od n = 0, pierwsze 20 liczb katalońskich to:
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190...
Wyzwanie
Napisz pełny program lub funkcję, która przyjmuje nieujemną liczbę całkowitą n przez STDIN lub akceptowalną alternatywę i wyprowadza ntą liczbę katalońską. Twój program musi działać co najmniej dla wejść 0–19.
I / O
Wkład
Twój program musi pobierać dane wejściowe z STDIN, argumenty funkcji lub dowolne z dopuszczalnych alternatyw dla tego meta postu. Wprowadzoną liczbę można odczytać jako jej standardową reprezentację dziesiętną, jedność lub bajty.
- Jeśli (i tylko jeśli) twój język nie może pobierać danych wejściowych ze STDIN lub jakiejkolwiek akceptowalnej alternatywy, może pobierać dane wejściowe ze zmiennej zakodowanej na stałe lub odpowiedniego odpowiednika w programie.
Wydajność
Twój program musi wypisać n-ty kataloński numer do STDOUT, wyniku funkcji lub dowolnej z dopuszczalnych alternatyw dla tego meta-postu. Możesz wypisać liczbę katalońską w jej standardowej reprezentacji dziesiętnej, jedności lub bajtach.
Wynik powinien składać się z odpowiedniej liczby katalońskiej, po której opcjonalnie może następować jedna lub więcej nowych linii. Żadne inne dane wyjściowe nie mogą być generowane, z wyjątkiem stałych wyników tłumacza języka, których nie można stłumić (takich jak powitanie, kody kolorów ANSI lub wcięcia).
Tu nie chodzi o znalezienie najkrótszego języka. Chodzi o znalezienie najkrótszego programu w każdym języku. Dlatego nie przyjmuję odpowiedzi.
W tym wyzwaniu języki nowsze niż wyzwanie są dopuszczalne, o ile mają implementację. Dozwolone jest (a nawet zachęcane) samodzielne pisanie tego tłumacza dla wcześniej niewdrożonego języka. Poza tym należy przestrzegać wszystkich standardowych zasad gry w golfa kodowego . Zgłoszenia w większości języków będą oceniane w bajtach w odpowiednim wcześniej istniejącym kodowaniu (zwykle UTF-8). Należy również pamiętać, że wbudowane metody obliczania n-tej liczby katalońskiej są dozwolone.
Katalog
Fragment kodu na dole tego postu generuje katalog na podstawie odpowiedzi a) jako listy najkrótszych rozwiązań według języka oraz b) jako ogólnej tabeli wyników.
Aby upewnić się, że twoja odpowiedź się pojawi, zacznij od nagłówka, korzystając z następującego szablonu Markdown:
## Language Name, N bytes
gdzie N
jest rozmiar twojego zgłoszenia. Jeśli poprawić swój wynik, to może zachować stare porachunki w nagłówku, uderzając je przez. Na przykład:
## Ruby, <s>104</s> <s>101</s> 96 bytes
Jeśli chcesz umieścić w nagłówku wiele liczb (np. Ponieważ twój wynik to suma dwóch plików lub chcesz osobno wymienić kary za flagi tłumacza), upewnij się, że rzeczywisty wynik jest ostatnią liczbą w nagłówku:
## Perl, 43 + 2 (-p flag) = 45 bytes
Możesz także ustawić nazwę języka jako link, który pojawi się we fragmencie:
## [><>](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>
Odpowiedzi:
C,
7852393433 bajtówJeszcze więcej magii C (dzięki xsot):
?:
jest rozszerzeniem GNU .Tym razem rozszerzając ponowny cykl poniżej (dzięki xnor i Thomas Kwa):
-(n+1)
jest zastąpiony przez~n
, co jest równoważne uzupełnieniu dwóch i pozwala zaoszczędzić 4 bajty.Ponownie jako funkcja, ale tym razem wykorzystując następującą powtarzalność:
c(n)
wchodzi w nieskończoną rekurencję jako negatywnąn
, chociaż nie ma to znaczenia dla tego wyzwania.Ponieważ wywoływanie funkcji wydaje się akceptowalną alternatywą dla konsoli I / O:
c(n)
bierzeint
i zwraca anint
.Oryginalny wpis:
Zamiast bezpośrednio obliczać definicję, formuła jest przepisywana jako:
Formuła zakłada
n >= 2
, ale kod stanowin = 0
in = 1
zbyt.W bałaganie C powyżej
n
ik
pełnią tę samą rolę, co w formule, jednocześniec
kumulując produkt. Wszystkie obliczenia są wykonywane przy użyciu liczb zmiennoprzecinkowychdouble
, co prawie zawsze jest złym pomysłem, ale w tym przypadku wyniki są poprawne do co najmniej n = 19, więc jest w porządku.float
zaoszczędziłby 1 bajt, niestety nie jest wystarczająco precyzyjny.źródło
c(n){return!n?:(4+6./~n)*c(n-1);}
?:
! Najwyraźniej jest to rozszerzenie GNU C, ale myślę, że nadal się kwalifikuje.Galaretka , 4 bajty
Wypróbuj online!
Jak to działa
źródło
c
get2z
iz
jego argumenty?CJam, 12 bajtów
Wypróbuj online.
Poza wejściem 11 musisz powiedzieć maszynie wirtualnej Java, aby zużywała więcej pamięci. I tak naprawdę nie zalecałbym wychodzenia daleko poza 11. Teoretycznie działa to na dowolne N, ponieważ CJam używa liczb całkowitych o dowolnej precyzji.
Wyjaśnienie
CJam nie ma wbudowanego współczynnika dwumianowego, a obliczenie ich z trzech silni zajmuje dużo bajtów ... więc będziemy musieli zrobić coś lepszego. :)
źródło
ri_2*m!1$m!_*/\)/
) w mojej implementacji. Jedyną dobrą rzeczą jest to, że jest znacznie szybsza. :)Mathematica,
1613 bajtówWbudowane, amirite fellas: /
Wersja niewbudowana (21 bajtów):
Wersja bez dwumianowa (25 bajtów):
źródło
TI-BASIC, 11 bajtów
O dziwo, nCr ma wyższy priorytet niż mnożenie.
źródło
Python 3, 33 bajty
Korzysta z nawrotu
Podstawowy przypadek 0 jest obsługiwany jako
0**n or
, który zatrzymuje się jako1
kiedy,n==0
a w przeciwnym razie ocenia wyrażenie rekurencyjne po prawej stronie. Bitowy operator~n==-n-1
skraca mianownik i oszczędza na parenach.Python 3 jest używany do podziału zmiennoprzecinkowego. Python 2 mógłby zrobić to samo z jeszcze jednym bajtem do napisania
6.
.źródło
n<1
zamiast0**n
?True
nan==0
zamiast1
. Oczywiście,True == 1
aleTrue is not 1
i drukuje inaczej. Spodziewałbym się, że to nie będzie dozwolone. Czy wiesz, czy mamy w tej sprawie orzeczenie?isinstance(True, int) is True
po wszystkim.J, 8 bajtów
To jest pociąg monadyczny; wykorzystuje formułę (2x nCr x) / (x + 1). Wypróbuj tutaj .
źródło
pl, 4 bajty
Wypróbuj online.
Wyjaśnienie
W pl, funkcje usuwają argumenty ze stosu i wypychają wynik z powrotem na stos. Zwykle, gdy na stosie nie ma wystarczającej liczby argumentów, funkcja po prostu nie działa. Jednak dzieje się coś wyjątkowego, gdy ilość argumentów na stosie jest jednoznaczna z rodzajem funkcji - zmienna wejściowa
_
jest dodawana do listy argumentów:W efekcie jest to pseudokod:
źródło
Sesos ,
948668 bajtów8 bajtów poprzez zmianę silnidera z wersji 1 na wersję 2.
18 bajtów, obliczając
n!(n+1)!
w jednym kroku. W dużej mierze inspirowany algorytmem testowania pierwotności Dennisa .Hexdump:
Wypróbuj online!
Korzysta ze wzoru
a(n) = (2n)! / (n!(n+1)!)
.Monter
Odpowiednik Brainfuck
Ten skrypt Retina jest używany do generowania ekwiwalentu pieprzenia mózgu. Zauważ, że akceptuje tylko jedną cyfrę jako argument polecenia i nie sprawdza, czy polecenie jest w komentarzach.
źródło
Pyth, 8
Wypróbuj online lub uruchom pakiet testowy
Wyjaśnienie
źródło
Poważnie, 9 bajtów
Hex Dump:
Wypróbuj online
Wyjaśnienie:
źródło
2n
trzeciego rzędu toC(2n,n)
. Zatem:,;u@τ╣║/
dla 8 bajtów.║
iM
działałyby.JavaScript (ES6), 24 bajty
Na podstawie odpowiedzi w języku Python .
Jak to działa
Myślę, że jest to najkrótszy możliwy, ale sugestie są mile widziane!
źródło
Julia, 23 bajty
Jest to anonimowa funkcja, która przyjmuje liczbę całkowitą i zwraca liczbę zmiennoprzecinkową. Wykorzystuje podstawową formułę dwumianową. Aby to nazwać, nadaj mu nazwę, np
f=n->...
.źródło
Matlab,
3525 bajtówOktawa, 23 bajty
źródło
@(n)
zamiast funkcji, funkcje anonimowe są w porządku.n
:@(n)nchoosek(2*n,n++)/n
.../++n
też nie działa. : /𝔼𝕊𝕄𝕚𝕟, 3 znaki / 6 bajtów
Try it here (Firefox only).
Wbudowane ftw! Cieszę się, że wcześnie zaimplementowałem math.js.
Rozwiązanie premiowe, 12 znaków / 19 bajtów
Try it here (Firefox only).
Ay! 19 bajt!
Ocenia na pseudo-ES6 jako:
źródło
Haskell, 27 bajtów
Recursywna formuła. Musi być sposób na oszczędzanie na parens ...
Bezpośrednie pobranie produktu było o 2 bajty dłuższe:
źródło
g(n-1)
=>g$n-1
zapisuje jeden bajt. Edycja: tak naprawdę to nie działa, ponieważ wtedy formuła jest interpretowana jako(...*g) (n-1)
.Dyalog APL, 9 bajtów
To jest pociąg monadyczny; wykorzystuje formułę (2x nCr x) / (x + 1). Wypróbuj online tutaj .
źródło
C,
122121119108 bajtówUżyłem gcc (GCC) 3.4.4 (cygming special, gdc 0.12, używając dmd 0.125) do kompilacji w środowisku Windows cygwin. Dane wejściowe pojawiają się w wierszu poleceń. Jest podobny do rozwiązania Python Sherlock9, ale pętle są łączone w jedną, aby uniknąć przepełnienia i uzyskać wynik do 20. liczby katalońskiej (n = 19).
źródło
main
definicji, aby zapisać bajt.char**v
zamiastchar *v[]
. (Poprzednia przestrzeń*
nie jest potrzebna, a typy są równoważne.)n
.Javagony , 223 bajty
W pełni rozbudowany:
źródło
Japt, 16 bajtów
Nawet Mathematica jest krótsza.
:-/
Wypróbuj online!
Bez golfa i wyjaśnienia
Alternatywna wersja, oparta na rekurencyjnej formule:
źródło
Vitsy , 13 bajtów
Jest to funkcja w Vitsy . Jak zrobić program, który to robi, pytasz? Łączy
N
. do:Wypróbuj online!
źródło
Droga Mleczna 1.5.14 , 14 bajtów
Wyjaśnienie
lub, alternatywnie, znacznie bardziej wydajna wersja:
Droga Mleczna 1.5.14 , 22 bajty
Wyjaśnienie
Stosowanie
źródło
Clojure / ClojureScript, 53 bajty
Clojure może być dość frustrujący podczas gry w golfa. Jest bardzo krwisty, a jednocześnie bardzo czytelny, ale niektóre z bardziej subtelnych cech są naprawdę pełne.
(inc x)
jest bardziej idiomatyczny(+ x 1)
i „wydaje się” bardziej zwięzły, ale tak naprawdę nie zapisuje postaci. A pisanie łańcuchów operacji jest przyjemniejsze(->> x inc (/ 6) (- 4))
, ale w rzeczywistości jest dłuższe niż robienie tego w brzydki sposób.źródło
Prolog, 42 bajty
Korzystanie z rekurencji jest prawie zawsze sposobem na skorzystanie z Prologu.
Kod:
Przykład:
Wypróbuj online tutaj
źródło
*
tutaj symbol?Oktawa, 22 bajty
źródło
Cejlon, 60 bajtów
Działa to do C 30 , ponieważ liczby całkowite Cejlona są oznaczone liczbami 64-bitowymi (C 31 ma przepełnienie, zostanie obliczone jako -4050872099593203).
Nie wiem, czy Ceylon ma jakieś wbudowane wyższe funkcje matematyczne, ale zaimportowanie odpowiedniego pakietu prawdopodobnie byłoby dłuższe niż zwykłe obliczenie tego na piechotę.
źródło
R,
352816 bajtówEdycja: użyj wbudowanego pakietu liczb.
źródło
MATL , 8 bajtów
Wypróbuj online!
Wyjaśnienie
źródło
05AB1E , 6 bajtów
Wyjaśnienie:
źródło
R, 28 bajtów
Nie używa pakietu, więc nieco dłużej niż poprzednia odpowiedź
źródło