Mir ist klar, dass dies ein bisschen mathematisch ist, aber - hier geht es weiter.

In der Mathematik ist die Hyperoperationssequenz eine unendliche Folge von arithmetischen Operationen (Hyperoperationen genannt), die mit der unären Operation des Nachfolgers beginnt und dann mit den binären Operationen der Addition, Multiplikation und Exponentiation fortgesetzt wird, wonach die Sequenz mit weiteren darüber hinausgehenden binären Operationen fortfährt Potenzierung unter Verwendung von Rechtsassoziativität.

Ihr Ziel ist es, ein Programm zu schreiben, das drei ganze Zahlen x, y und n als Eingabe verwendet und das Ergebnis der n-ten Hyperoperation für x und y ausgibt.

Z.B

1 1 1 Ausgänge 2

2 4 4 Ausgänge 65536

3 3 4 Ausgänge 7625597484987

• Das Programm muss in kürzester Zeit geschrieben sein.
• Sie können Eingaben entweder aus STDINoder aus einer Datei vornehmen.
• Bibliotheksfunktionen nicht erlaubt.
• Eingabebeschränkungen: n ist ≥ 1.

http://en.wikipedia.org/wiki/Tetration bietet eine gute Erklärung für den Fall, dass Sie sich nicht darum kümmern können.

Rubin, langsam, 86 84 83 Zeichen

def f x,y,n
n>1?(c=x;2.upto(y){c=f(x,c,n-1)};c):x+y
end
p f *gets.split.map(&:to_i)

Ruby, schnell, 96 94 93 Zeichen

def f x,y,n
n>1?(n>2?(c=x;2.upto(y){c=f(x,c,n-1)};c):x*y):x+y
end
p f *gets.split.map(&:to_i)

Die erste Version ist mit dem letzten Testfall viel zu langsam, daher habe ich eine Version hinzugefügt, die Multiplikation als Basisfall anstelle von Addition verwendet. Die Berechnung der ersten Version dauert ewig 3 3 4. Die zweite ist instanteneous (in der nativen IRB-Konsole; die Webversion ist etwas langsamer).

Hier tauchen einige Schönheiten von Ruby auf:

Fast jede Aussage ist ein Ausdruck in Rubin. Auf diese Weise können Sie Semikolons in den ternären Operator einfügen, vorausgesetzt, Sie haben genügend Klammern herumliegen. Coffeescript hat das ausgeliehen. Es wurde auch Rubys Aufrufsyntax "Keine Parens erforderlich" ausgeliehen.

Implizite Rückgabe: Dies ist eine coole Funktion und folgt aus der vorherigen. In der Tat wird das Starten der letzten Zeile einer Funktion mit returnals lahm angesehen, selbst wenn nicht Golf gespielt wird.

Zahlen sind Objekte in Rubin (gerade nullist ein Objekt). In Ruby haben Ganzzahlen die Methode times, die den an sie übergebenen Block mehrmals ausführt. Dies ist nur eine von Rubys vielen Iteratormethoden. Hier uptokönnen wir mit der Methode zwei weitere Zeichen über dem speichern, was timesuns erlaubt.

einstellige *ist der Splat - Operator hier. Es verwandelt ein Array in eine Argumentliste. Genau wie bei Javascript Function#apply, aber es ist kürzer und besser.

unary &verwandelt eine Prozedur in einen Block. Während :to_ies ein Symbol ist, kann es ziemlich gut in eine Prozedur umgewandelt werden. Es wird nämlich zu einer Prozedur, die to_iihr Argument aufruft und das Ergebnis zurückgibt. Weitere Informationen zum Stapelüberlauf.

Es wäre möglich, es noch schneller zu bekommen, wenn man es n=3als Basisgehäuse verwendet, aber ich fürchte, es wird nicht benötigt. Es würde jedoch nur 11 Zeichen kosten, dank einer anderen Schönheit von Ruby: dem Exponentiationsoperator **. Python hat diesen Operator, aber es ist nicht der erste (wie @ aka.nice feststellte - danke - hatte Fortran diesen Operator bereits).

Online-Ruby-Interpreter hier verfügbar: http://repl.it/Ikj/1

APL, 62

{1=3⌷⍵:2⌷+\⍵⋄0=2⌷⍵:(⍵[3]⌊3)⌷⍵[1],0,1⋄∇⍵[1],(∇⍵-0 1 0),3⌷⍵-1}⎕

{...}⎕: Nimmt ausgewertete Eingaben (durch Leerzeichen getrennte Zahlen ergeben ein numerisches Array) und wendet eine Funktion darauf an.

1=3⌷⍵:: Wenn n gleich 1 ist ...
2⌷+\⍵: Rückgabesumme der ersten 2 Elemente (x + y) ...
⋄0=2⌷⍵:: Andernfalls, wenn y gleich 0 ist ...
(⍵[3]⌊3)⌷⍵[1],0,1: Numerisches Array [x, 0,1] erstellen und Index zurückgeben min(n,3)...
⋄∇⍵[1],(∇⍵-0 1 0),3⌷⍵-1: Andernfalls wird ∇ (x, ∇ (x, y-1, n), n-1) zurückgegeben. (∇ ist Selbstreferenz)

Ich habe einen "Hyper-Raiser" -Operator, der eine Funktion übernimmt und die nächste Hyperoperation zurückgibt

{⍺⍺/⊃⍴/⌽⍵}

Zum Beispiel +{⍺⍺/⊃⍴/⌽⍵}wäre die Multiplikationsfunktion und die +{⍺⍺/⊃⍴/⌽⍵}5 3Ausgänge 15.

Aber ich kann es nicht dazu bringen, sich zu wiederholen. Vielleicht kann es jemand anderes tun.

Python, 83

(Basierend auf der Antwort von Flornquake )

def h(x,y,n):r=n>2;exec"r=h(x,r,n-1);"*y*(n>1);return(x+y,r)[n>1]
print h(*input())

Sehr langsam für große Ergebnisse.

Für 2, 4, 4die Ausgabe ist 65536.

Python, 96 92

def h(x,y,n):r=1;exec(n>2)*y*"r=h(x,r,n-1);";return(r,(x+y,x*y)[n>1])[n<3]
print h(*input())

Eingabe: 3, 3, 4
Ausgabe:7625597484987

Verkürzt mit ein paar Ideen von @ WolframH .

Golfscript, langsam, 39 Zeichen

 ~{\(.{3${[4$\2$4$.~}4$(*}{;;+}if])\;}.~

(Live-Link)

Dies ist der rekursive Standardalgorithmus mit einem Basisfall von n = 1 (Addition) (dh langsam). Das gleiche habe ich in meiner Ruby-Lösung verwendet

Hier ist eine Version mit meinen Anmerkungen (meistens Stapelhaltung). Es enthält keine Optimierung, die ich später hinzugefügt habe:

~{            #read the input and do (x y n f)
 \(.{         #(x y f n-1); if(n-1)
  3${         #(x y f n-1 c)
   4$\2$4$.~  #(x y f n-1 x c n-1 f); call
  }3$(*       #y-1 times
  {\;}4*
 }{           #else
  ;;+         #return (x+y)
 }if
}.~           #once

~ist der Bewertungsoperator. Bei Zeichenfolgen wird die Zeichenfolge als GolfScript-Programm behandelt. Glücklicherweise ist eine durch Leerzeichen getrennte Liste von Ganzzahlen ein gültiges GolfScript-Programm, das diese Ganzzahlen auf den Stapel schiebt. Im Vergleich dazu ist meine vorherige Version der Eingaberoutine ( " "/{~}/aufgeteilt nach Leerzeichen und Auswertung) ziemlich lahm. Bei Funktionen wird die Funktion aufgerufen. Wenn .(Klon) vorangestellt wird , ruft es die Funktion mit sich selbst als erstem Argument auf.

Golfscript scheint nicht gerade für die Erstellung rekursiver Algorithmen geeignet zu sein. Wenn Sie einen rekursiven Algorithmus wünschen, der nicht optimierbar ist, müssen Sie Stapelrahmen erstellen und zerstören, um Ihre Variablen zu erhalten. In den meisten Sprachen erfolgt dies automatisch. In Golfscript müssen Sie die Variablen (eigentlich Stapeleinträge) tatsächlich klonen und die Stapeleinträge zerstören, die Sie nicht mehr benötigen. Golfscript hat kein Konzept für Stapelrahmen. Habe ich gesagt, dass GolfScript eine stapelbasierte Sprache ist?

Die erste Anforderung ist verständlich. Sie müssen die Argumente irgendwie angeben. Es ist nur schön, wenn sie auch ihre ursprünglichen Positionen behalten. Die zweite Anforderung ist unglücklich, insbesondere da sich der Rückgabewert oben auf dem Stapel befindet und Golfscript nicht in der Lage ist, nur ein beliebiges Stapelelement zu löschen. Sie können den Stapel drehen und das neue obere Element verwerfen, aber das baut sich schnell auf. \;ist gut. \;\;\;\;\;ist nicht. Sie können dies \;in einer Schleife tun ( {\;}9*; Kosten: 6 Zeichen, um bis zu 9 Elemente zu verwerfen, oder 7 Zeichen, um bis zu 99 Elemente zu verwerfen), aber wir können es besser machen:

Golfscript verfügt über erstklassige Arrays. Es hat auch die Array-Literal-Syntax [1 2 3 4]. Was unerwartet ist, ist das [und ]ist eigentlich kein Teil der Syntax. Sie sind lediglich zwei Operatoren: [Markiert die aktuelle Position auf dem Stapel und ]sammelt jedes Element, bis es die Markierung für den Start des Arrays findet oder keinen Stapel mehr hat, und verwirft die Markierung. Sie können diese beiden sogar auseinander reißen und sehen, was passiert. Nun, eine ziemlich interessante Sache:

Habe ich gesagt, Golfscript hat kein Konzept für Stapelrahmen? Ich habe gelogen. Dies ist ein Stapelrahmen : [. Sie können alles auf einmal verwerfen : ];. Aber was ist, wenn wir den Rückgabewert behalten wollen? Sie können den Stapelrahmen bei der Funktionseingabe schließen (dann haben wir eine leicht verstümmelte Version von Pass-by-Array - kein interessantes Konzept), oder Sie können den Stapelrahmen schließen und sein letztes Element übernehmen, anstatt ihn vollständig zu verwerfen: ]-1=oder wir kann stattdessen das letzte Element entsperren und dann den Frame verwerfen : ])\;. Sie sind gleich lang, aber letzteres ist etwas kühler, also benutze ich es.

Anstelle von 6 oder 7 Zeichen für eine Bereinigung können wir also 5 verwenden. Ich bin immer noch der Meinung, dass dies mehr Golf sein könnte, aber hey, wir haben einen Charakter gespeichert.

Smalltalk Squeak 4.x schmeckt vielen Bytes!

Ich könnte eine der rekursiven Formen in Integer in 71 Zeichen implementieren

f:y n:n n=1or:[^(2to:y)inject:self into:[:x :i|self f:x n:n-1]].^self+y

Dann kostet mich das Lesen aus einer Datei oder einem FileStream-Standard einen Arm ... Squeak wurde offensichtlich nicht als Skriptsprache entwickelt. Daher werde ich viele Bytes ausgeben, um meine eigenen allgemeinen Dienstprogramme zu erstellen, die nichts mit dem Problem zu tun haben:

Implementieren Sie diese 21-Zeichen-Methode in Stream (um Seaparatoren zu überspringen).

s self skipSeparators

Implementieren Sie diese 20-Zeichen-Methode in Behavior (um eine Instanz aus einem Stream zu lesen).

<s^self readFrom:s s

Dann 28 Zeichen in String (um ein Dateihandle zu erstellen)

f^FileDirectory default/self

Dann 59 Zeichen in FileDirectory (um einen readStream zu erstellen)

r^FileStream concreteStream readOnlyFileNamed:self fullName

Dann 33 Zeichen in BlockClosure (um es n-mal auszuwerten)

*n^(1to:n)collect:[:i|self value]

Dann 63 Zeichen im Array (bewerten Sie das Argument mit dem Empfänger und die Argumente aus dem Array)

`s^self first perform:s asSymbol withArguments:self allButFirst

Lösen Sie dann das Problem, indem Sie dieses 31-Zeichen-Snippet an einer beliebigen Stelle auswerten, um es aus der Datei mit dem Namen x zu lesen

|s|s:='x'f r.[0class<s]*3`#f:n:

Auch ohne die Dienstprogramme zu zählen, sind das bereits 71 + 31 = 102 Zeichen ...

Jetzt, da ich sicher bin, den CodeGolf zu verlieren, habe ich eine lustigere Implementierung in Integer:

doesNotUnderstand:m
    (m selector allSatisfy:[:c|c=$+])or:[^super doesNotUnderstand:m].
    self class compile:
        m selector,'y y=0or:[^(2to:y)inject:self into:[:x :i|self'
        ,m selector allButLast,'x]].^'
        ,(Character digitValue:()asBit)
        ,(m selector size-2min:1)hex last.
    thisContext sender restart

Diese Methode definiert (kompiliert) eine binäre Nachricht aus n +, wenn sie nicht existiert (wird vom Empfänger der Nachricht m nicht verstanden), und startet die Ausführung zu Beginn des Senderkontexts neu. Ich habe zusätzlichen Wagenrücklauf und Leerzeichen zur besseren Lesbarkeit eingefügt.

Beachten Sie, dass dies (m selector size-2min:1)hex lasteine Kurzschlussform von ist (m selector size>2)asBit printString.

Wenn Smalltalk keine bösen Supermächte demonstrieren sollte, könnte die letzte Aussage durch kürzere und einfachere ersetzt werden

^m sendTo:self

Implementieren Sie nun das Dienstprogramm mit 28 Zeichen in Character (um es n-mal in einem String zu wiederholen).

*n^String new:n withAll:self

Bewerten Sie dann diesen Ausdruck mit 43 Zeichen:

|i s|i:=0class.s:='x'f r.[i<s]*2`($+*(i<s))

Wir können mit 10 weiteren Zeichen beschleunigen, indem wir in Integer implementieren:

++y^self*y

und in diesem Fall sind wir auch kürzeren Code haben , weil wir ersetzen können ^',(m selector size-2min:1)hex lastmit^1'

Für einen so hohen Preis arbeitet der Code mit der zweiten Ganzzahl = 0 :)

Groovy - 77

h={x,y,n->n<2?x+y:y<2?x:h(x,h(x,y-1,n),n-1)}
print h(args.collect{it as int})

Hinweis: Für nicht winzige Argumente sind obszöne Mengen an Stapel (und Zeit) erforderlich.

AXIOM Computer Algebra System, Bytes 69

p(x,y,n)==(n<=1=>y+x^n;n=2=>y*x;n=3=>x^y;y<=0=>1;p(x,p(x,y-1,n),n-1))

Prüfung:

(2) -> p(1,1,1)
   (2)  2
                                                 Type: Expression Integer
                                   Time: 0.05 (IN) + 0.03 (OT) = 0.08 sec
(3) -> p(2,4,4)
   (3)  65536
                                                 Type: Expression Integer
                                                              Time: 0 sec
(4) -> p(3,3,4)
   (4)  7625597484987
                                                 Type: Expression Integer
                                                              Time: 0 sec

Dies würde eine gewisse Rekursion beseitigen ... Möglicherweise tausche ich x und y in einer Rückgabe aus ... gibt es andere Testwerte?

APL (NARS), Zeichen 61, Bytes 122

{(x y n)←⍵⋄n≤1:y+x*n⋄n=2:x×y⋄n=3:x*y⋄y≤0:1⋄∇x,(∇x(y-1)n),n-1}

Prüfung:

  h←{(x y n)←⍵⋄n≤1:y+x*n⋄n=2:x×y⋄n=3:x*y⋄y≤0:1⋄∇x,(∇x(y-1)n),n-1}
  h 1 1 1
2
  h 2 4 4
65536
  h 3 4 4
∞
  h 3 3 4
7625597484987