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>
Antworten:
Binäre Lambda-Rechnung , 114 Bits = 14,25 Bytes
Hexdump:
Binär:
Erläuterung
Dies ist (λ 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, wobei alle Zahlen als Kirchenzahlen dargestellt werden. Kirchenzahlen sind die Standard-Lambda-Kalkül-Darstellung natürlicher Zahlen und eignen sich gut für dieses Problem, da eine Kirchenzahl durch Funktionsiteration definiert wird: n g ist die n- te Iteration der Funktion g .
Wenn zum Beispiel g die Funktion λ n ist . λ f . 3 ( n f ), die 3 mit einer Kirchenzahl multipliziert, dann λ n . n g 1 ist die Funktion, die 3 zur Potenz einer Kirchenzahl macht. Durch m- maliges Wiederholen dieser Operation erhält man
m (λ g . λ n . n g 1) (λ n . λ f . 3 ( n f )) n = U (3, n , m ).
(Wir verwenden die Multiplikation u (-, -, 0) anstelle der Potenzierung u (-, -, 1) als Basisfall, weil es unangenehm ist, 1 von einer Kirchenzahl zu subtrahieren .)
Ersatz n = 3:
m (& lgr; g . & lgr; n . n g 1) (& lgr; n . & lgr; f . 3 ( n f )) 3 = u (3, 3, m ).
64-maliges Iterieren dieser Operation, beginnend mit m = 4, ergibt
64 (λ m . M (λ g . Λ n . N g 1) (λ n . Λ f . 3 ( n f )) 3) 4 = G .
Um diesen Ausdruck zu optimieren, ersetzen Sie 64 = 4 ^ 3 = 3 4:
3 4 (λ m . M (λ g . Λ n . N g 1) (λ n . Λ f . 3 ( n f )) 3) 4 = G .
Denken Sie daran, 4 = succ 3 = λ f . λ z . f (3 f z ) als Lambda-Argument:
(λ y . 3 y (λ m . m (λ g . λ n . n g 1) (λ n . λ f . 3 ( n f )) 3) y ) (λ f . λ z . f (3 f z )) = G .
Erinnern Sie sich schließlich an 3 = λ f . λ z . f ( f ( f z )) als Lambda-Argument:
(λ 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 .
quelle
14.25 bytes
scheint die Bestenliste durcheinander zu bringen. Es wird analysiert als25 bytes
, und Sie werden daher als zweiter platziert.Haskell, 41 Bytes
Erläuterung:
(`i`1)f n
=i f 1 n
berechnet dien
Iteration der Funktionf
ab1
. Insbesondere ergibt(`i`1)(*3)n
= 3 ^ n und m- maliges Iterieren dieser Konstruktioni(`i`1)(*3)m n
= u (3, n , m ). Wir können neu zu schreiben , daß als(($n).i(`i`1)(*3))m
= U (3, n , m ) und iterieren diese Konstruktion k mal zu erhalteni(($3).i(`i`1)(*3))4 k
= g _ k .quelle
Haskell, 43 Bytes
Es gibt einen besseren Weg, um
g
Inline umzudrehen.46 Bytes:
48 Bytes:
Schreiben Sie einfach die Definitionen auf.
Die Basisfälle sind ein bisschen sauberer bis 0 gesichert, obwohl es keine Bytes spart. Vielleicht wird es einfacher, eine alternative Definition zu schreiben.
quelle
+
, um die Klammern dazwischen zu entfernenm-1
?(`g`3)
, nicht(3`g`)
.Pyth, 25 Bytes
Der erste Teil
M?H.UgbtH*G]3^3G
definiert eine Methodeg(G,H) = u(3,G,H+1)
.Um den ersten Teil zu testen, prüfen Sie, ob
7625597484987=u(3,3,2)=g(3,1)
:g3 1
.Der zweite Teil
ug3tG64 4
beginnt mit der 64-fachenr0 = 4
Berechnungrn = u(3,3,r(n-1)) = g(3,r(n-1))
und gibt den endgültigen Wert aus (r
wird gewähltg
, um Verwechslungen zu vermeiden).Um diesen Teil zu testen, starten aus
r0=2
und dann berechnenr1
:ug3tG1 2
.quelle
^3
↦*3
,tG
↦G
) und ein anderes Byte mit.UgbtH*G]3
↦ verwendene.ugNtHG1
.*G]3
↦ShG
.Sesos , 30 Bytes
Zerlegt
Oder in Brainfuck-Notation:
Testen
Zu berechnen , u (3, n , U (3, n , ... u (3, n , m ) ...)) mit k verschachtelt Anrufen u , ersetzen die ersten drei
add
Befehleadd 4
,add 64
,add 3
mitadd m
,add k
,add n
, respectively. Da Sesos keine Zahlen schneller als in linearer Zeit erstellen kann, sind Sie praktisch auf kleine Werte wie u (3, 2, 2) = 27, u (3, 5, 1) = 243 und u (3, 1) beschränkt , u (3, 1, ... u (3, 1, m ) ...)) = 3.quelle
[-]
mit,
seit EOF ist0
.JavaScript (ES7), 63 Byte
quelle
Brachylog , 57 Bytes
Erwartet keine Eingabe oder Ausgabe und schreibt das Ergebnis in
STDOUT
. Dies führt an einer Stelle zu einem Stapelüberlauf.Um zu überprüfen, ob dies für kleine Werte (z. B.
u(3,3,2)
) funktioniert , können Sie4
den Wert durch den Wert vonm
und64
durch ersetzen1
.Erläuterung
Dies ist im Grunde eine einfache Implementierung der erläuterten Methode zur Berechnung der Zahl.
Hauptprädikat:
Prädikat 1:
Prädikat 2:
quelle
Karamell , 38 Bytes
Dies ist syntaktischer Zucker für den Lambda-Kalkül-Ausdruck 64 (λ m . M (λ f . Λ n . N f 1) (λ n . Λ f . 3 ( n f )) 3) 4, in denen alle Zahlen als dargestellt werden Church Ziffern .
quelle
(n f->3 (n f))
sollte es nicht lesenn-1
?(n f->3 (n f))
ist eine Funktion zur Multiplikation mit drei in den Ziffern der Kirche .Prolog (SWIPL), 129/137 Bytes
Um Grahams Nummer auszugeben, fragen Sie nach
g(64,G).
(wenn die 8 Bytes dieser Abfrage gezählt werden sollen, beträgt die Länge 137 Bytes):Aber wie zu erwarten ist, geht dieser Stapel aus.
Prüfung
Backtracking führt dazu, dass der Stack ausgeht:
Ungolfed
Die ungolfed-Version fügt die allgemeine Aufwärtspfeilnotation hinzu, nicht nur für 3, und verwendet Schnitte und Überprüfungen, um ein Zurückverfolgen und undefinierte Situationen zu vermeiden.
quelle
64
irgendwo in Ihrem Code zu haben?C 161 Bytes
BEARBEITEN: 11 Bytes durch Entfernen von Tabulatoren und Zeilenumbrüchen gespart. BEARBEITEN: thx auhmann hat ein weiteres byte gespeichert und mein programm repariert
quelle
g(int a){if(a==1)return u(3,4);return g(a-1);}
da es überhaupt nicht verwendet wird ... Oder vergessen Sie etwas?return g(a-1)
solltest seinreturn 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 Bytes
Verwendet einen undefinierten Infix-Operator,
±
der nur 1 Byte benötigt, wenn er in ISO 8859-1 codiert ist. Siehe @ Martins Beitrag für weitere Informationen. Mathematica-Funktionen unterstützen den Mustervergleich für ihre Argumente, sodass die beiden Basisfälle separat definiert werden können.quelle
n_ ±m_:=Nest[#±(m-1)&,3,n]
C,
114109 BytesBasierend auf der Antwort von @thepiercingarrow ( Link ) habe ich die Antwort ein bisschen heruntergespielt. Die meisten Einsparungen ergeben sich aus dem Missbrauch der Standard-Typisierung von Argumenten beim Ausführen von K & R-Funktionen und dem Ersetzen von if-Anweisungen durch ternäre Operatoren. Optionale Zeilenumbrüche zwischen den Funktionen zur besseren Lesbarkeit hinzugefügt.
Dank @LeakyNun auf 109 verbessert.
quelle
g(a){return u(3,a<2?4:g(a-1));}
Python, 85 Bytes
Die
v
Funktion definiert die gleiche Funktion wie die in gefunden Dennis Antwort :v(n,m) = u(3,n+1,m+1)
. Dieg
Funktion ist eine Null-indizierte Version der traditionellen Iteration:g(0) = v(2,3), g(n) = v(2,g(n-1))
. Somitg(63)
ist Grahams Nummer. Durch Setzen des Standardwerts desn
Parameters derg
Funktion auf63
kann die gewünschte Ausgabe durch Aufrufen erhalten werdeng()
(ohne Parameter) erhalten werden, wodurch unsere Anforderungen für eine Funktionsübergabe erfüllt werden, für die keine Eingabe erforderlich ist.Überprüfen Sie die
v(2,1) = u(3,3,2)
undv(4,0) = u(3,5,1)
testen Sie die Fälle online: Python 2 , Python 3quelle
g
scheint aus. Sollte nichtv(2,n-1)
seing(n-1)
oder etwas ähnliches?u
und,v
dass es sein sollteg(n-1)-1
.Dyalog APL, 41 Bytes
Testfall:
quelle
1=⍺:3⋄1=⍵:3*⍺
nur1=⍵:3*⍺
(3=3*1
)Ruby, 64 Bytes
Ausleihen aus dem theoretischen Algorithmus zur Berechnung von Grahams Zahl .
Einfach ausgedrückt,
f a = u(3,3,a)
und es gilt dies 64 Mal.quelle
J, 107 Bytes
Ich arbeite daran,
u
auf eine Agenda umzusteigen, aber im Moment reicht es.quelle
u=:3^[`[:(3$:])/[#<:@]@.*@]
(nicht getestet)F #,
111108 BytesBearbeiten
Dies benutzt die unten stehende Funktion, um Grahams Nummer zu berechnen
Hier ist meine vorherige Antwort, die es nicht tat:
Ziemlich einfach. Nur eine Definition der
u
Funktion.Verwendungszweck:
Wenn ich 3 als Wert für a annehmen würde, könnte ich es auf 60 reduzieren:
Verwendungszweck:
quelle
u
. Natürlich können Sie auch Zwischenfunktionen einfügen, z. B.u
mit oder ohne das erste Argument, das auf 3 festgelegt ist.R,
154142128126118 BytesIch habe die Wikipedia-Definition für diese rekursive Funktion verwendet, weil aus irgendeinem Grund die vorgeschlagene Funktion nicht funktioniert hat ... oder ich habe nur Spaß am R-Golf.
UPD: Abgeschnitten von 12 + 14 = 26 Bytes dank eines Tipps von Leaky Nun . Die Vorgängerversion verwendete das sperrige und weniger leistungsfähige
UPD: 2 + 6 + 2 weitere Bytes wurden abgeschnitten (erneut ein Lob an Leaky Nun ), da "if (x)" anstelle von "if (x == 0)" verwendet wurde, da x <0 nie eingegeben wird die Funktion ... richtig?
quelle
u
in der gleichen Taste wie Ihre geändertg
und 6 weitere Bytes gespeichert - großartig!PHP, 114 Bytes
ignoriere die Zeilenumbrüche; Sie dienen nur der Lesbarkeit.
Es ist möglich, den zweiten Fall in den ersten zu integrieren: for
n=1
,3^n
equals3
.Dies spart ein paar Bytes bei - soweit ich sehen kann - allen vorhandenen Antworten; sparte zwei Bytes auf meinem
vorherige Version, 62 + 43 + 11 = 116 Bytes
Die linke Assoziativität von PHP zum Ternären erfordert Klammern ... oder eine bestimmte Testreihenfolge.
Dies sparte zwei Bytes im Ausdruck in Klammern.
Es ist wahrscheinlich ein iterativer Ansatz, der kann weiter Golf spielen lassen ...
aber ich kann nicht jetzt es die Zeit nehmen.
quelle