var QUESTION_ID=83873,OVERRIDE_USER=48934;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+(?:\.\d+)?)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<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="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><div id="language-list"> <h2>Winners 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><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>
Odpowiedzi:
Binarny rachunek lambda , 114 bitów = 14,25 bajtów
Hexdump:
Dwójkowy:
Wyjaśnienie
Jest to (λ x . (Λ y . X y (λ m . M (λ g . Λ n . N g 1) (λ n . Λ f . X ( n f )) x ) y ) (λ f . Λ z . f ( x f z ))) 3, gdzie wszystkie liczby są reprezentowane jako cyfry kościelne. Liczby kościelne są standardową reprezentacją liczb naturalnych w rachunku lambda i dobrze nadają się do tego problemu, ponieważ liczbę kościelną definiuje się przez iterację funkcji: n g jest n- tym iteratem funkcji g .
Na przykład, jeśli g jest funkcją λ n . λ f . 3 ( n f ), który mnoży 3 przez liczbę kościelną, a następnie λ n . n g 1 to funkcja, która przenosi 3 do potęgi liczby Kościoła. Powtórzenie tej operacji m razy daje
m (λ g . λ n . n g 1) (λ n . λ f . 3 ( n f )) n = u (3, n , m ).
(Używamy mnożenia u (-, -, 0) zamiast potęgowania u (-, -, 1) jako podstawowego przypadku, ponieważ odejmowanie 1 od liczby kościelnej jest nieprzyjemne .)
Zamień n = 3:
m (λ g . λ n . n g 1) (λ n . λ f . 3 ( n f )) 3 = u (3, 3, m ).
Iterowanie tej operacji 64 razy, zaczynając od m = 4, daje
64 (λ m . M (λ g . Λ n . N g 1) (λ n . Λ f . 3 ( n f )) 3) 4 = G .
Aby zoptymalizować to wyrażenie, podstaw 64 = 4 ^ 3 = 3 4:
3 4 (λ m . M (λ g . Λ n . N g 1) (λ n . Λ f . 3 ( n f )) 3) 4 = G .
Pamiętaj 4 = succ 3 = λ f . λ z . f (3 f z ) jako argument lambda:
(λ y . 3 y (λ m . m (λ g . λ n . n g 1) (λ n . λ f . 3 ( n f )) 3) y ) (λ f . λ z . f (3 f z )) = G .
Na koniec pamiętaj 3 = λ f . λ z . f ( f ( f z )) jako argument lambda:
(λ x . (λ y . x y (λ m . m (λ g . λ n . n g 1) (λ n . λ f . x ( n f )) x ) y ) (λ f . λ z . f ( x f Z ))) 3 = G .
źródło
14.25 bytes
Wygląda na to, że psuje tabelę wyników. Jest analizowany jako25 bytes
i dlatego jesteś umieszczony na drugim miejscu.Haskell, 41 bajtów
Wyjaśnienie:
(`i`1)f n
=i f 1 n
obliczan
iterat funkcjif
rozpoczynający się od1
. W szczególności(`i`1)(*3)n
= 3 ^ n , a iteracja tej konstrukcji m razy dajei(`i`1)(*3)m n
= u (3, n , m ). Możemy przepisać to jako(($n).i(`i`1)(*3))m
= u (3, n , m ) i iterować tę konstrukcję k razy, aby uzyskaći(($3).i(`i`1)(*3))4 k
= g _ k .źródło
Haskell, 43 bajty
Istnieje lepszy sposób na odwrócenie w
g
linii.46 bajtów:
48 bajtów:
Zapisuję definicje.
Podstawowe przypadki są nieco czystsze, a ich kopia zapasowa wynosi 0, ale nie oszczędza bajtów. Być może ułatwi to napisanie alternatywnej definicji.
źródło
+
, aby usunąć nawiasy między nimim-1
?(`g`3)
nie(3`g`)
.Pyth, 25 bajtów
Pierwsza część
M?H.UgbtH*G]3^3G
określa metodęg(G,H) = u(3,G,H+1)
.Aby przetestować pierwszą część należy sprawdzić, czy
7625597484987=u(3,3,2)=g(3,1)
:g3 1
.Druga część
ug3tG64 4
zaczyna się od,r0 = 4
a następnie obliczarn = u(3,3,r(n-1)) = g(3,r(n-1))
64 razy, wyprowadzając końcową wartość (r
jest wybierana zamiast,g
aby uniknąć zamieszania).Aby przetestować tę część, zacznij od
r0=2
a następnie obliczyćr1
:ug3tG1 2
.źródło
^3
↦*3
,tG
↦G
), a inny bajt za pomocą.UgbtH*G]3
↦e.ugNtHG1
.*G]3
↦ShG
.Sesos , 30 bajtów
Zdemontowane
Lub w notacji Brainfuck:
Testowanie
Aby obliczyć u (3, n , u (3, n , ... U (3, n , m ), ...)) z k zagnieżdżone wywołaniami u wymienić trzech pierwszych
add
instrukcjiadd 4
,add 64
,add 3
oadd m
,add k
,add n
odpowiednio. Ponieważ Sesos nie może budować liczb szybciej niż w czasie liniowym, praktycznie jesteś ograniczony do małych wartości, takich jak u (3, 2, 2) = 27, u (3, 5, 1) = 243 iu (3, 1 , u (3, 1,… u (3, 1, m )…)) = 3.źródło
[-]
z,
ponieważ EOF jest0
.JavaScript (ES7), 63 bajty
źródło
Brachylog , 57 bajtów
Nie oczekuje danych wejściowych ani wyjściowych i zapisuje wynik do
STDOUT
. Spowoduje to przepełnienie stosu w jednym punkcie.Aby sprawdzić, czy działa to dla małych wartości (na przykład
u(3,3,2)
) można zastąpić4
o wartościm
i64
z1
.Wyjaśnienie
Jest to w zasadzie prosta implementacja wyjaśnionego sposobu obliczania liczby.
Główny predykat:
Predykat 1:
Predykat 2:
źródło
Karmel , 38 bajtów
To cukier syntaktyczny dla wyrażenia rachunku lambda 64 (λ m . M (λ f . Λ n . N f 1) (λ n . Λ f . 3 ( n f )) 3) 4, gdzie wszystkie liczby są reprezentowane jako kościół cyfry .
źródło
(n f->3 (n f))
nie powinien to czytaćn-1
?(n f->3 (n f))
to funkcja mnożenia przez trzy cyfry kościelne .Prolog (SWIPL), 129/137 bajtów
Aby wyprowadzić liczbę Grahama, zapytaj o
g(64,G).
(jeśli należy policzyć 8 bajtów tego zapytania, długość wynosi 137 bajtów):Ale jak można się spodziewać, kończy się to na stosie.
Test
Cofanie powoduje, że zaczyna brakować stosu:
Nie golfił
Wersja bez golfa dodaje ogólną notację ze strzałką w górę, nie tylko dla 3, i wykorzystuje cięcia i kontrole, aby uniknąć cofania się i nieokreślonych sytuacji.
źródło
64
dowolnym miejscu w kodzie?C, 161 bajtów
EDYCJA: zapisano 11 bajtów, usuwając tabulatory i znaki nowej linii. EDYCJA: thx auhmann zapisał kolejny bajt i naprawił mój program
źródło
g(int a){if(a==1)return u(3,4);return g(a-1);}
ponieważ w ogóle nie jest używany ... A może o czymś zapomniałeś?return g(a-1)
powinien byćreturn u(3,g(a-1))
.u(a,b){return a<2?3:b<2?pow(3,a):u(u(a-1,b),b-1);}g(a){return a<2?u(3,4):u(3,g(a-1));}main(){printf("%d",g(64));}
Mathematica, 59 bajtów
Wykorzystuje niezdefiniowany operator poprawki,
±
który wymaga tylko 1 bajtu, gdy jest zakodowany w ISO 8859-1. Zobacz post @ Martina, aby uzyskać więcej informacji. Funkcje matematyczne obsługują dopasowanie wzorca dla ich argumentów, dzięki czemu dwa przypadki podstawowe można zdefiniować osobno.źródło
n_ ±m_:=Nest[#±(m-1)&,3,n]
C,
114109 bajtówOpierając się na odpowiedzi @thepiercingarrow ( link ), grałem trochę w golfa. Większość oszczędności wynika z nadużywania domyślnego wpisywania argumentów podczas wykonywania funkcji w stylu K&R i zamiany instrukcji if na trójskładnikowe operatory. Dodano opcjonalne znaki nowej funkcji między funkcjami dla czytelności.
Poprawiono do 109 dzięki @LeakyNun.
źródło
g(a){return u(3,a<2?4:g(a-1));}
Python, 85 bajtów
v
Funkcja definiuje taką samą funkcję jak ten znaleziony w odpowiedzi Dennisa :v(n,m) = u(3,n+1,m+1)
.g
Funkcja jest zero-indeksowane wersja tradycyjnego iteracji:g(0) = v(2,3), g(n) = v(2,g(n-1))
. Zatemg(63)
jest liczbą Grahama. Ustawiając domyślną wartośćn
parametrug
funkcji na63
, można uzyskać wymaganą moc wyjściową przez wywołanieg()
(bez parametrów), spełniając w ten sposób nasze wymagania dotyczące przesyłania funkcji, która nie wymaga wprowadzania danych.Sprawdź
v(2,1) = u(3,3,2)
iv(4,0) = u(3,5,1)
przetestuj przypadki online: Python 2 , Python 3źródło
g
wydaje się , że Twoja funkcja jest wyłączona. Nie powinnov(2,n-1)
byćg(n-1)
lub coś podobnego?u
iv
oznacza, że powinno byćg(n-1)-1
.Dyalog APL, 41 bajtów
Przypadek testowy:
źródło
1=⍺:3⋄1=⍵:3*⍺
na just1=⍵:3*⍺
(3=3*1
)Rubinowy, 64 bajty
Pożyczki z algorytmu teoretycznego do obliczenia liczby Grahama .
Mówiąc wprost,
f a = u(3,3,a)
dotyczy to 64 razy.źródło
J, 107 bajtów
Pracuję nad konwersją
u
do programu, ale na razie się uda.źródło
u=:3^[`[:(3$:])/[#<:@]@.*@]
(nie testowano)F #,
111108 bajtówEdytować
Wykorzystuje to poniższą funkcję do obliczenia liczby Grahama
Oto moja poprzednia odpowiedź, która, no cóż, nie:
Całkiem proste. Po prostu definicja
u
funkcji.Stosowanie:
Gdybym przyjął 3 jako wartość dla a, mógłbym ją obniżyć do 60:
Stosowanie:
źródło
u
. Możesz oczywiście dołączyć dowolne potrzebne funkcje pośrednie, takie jaku
z pierwszym argumentem lub bez,R,
154142128126 126118 bajtówUżyłem definicji Wikipedii tej funkcji rekurencyjnej, ponieważ z jakiegoś dziwnego powodu sugerowana nie działała ... lub po prostu ssę golfa R.
UPD: wygolono 12 + 14 = 26 bajtów dzięki końcówce od Leaky Nun . Poprzednia wersja wykorzystywała nieporęczne i mniej wydajne
UPD: wygolono o 2 + 6 + 2 dodatkowe bajty (ponownie, uznanie dla Dziurawej Zakonnicy ) dzięki pomysłowej zamianie na „if (x)” zamiast „if (x == 0)”, ponieważ x <0 nigdy nie jest wprowadzane do funkcja ... prawda?
źródło
u
w tym samym klawiszu co twójg
i zapisałeś 6 dodatkowych bajtów - super!PHP, 114 bajtów
zignoruj podział linii; służą wyłącznie do odczytu.
Możliwe jest zintegrowanie drugiego przypadku z pierwszym: dla
n=1
,3^n
równa się3
.Pozwoli to zaoszczędzić kilka bajtów - o ile widzę - na wszystkich istniejących odpowiedziach; zapisałem dwa bajty na moim
poprzednia wersja, 62 + 43 + 11 = 116 bajtów
Lewe skojarzenie trójskładnika PHP wymaga nawiasów ... lub określonej kolejności testów.
Pozwoliło to zaoszczędzić dwa bajty wyrażenia w nawiasach.
Prawdopodobnie istnieje podejście iteracyjne, które może pozwolić na dalszą grę w golfa ...
ale nie mogę teraz na to pozwolić .
źródło