Le défi

Implémentez la tétration (aka Power Tower ou Hyperexponentiation) avec le moins de caractères.

Les conditions

• Ne pas utiliser l'opérateur « puissance » ou ses équivalents (tels que pow(x,y), x^y, x**y, etc.)
• Entrée donnée comme: x y(séparée par un espace)
• xest exponentiellement par lui-même yfois.
• Votre méthode doit être capable de calculer au moins 4 3(4 exponentiées par elle-même 3 fois)

La notation

• Le score le plus bas gagne: (# de caractères)
• Déduction de bonus si vous n'utilisez pas l'opérateur de multiplication (-5 points).
• Aucune exigence de vitesse / mémoire. Prenez aussi longtemps que vous le souhaitez.

Exemples

x, 0 -> 1

2, 2 -> 2^2 = 4

2, 4 -> 2^(2^(2^2)) = 65536

4, 3 -> 4^(4^4) = 4^256 = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096

Ouvert aux suggestions / modifications / questions

J, le score est de 7 (12 caractères - 5 points pour éviter la multiplication)

+/@$/@$~/@$~

usage:

   4 +/@$/@$~/@$~ 3
1.34078e154
t=.+/@$/@$~/@$~  NB. define a function
   4 t 3
1.34078e154
   2 t 2
4

Juste quelques plis imbriqués:

• En utilisant la multiplication, ce serait */@$~/@$~
• En utilisant l'énergie, ce serait là ^/@$~où $~crée le tableau, /est une fonction de repli.

Haskell, 87 85 - 5 == 80 82

import Data.List
t x=genericLength.(iterate(sequence.map(const$replicate x[]))[[]]!!)

N'utilise ni d'exponentiation, ni de multiplication, ni d'addition (!), Il suffit de lister les opérations. Manifestation:

Prelude> :m +Data.List
Prelude Data.List> let t x=genericLength.(iterate(sequence.map(const$replicate x[]))[[]]!!)
Prelude Data.List> t 2 2
4
Prelude Data.List> t 2 4
65536
Prelude Data.List> t 4 3

...
ahm ... vous n'avez rien dit sur la performance ou la mémoire, n'est-ce pas? Mais étant donné suffisamment de milliards d'années et quelques pétaoctets de RAM, cela donnerait toujours le résultat correct (genericLength peut utiliser un bigInt pour compter la longueur de la liste).

GolfScript, 15 18 caractères

~])*1\+{[]+*{*}*}*

Oui, l'un des *s est un opérateur de multiplication (exercice: lequel?) Donc je ne me qualifie pas pour le bonus de 5 caractères. Pourtant, c'est à peine plus court que la solution de Peter .

Cette version antérieure de 15 caractères est par ailleurs la même, mais ne produit aucune sortie lorsque le deuxième argument est 0. Merci à res d'avoir repéré le bogue.

~])*{[]+*{*}*}*

J, 16 19 12 caractères

*/@$~/1,~$~/

ou comme verbe (17 caractères):

h=:[:*/@$~/1,~$~/

usage:

   h 2 4
65536

ou en prenant la saisie du clavier ( 24 27 20 caractères):

*/@$~/1,~$~/".1!:1]1

avec mes remerciements à FUZxxl pour avoir souligné ma stupidité. :-)

Explication:

J est lu de droite à gauche, donc en utilisant 2 4:

/est utilisé pour insérer le verbe $~entre chaque paire d'éléments dans la liste. $~prend l'élément de gauche et le façonne en $utilisant l'élément de droite (l' ~inverse les arguments) - donc ce serait équivalent à 4 $ 2ce qui vous donne une liste de 2s qui est de quatre éléments 2 2 2 2.

Maintenant, nous ajoutons 1 à la liste 1,~et faisons à nouveau la même chose; /insérez un verbe */@$~entre chaque paire d'éléments de la liste. Ce verbe démarre de la même manière $~mais cette fois il /insère un *entre chaque élément de la liste nouvellement générée. Le @s'assure juste que le*/@$~ fonctionne comme un verbe au lieu de deux. Cela donne 2multiplié par lui-même suffisamment de fois pour être équivalent à 2^4.

Page de vocabulaire de J - Je trouve que résoudre des problèmes avec J est amusant simplement à cause de la manière différente dont il fait parfois les choses.

L'ajout d'une autre itération pour supprimer l' *opérateur a 2 problèmes

• Il sort à 17 caractères (+/@$~/,@$~/1,~$~/ ) ce qui, même avec le bonus de -5, est trop long
• Il manque de mémoire si le nombre devient trop grand et ne répond donc pas à l'exigence de pouvoir calculer 4 3

GolfScript (24 caractères - 5 = 19 points)

~\1{1{0{+}?}?}{@\+@*}:?~

est incroyablement lent.

(ou 20 caractères)

~\1{1{*}?}{@\+@*}:?~

est beaucoup plus rapide.

Python, 70

Cela utilise des evalappels imbriqués , produisant éventuellement une chaîne "a*a*a*a...*a"qui est évaluée. Près de la moitié du score est gaspillée pour obtenir les arguments ... même si j'ai remarqué que quelques autres solutions ne dérangent pas avec ça.

a,b=map(int,raw_input().split())
exec"eval('*'.join('a'*"*b+'1'+'))'*b

Scala: 110

type B=BigInt
def r(a:B,b:B,f:(B,B)=>B):B=if(b>1)f(a,r(a,b-1,f))else a
def h(a:B,b:B)=r(a,b,r(_,_,r(_,_,(_+_))))

non golfé:

type B=BigInt
def recursive (a:B, b:B, f:(B,B)=>B): B = 
  if (b>1) f (a, recursive (a, b-1, f)) 
  else a
recursive (2, 3, recursive (_, _, recursive (_, _, (_ + _))))

explication:

type B=BigInt
def p (a:B, b:B):B = a+b
def m (a:B, b:B):B = if (b>1) p (a, m (a, b-1)) else a
def h (a:B, b:B):B = if (b>1) m (a, h (a, b-1)) else a
def t (a:B, b:B):B = if (b>1) h (a, t (a, b-1)) else a

plus, mul, high (: = pow), tetration fonctionnent tous de la même manière. Le modèle commun peut être extrait en tant que méthode récursive, qui prend deux BigInts et une fonction de base:

def r (a:B, b:B, f:(B,B)=>B):B = 
  if (b>1) f(a, r(a, b-1, f)) else a
r (4, 3, r (_,_, r(_,_, (_+_))))

Les soulignements sont réservés pour quelque chose qui est appelé dans cette séquence, par exemple l'addition plus (a, b) = (a + b); donc ( + ) est une fonction qui prend deux arguments et les ajoute (a + b).

malheureusement, j'ai des problèmes avec la taille de la pile. Cela fonctionne pour de petites valeurs pour 4 (par exemple: 2) ou si je réduis la profondeur pour une étape:

def h(a:B,b:B)=r(a,b,r(_,_,(_*_))) // size -7, penalty + 5
def h(a:B,b:B)=r(a,b,r(_,_,r(_,_,(_+_)))) 

Le code d'origine est de 112 caractères et marquerait, s'il était valide, 107. Peut-être que je trouverai comment augmenter la pile.

L'algorithme étendu peut être transformé en appels récursifs:

type B=BigInt
def p(a:B,b:B):B=a+b
import annotation._
@tailrec
def m(a:B,b:B,c:B=0):B=if(b>0)m(a,b-1,p(a,c))else c
@tailrec
def h(a:B,b:B,c:B=1):B=if(b>0)h(a,b-1,m(a,c))else c
@tailrec
def t(a:B,b:B,c:B=1):B=if(b>0)t(a,b-1,h(a,c))else c

L'appel tailrecursive est plus long que la méthode d'origine, mais n'a pas déclenché de stackoverflow dans la version longue - mais il ne donne pas de résultat dans un délai raisonnable. t (2,4) est bien, mais t (3,3) a déjà été arrêté par moi après 5 min. Mais c'est très élégant, non?

// 124 = 119-5 bonus
type B=BigInt
def r(a:B,b:B,c:B,f:(B,B)=>B):B=if(b>0)r(a,b-1,f(a,c),f)else c
def t(a:B,b:B)=r(a,b,1,r(_,_,1,r(_,_,0,(_+_))))

Et maintenant la même chose que ci-dessus: utilisez la multiplication puante (nous profitons même en rejetant le bonus de 5, car nous économisons 7 caractères: win = 4 caractères :)

// 115 without bonus
type B=BigInt
def r(a:B,b:B,c:B,f:(B,B)=>B):B=if(b>0)r(a,b-1,f(a,c),f)else c
def t(a:B,b:B)=r(a,b,1,r(_,_,1,(_*_)))

invocation:

timed ("t(4,3)")(t(4,3)) 
t(4,3): 1
scala> t(4,3)
res89: B = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096

durée d'exécution: 1 ms.

Br ** nfuck, 128-5 = 123 octets

+<<+<<,<,[>[>+>>+<<<-]>[<+>-]>[>[>>+>+<<<-]>>>[<<<+>>>-]<<[>[>+>+<<-]>>[<<+>>-]<<<-]>[-]>[<<+>>-]<<<<-]>>[<<+>>-]+<[-]<<<<-]>>>.

L'entrée se présente sous la forme de caractères avec des points de code des nombres souhaités comme entrées. La sortie est la même.

Une explication arrive quand j'ai le temps ci - dessous. Est-ce que j'obtiens des points bonus pour ne pas utiliser l'exponentiation, la multiplication OU même l'addition?

Cell 3 (0-indexed) is the running total x.
This calculates the nth tetration of a.

+<<+<<,<,                                       Initialize tape with [n, a, 0, 1, 0, 1]
[                                               While n:
  >[>+>>+<<<-]>[<+>-]                             Copy a 3 cells to right: [n, a, 0, x, a, 1]
  >[                                              While x:
    >[>>+>+<<<-]>>>[<<<+>>>-]                       Copy a 2 cells to right: [n, a, 0, x, a, 1, a, 0]
    <<[>[>+>+<<-]>>[<<+>>-]<<<-]                    Cell 7 = prod(cell 5, cell 6)
    >[-]>[<<+>>-]<<<<-]                             Move this value to cell 5. End while.
  >>[<<+>>-]+<[-]<<<<-]                           Update x to result of exponentiation. End while.
>>>.                                            Print the result!

Pour cette œuvres (testé) x 0, 0 x, x 1, 1 x, x 2, 2 3et 2 4. J'ai essayé 3 3, mais cela a fonctionné pendant plusieurs heures sans terminer (dans mon implémentation Java — probablement pas optimal) (EDIT: dans @ Timwi's EsotericIDE [C'est génial! Vous devriez tous l'essayer] aussi. Pas de chance.). En théorie, cela fonctionne jusqu'à la taille de cellule de l'implémentation spécifique.

Python, 161-5 (pas d'opérateur *) = 156

r=xrange
def m(x,y):
 i=0
 for n in r(y):i+=x
 return i
def e(x,y):
 i=1
 for n in r(1,y+1):i=m(i,x)
 return i
def t(x,y):
 i=1
 for n in r(y):i=e(x,i)
 return i

invoquer:

t(2, 4)

Perl, 61 caractères

en voici une bizarre

sub t
{
  ($x,$y,$z)=@_;
  $y>1&&t($x,$y-1,eval$x."*$x"x($z-1||1))||$z
}

usage:

print t(2,4,1)

Mathematica, 40 33

Ce n'est pas tout à fait conforme aux règles, mais ce n'est pas de toute façon en lice pour le code le plus court, et j'espère que cela intéressera quelqu'un.

m@f_:=Fold[f,1,#2~Table~{#}]&;

m[m@Sum]

Cela crée une fonction de "tétration" lors de son exécution, mais les arguments doivent être donnés dans l'ordre inverse. Exemple:

m[m@Sum][3, 4]

1340780792994259709957402499820584612747936582059239337772356144372176 4030073546976801874298166903427690031858186486050853753882811946569946 433649006084096

Haskell:  58  51 chars, with or without multiplication.

i f x 1=x;i f x n=f$i f x$n-1
t=i(\o n->i(o n)n)(+)4

Ungolfed:

bump op n a = iterate (op n) n !! (fromIntegral $ a-1)
tetrate = iterate bump (+) !! 3

Shorter definition comes from inlining “bump”, and defining a custom version of “iterate”. Unfortunately the result is impossibly inefficient, but starting with (*) instead of (+) gives decent speed. In ghci:

Prelude> let i f x 1=x;i f x n=f$i f x$n-1
(0.00 secs, 1564024 bytes)
Prelude> let t=i(\o n->i(o n)n)(*)3
(0.00 secs, 1076200 bytes)
Prelude> t 4 3
13407807929942597099574024998205846127479365820592393377723561443721764030073546
976801874298166903427690031858186486050853753882811946569946433649006084096
(0.01 secs, 1081720 bytes)

Ruby 66 59 characters

def e(x,y)
r=1
(1..y).each{t=x
(2..r).each{t*=x}
r=t}
r
end

Python, 112 chars

The numbers should be the 1st and 2nd argument: python this.py 4 3
** operator not used.
* used. It's quite trivial to implement, exactly like **, but costs more than 5 chars.

import sys
p=lambda y:y and x*p(y-1)or 1
t=lambda y:y>1 and p(t(y-1))or x
x,y=map(long,sys.argv[1:])
print t(y)

C, 117 105 99 chars

EDIT: Merged the two functions p and r into one, saving some chars.
Of 99 chars, 52 do the actual calculation (including variable definitions). The other 47 are for handling input and output.
BUG: Badly handles powers of 0 (e.g. 0 2). Should find a minimum cost fix. This isn't a bug, I forgot that 0 2 is undefined.

Successfully handles 4 3, and even gives an exact result. However, can be inaccurate for some smaller numbers.
Prints the number with a trailing .000000.

x,y,z;
double R(){return--y?!z?y=R(),R(z=1):x*R():x;}
main(){
    scanf("%d%d",&x,&y);
    printf("%f\n",R());
}

Factor, 187 characters

USING: eval io kernel locals math prettyprint sequences ;
IN: g
:: c ( y x o! -- v )
o 0 = [ x y * ] [ o 1 - o!
y x <repetition> 1 [ o c ] reduce ] if ;
contents eval( -- x y ) swap 2 c .

Before golf:

USING: eval io kernel locals math prettyprint sequences ;
IN: script

! Calculate by opcode:
!   0 => x * y, multiplication
!   1 => x ^ y, exponentiation
!   2 => x ^^ y, tetration
:: calculate ( y x opcode! -- value )
    opcode 0 = [
        x y *
    ] [
        ! Decrement the opcode. Tetration is repeated exponentiation,
        ! and exponentiation is repeated multiplication.
        opcode 1 - opcode!

        ! Do right-associative reduction. The pattern is
        !   seq reverse 1 [ swap ^ ] reduce
        ! but a repetition equals its own reverse, and 'calculate'
        ! already swaps its inputs.
        y x <repetition> 1 [ opcode calculate ] reduce
    ] if ;

contents eval( -- x y )         ! Read input.
swap 2 calculate .              ! Calculate tetration. Print result.

I did not remove the multiplication operator *. If I did so, then I would need to add some logic expressing that the sum of an empty sequence is 0, not 1. This extra logic would cost more than the -5 bonus.

Rule breaker, 124 + 10 = 134 characters

USING: eval kernel math.functions prettyprint sequences ;
contents eval( -- x y ) swap <repetition> 1 [ swap ^ ] reduce .

This program has a lower score, but the exponentiation operator ^ breaks the rules. The rules say "(# of characters) + (10 * (# of 'power' operators))", so I applied the +10 penalty. However, the rules also say "Don't use the 'power' operator", so any program taking this penalty does break the rules. Therefore, this program of 134 characters is not a correct answer, and I must present my longer program of 187 characters as my answer.

Haskell 110 - 5 = 105

Tetration Peano Style. This is the most insanely slow solution possible, just a warning, but also avoids even addition.

data N=Z|S N
a&+Z=a
a&+S b=S$a&+b
_&*Z=Z
a&*S b=a&+(a&*b)
_&^Z=S Z
a&^S b=a&*(a&^b)
_&>Z=S Z
a&>S b=a&^(a&>b)

This relies on you having the patience to type out Peano numbers (and won't show the answer, If you actually want to run it, add these few lines (90 chars):

f 0=Z
f a=S$f$a-1
t Z=0
t(S a)=1+t a
main=interact$show.f.(\[x,y]->x&>y).map(f.read).words

Ruby, 47 46 45

t=->x,n{r=x;2.upto(n){r=([x]*r).inject :*};r}

Lua: 133 chars, multiplication-less

a,b=io.read():match"(%d+) (%d+)"a,b,ba=a+0,b+0,a for i=1,b-1 do o=1 for i=1,a do o=o+o for i=1,ba-b do o=o+o end end a=o end print(o)

I was originally going to use string repetition hacks to do fake multiplication, but it likes to fail on large values. I could possibly use dynamic compilation and loadstring to make it smaller, but it's getting late here... I need sleep.

Entering "4 3" into stdin outputs:

1.3407807929943e+154

VBA, 90 Chars

*Perhaps the no multiplication bonus is not good enough. I think the no multiplication answer is much more interesting, but this is code golf, so it's not the best. Here's an answer without *, and a better (shorter, and better scoring) answer with it:

90 chars, no power operators, uses multiplication = 90

Sub c(x,y)
f=IIf(y,x,1):For l=2 To y:b=x:For j=2 To f:b=b*x:Next:f=b:Next:MsgBox f
End Sub

116 chars, no power operators, no multiplication bonus (-5) = 111

Sub c(x,y)
f=IIf(y,x,1):For l=2 To y:b=x:For j=2 To f:For i=1 To x:a=a+b:Next:b=a:a=0:Next:f=b:Next:MsgBox f
End Sub

NOTE: VBA has issues printing the number when the result is very large (i.e. 4, 3), but it does calculate correctly, so if, for example, you wanted to USE that number, you would be good to go. Also, even BIGGER numbers overflow (i.e. 3, 4).

Perl 6, 32 bytes

->\a,\b{(1,{[*] a xx$_}...*)[b]}

Try it online!

(1, { [*] a xx $_ } ... *) is a lazy sequence that generates the power tower, each element being the a list which consists of the first input parameter a replicated (xx) a number of times equal to the previous element ($_), that list then being reduced with multiplication ([*]). From that sequence we simply pluck out the b-th element.

Lambda calculus, 10-5

(using Church encoding and De Bruijn indeces)
λλ(1λ13)λ1

Explanation

Without De Bruijn indeces: λa,b.(b λc.ca)λc.c:

λa,b.                                                 define the anonymous function f(a,b)=
     (b                                                apply the following function b times
        λc.                                                    the anonymous function g(c)=
           ca)                 apply c to a because of church encoding this is equal to a^c
              λc.c                              the identity function, 1 in church encoding

If you define exp_a(x)=a^x this program defines a↑↑b=exp_a^b(1) where ^b denotes function itteration.

I'm not sure if this is allowed because ca is technically equivalent to a^c how ever it is not a real built-in and only a side effect of the way integers are encoded in lambda calculus.

Javascript: 116 chars

function t(i){y=i.split(' ');a=y[0];b=y[1];return+b&&p(a,t(a+' '+(b-1)))||1}function p(a,b){return+b&&a*p(a,b-1)||1}

t('4 3') Outputs:

1.3407807929942597e+154

Python (111) (113) no *

r=lambda x,y:(x for _ in range(y));t=lambda x,y:reduce(lambda y,x:reduce(lambda x,y:sum(r(x,y)),r(x,y)),r(x,y),1)

6***3 - 36k digits))

Upd: Have to add initial value, to fit t(X,0)=1

Haskell: 88-5 chars without multiplication, 59 chars with multiplication

Without multiplication:

h x y=foldr(\x y->foldl(\x y->foldl(+)0(replicate x y))1(replicate y x))1(replicate y x)

There are probably ways that I could golf that down a little.

With multiplication:

h x y=foldr(\x y->foldl(*)1(replicate y x))1(replicate y x)

And finally, the ungolfed program:

mult x y = foldl (+) 0 (replicate x y)
expo x y = foldl (mult) 1 (replicate y x)
h x y = foldr (expo) 1 (replicate y x)

This is probably the simplest way to do this problem, which is defining multiplication as repeated addition, exponentiation as repeated multiplication, and tetration as repeated exponentiation.

Racket 58 (no *)

(define(t x y)(if(= y 0)1(for/product([i(t x(- y 1))])x)))

Common Lisp, 85 chars

(lambda(b c)(let((r b)u)(dotimes(c c r)(setf u 1 r(dotimes(c b u)(setf u(* u r)))))))

I tried doing the multiplications through repeated addition, but it was way more than 5 characters. Same thing with macrolets, the declarations were not worth the gains.

Another solution, inspired by boothby's python solution. It's 1 character less than the above solution.

(lambda(a b)(eval`(*,@(loop for x below b nconc(loop for x below a nconc`(,a,a))))))

Python 3 – 68

(including the 10-point penalty for the power operator)

a,b=input().split()
r=1
exec("r=%s**r;"%a*int(b))
print(r)

Yabasic, 71 bytes

A function that takes input a and b as a space delimited string.

Input""a,b
d=a^(b>0)
For i=2To b
c=a
For j=2To d
c=c*a
Next
d=c
Next
?d

Try it online!

R, 71 - 5 = 66 bytes

function(x,y,b=x){for(i in 2:y)b=cumprod(z<-rep(x,b))[sum(z|1)];cat(b)}

Try it online!

-5 for avoiding *, which was harder than I expected. It explodes really fast and won't work (unless it had more memory) but it satisfies all necessary criteria.