Je me rends compte que c'est un peu mathématique, mais - voilà.

En mathématiques, la séquence d'hyperopération est une séquence infinie d'opérations arithmétiques (appelées hyperopérations) qui commence par l'opération unaire du successeur, puis se poursuit par les opérations binaires d'addition, de multiplication et d'exponentiation, après quoi la séquence se poursuit avec d'autres opérations binaires s'étendant au-delà exponentiation, en utilisant l'associativité droite.

Votre objectif est d'écrire un programme qui prend en entrée trois entiers x, y et n et génère le résultat de la nième hyperopération sur x et y.

Par exemple

1 1 1 sorties 2

2 4 4 sorties 65536

3 3 4 sorties 7625597484987

• Le programme doit être écrit dans le bit de code le plus court.
• Vous pouvez prendre des entrées à partir STDINou à partir d'un fichier.
• Fonctions de bibliothèque non autorisées.
• Contraintes d'entrée: n sera ≥ 1.

http://en.wikipedia.org/wiki/Tetration a une bonne explication au cas où vous ne pourriez pas vous en tenir compte.

Rubis, lent, 86 84 83 caractères

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)

Rubis, rapide, 96 94 93 caractères

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)

La première version est beaucoup trop lente avec le dernier cas de test, j'ai donc ajouté une version qui utilise la multiplication comme cas de base au lieu de l'addition. La première version prend du temps à calculer 3 3 4; la seconde est instantanée (dans la console IRB native; la version web est un peu plus lente).

Plusieurs beautés de Ruby apparaissent ici:

Presque chaque déclaration est une expression en rubis. Ainsi, vous pouvez remplir des points-virgules à l'intérieur de l'opérateur ternaire, à condition que vous ayez suffisamment de parenthèses qui traînent. Coffeescript a emprunté celui-là. Il a également emprunté la syntaxe d'appel "sans parens nécessaire" de Ruby.

Retours implicites: il s'agit d'une fonctionnalité intéressante, qui découle de la précédente. En effet, commencer la dernière ligne d'une fonction avec returnest considéré comme boiteux, même lorsqu'il ne joue pas au golf.

Les nombres sont des objets en rubis (même nullest un objet). En ruby, les entiers ont la méthode times, qui exécute le bloc qui lui est passé plusieurs fois. Ceci n'est qu'une des nombreuses méthodes d'itérateur de Ruby. Ici, la uptométhode nous permet d'enregistrer deux autres caractères sur ce qui timesnous permet.

unaire *est l'opérateur splat ici. Il transforme un tableau en liste d'arguments. Tout comme Javascript Function#apply, mais il est plus court et meilleur.

unaire &transforme une procédure en bloc. Bien que ce :to_isoit un symbole, il se transforme assez bien en procédure. À savoir, il se transforme en une procédure qui fait appel to_ià son argument et renvoie le résultat. Plus d'informations sur Stack Overflow.

Il serait possible de l'obtenir encore plus rapidement en utilisant n=3comme cas de base, mais je crains que ce ne soit pas nécessaire. Cela ne coûterait que 11 caractères, cependant, grâce à une autre beauté de rubis: l'opérateur d'exponentiation **. Python a cet opérateur, mais ce n'est pas le premier (comme l'a noté @ aka.nice - merci -, Fortran avait déjà cet opérateur).

interprète de rubis en ligne disponible ici: http://repl.it/Ikj/1

APL, 62

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

{...}⎕: Prend l'entrée évaluée (les nombres séparés par des espaces sont évalués dans un tableau numérique) et lui applique une fonction.

1=3⌷⍵:: Si n est égal à 1 ...
2⌷+\⍵: Retourne la somme des 2 premiers éléments (x + y) ...
⋄0=2⌷⍵:: Sinon si y est égal à 0 ...
(⍵[3]⌊3)⌷⍵[1],0,1: Crée un tableau numérique [x, 0,1] et retourne l'index min(n,3)...
⋄∇⍵[1],(∇⍵-0 1 0),3⌷⍵-1: Sinon, retournez ∇ (x, ∇ (x, y-1, n), n-1). (∇ est auto-référence)

J'ai un opérateur "hyper-raiser", qui prend une fonction et retourne la prochaine hyperopération

{⍺⍺/⊃⍴/⌽⍵}

Par exemple, +{⍺⍺/⊃⍴/⌽⍵}serait la fonction de multiplication et les +{⍺⍺/⊃⍴/⌽⍵}5 3sorties 15.

Mais je ne peux pas le faire récuser. Peut-être que quelqu'un d'autre peut le faire.

Python, 83

(Basé sur la réponse de 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())

Très lent pour de grands résultats.

Car 2, 4, 4la sortie est 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())

Entrée: 3, 3, 4
Sortie:7625597484987

Raccourci en utilisant quelques idées de @ WolframH .

Golfscript, lent, 39 caractères

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

(lien en direct)

Il s'agit de l'algorithme récursif standard avec un cas de base de n = 1 (addition) (c'est-à-dire lent). Le même que j'ai utilisé dans ma solution Ruby

Voici une version avec mes annotations (principalement la conservation de la pile). Il ne comprend pas une optimisation que j'ai ajoutée plus tard:

~{            #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

~est l'opérateur eval. Dans le cas de chaînes, il traite la chaîne comme un programme GolfScript. Heureusement, une liste d'entiers séparés par des espaces est un programme GolfScript valide qui pousse ces entiers sur la pile. Par rapport à cela, ma version précédente de la routine d'entrée ( " "/{~}/, divisée par espace et eval chacun) est assez boiteuse. En cas de fonctions, il appelle la fonction. Lorsqu'elle est précédée de .(clone), elle appelle la fonction avec elle-même comme premier argument.

Golfscript ne semble pas être parfaitement adapté à la création d'algorithmes récursifs. Si vous voulez un algorithme récursif qui ne soit pas optimisé pour les appels de queue, vous devez créer et détruire des cadres de pile pour préserver vos variables. Dans la plupart des langues, cela se fait automatiquement. Dans golfscript, vous devez réellement cloner les variables (en fait, les entrées de pile) et détruire les entrées de pile dont vous n'avez plus besoin. Golfscript n'a aucun concept de cadres de pile. Ai-je dit que GolfScript est un langage basé sur la pile?

La première exigence est compréhensible. Vous devez en quelque sorte spécifier les arguments. Ce n'est agréable que s'ils conservent également leur position d'origine. La deuxième exigence est regrettable, d'autant plus que la valeur de retour est au sommet de la pile, et golfscript n'a pas la possibilité de supprimer n'importe quel élément de la pile. Vous pouvez faire pivoter la pile et jeter le nouvel élément supérieur, mais cela s'accumule rapidement. \;c'est bien. \;\;\;\;\;n'est pas. Vous pouvez le faire \;en boucle ( {\;}9*; coût: 6 caractères pour éliminer jusqu'à 9 éléments, ou 7 caractères pour supprimer jusqu'à 99 éléments), mais nous pouvons faire mieux:

Golfscript a des tableaux de première classe. Il a également la syntaxe littérale du tableau [1 2 3 4]. Ce qui est inattendu est que [et ]ne sont pas en fait une partie de la syntaxe. Ce ne sont que deux opérateurs: [marque la position actuelle sur la pile, et ]collecte chaque élément jusqu'à ce qu'il trouve la marque de début de tableau ou soit à court de pile, et rejette la marque. Vous pouvez même les déchirer et voir ce qui se passe. Eh bien, une chose assez intéressante:

Ai-je dit que golfscript n'a pas de concept de cadres de pile? J'ai menti. Ceci est un cadre de pile: [. Vous pouvez jeter tout à la fois: ];. Mais que se passe-t-il si nous voulons conserver la valeur de retour? Vous pouvez fermer le cadre de pile à l'entrée de la fonction (alors nous avons une version légèrement modifiée du tableau de bord - ce n'est pas un concept intéressant), ou nous pouvons fermer le cadre de pile et prendre son dernier élément au lieu de le supprimer complètement: ]-1=ou nous peuvent uncons le dernier élément à la place, et puis jeter le cadre: ])\;. Ils ont la même longueur, mais ce dernier est légèrement plus frais, donc je l'utilise.

Donc, au lieu de 6 ou 7 caractères pour faire un nettoyage, nous pouvons le faire avec 5. Je pense toujours que cela pourrait être joué plus, mais bon, nous avons sauvé un personnage.

Smalltalk Squeak 4.x saveur de nombreux octets!

Je pourrais implémenter l'une des formes récursives dans Integer en 71 caractères

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

La lecture d'un fichier ou d'un fichier FileStream stdin me coûtera un bras ... Squeak n'a évidemment pas été conçu comme un langage de script. Je vais donc dépenser de nombreux octets pour créer mes propres utilitaires à usage général sans rapport avec le problème:

Implémenter cette méthode de 21 caractères dans Stream (pour ignorer les Seaparators)

s self skipSeparators

Implémentez cette méthode de 20 caractères dans Behavior (pour lire une instance à partir d'un flux)

<s^self readFrom:s s

Puis 28 caractères en chaîne (pour créer un descripteur de fichier)

f^FileDirectory default/self

Puis 59 caractères dans FileDirectory (pour créer un readStream)

r^FileStream concreteStream readOnlyFileNamed:self fullName

Puis 33 caractères dans BlockClosure (pour l'évaluer n fois)

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

Puis 63 caractères dans le tableau (évaluer l'argument avec le récepteur et les arguments tirés du tableau)

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

puis résolvez le problème en évaluant cet extrait de 31 caractères n'importe où pour lire à partir du fichier nommé x

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

Même sans compter les utilitaires, c'est déjà 71 + 31 = 102 caractères ...

Maintenant, comme je suis sûr de perdre le codeGolf, j'ai une implémentation plus amusante dans 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

Cette méthode définira (compilera) un message binaire en n + s'il n'existe pas (n'est pas compris par le destinataire du message m), et recommencera l'exécution au début du contexte émetteur. J'ai inséré un retour chariot supplémentaire et des espaces pour plus de lisibilité.

Notez que (m selector size-2min:1)hex lastc'est une forme abrégée de (m selector size>2)asBit printString.

Si ce n'était pas pour démontrer les super-pouvoirs maléfiques de Smalltalk, la dernière déclaration pourrait être remplacée par une plus courte et plus simple

^m sendTo:self

Maintenant, implémentez l'utilitaire 28 caractères dans Caractère (pour le répéter n fois dans une chaîne)

*n^String new:n withAll:self

Évaluez ensuite cette expression de 43 caractères:

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

Nous pouvons accélérer avec 10 caractères supplémentaires en implémentant Integer:

++y^self*y

et dans ce cas, nous avons également un code plus court, car nous pouvons remplacer ^',(m selector size-2min:1)hex lastpar^1'

Pour un prix aussi élevé, le code fonctionne avec un deuxième entier = 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})

Remarque: il nécessite des quantités obscènes de pile (et de temps) pour des arguments non minuscules.

Système d'algèbre informatique AXIOM, octets 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))

tester:

(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

Cela éliminerait une certaine récursivité ... Possible que j'échange en x et y en retour ... y a-t-il d'autres valeurs de test?

APL (NARS), caractères 61, octets 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}

tester:

  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