Die Herausforderung

Implementieren Sie die Tetration (auch Power Tower oder Hyperexponentiation genannt) mit der geringsten Anzahl von Zeichen.

Die Bedingungen

• Verwenden Sie nicht das ‚Power‘ Bediener oder ihre Äquivalente (wie zum Beispiel pow(x,y), x^y, x**y, etc.)
• Eingabe erfolgt als: x y(durch ein Leerzeichen getrennt)
• xwird von sich aus ymal potenziert.
• Ihre Methode muss mindestens in der Lage sein zu berechnen 4 3(4 mal für sich selbst potenziert)

Die Wertung

• Die niedrigste Punktzahl gewinnt: ( Anzahl der Charaktere)
• Bonusabzug, wenn Sie den Multiplikationsoperator nicht verwenden (-5 Punkte).
• Keine Geschwindigkeits- / Speicheranforderungen. Nimm so lange du willst.

Beispiele

x, 0 -> 1

2, 2 -> 2^2 = 4

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

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

Offen für Vorschläge / Änderungen / Fragen

J, Punktzahl ist 7 (12 Zeichen - 5 Punkte zur Vermeidung der Multiplikation)

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

Verwendung:

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

Nur ein paar verschachtelte Falten:

• Mit Multiplikation wäre es */@$~/@$~
• Mit Strom wäre es, ^/@$~wo $~Array erstellt wird, /eine Fold-Funktion.

Haskell, 87 85 - 5 == 80 82

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

Uses neither of exponentiation, multiplication or addition (!), just list operations. Demonstration:

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... you didn't say anything about performance or memory, did you? But given enough billions of years and some petabytes of RAM, this would still yield the correct result (genericLength can use a bigInt to count the length of the list).

GolfScript, 15 18 chars

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

Yes, one of the *s is a multiplication operator (exercise: which one?) so I don't qualify for the 5 char bonus. Still, it's just barely shorter than Peter's solution.

This earlier 15-char version is otherwise the same, but produces no output when the second argument is 0. Thanks to r.e.s. for spotting the bug.

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

J, 16 19 12 characters

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

or as a verb (17 characters):

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

usage:

   h 2 4
65536

or taking input from keyboard (24 27 20 characters):

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

with thanks to FUZxxl for pointing out my stupidity. :-)

Explanation:

J is read from right to left, so using 2 4:

/ is used to insert the verb $~ between each pair of items in the list. $~ takes the left item and shapes it $ using the right item (the ~ reverses the arguments) - so this would be equivalent to 4 $ 2 which gives you a list of 2s which is four items long 2 2 2 2.

Now we append 1 to the list 1,~ and then do the same thing again; / insert a verb */@$~ between each pair of items in the list. This verb starts in the same way $~ but this time it / inserts a * between each item of the newly generated list. The @ just makes sure that the */@$~ works as one verb instead of two. This gives 2 multiplied by itself enough times to be equivalent to 2^4.

J's vocabulary page - I find solving problems with J fun just because of the different way it sometimes does things.

Adding one further iteration to remove the * operator has 2 problems

• It comes out at 17 characters (+/@$~/,@$~/1,~$~/) which, even with the -5 bonus, is too long
• It runs out of memory if the number gets too large so doesn't meet the requirement of being able to calculate 4 3

GolfScript (24 chars - 5 = 19 points)

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

is insanely slow.

(or 20 chars)

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

is much faster.

Python, 70

This uses nested eval calls, eventually producing a string "a*a*a*a...*a" which gets evaluated. Almost half of the score is wasted on getting the arguments... though I've noticed that a few other solutions don't bother with that.

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(_,_,(_+_))))

ungolfed:

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 (_, _, (_ + _))))

explanation:

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 all work in the same manner. The common pattern can be extracted as recursive method, which takes two BigInts and a basic function:

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(_,_, (_+_))))

The underlines are placeholder for something which gets called in this sequence, for example the addition plus(a,b)=(a+b); therefore (+) is a function which takes two arguments and adds them (a+b).

unfortunately, I get issues with the stack size. It works for small values for 4 (for example: 2) or if I reduce the depth for one step:

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(_,_,(_+_)))) 

The original code is 112 characters and would score, if valid, 107. Maybe I find out how to increase the stack.

The expanded algorithm can be transformed to tailrecursive calls:

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

The tailrecursive call is longer than the original method, but didn't raise a stackoverflow in the long version - however it doesn't yield a result in reasonable time. t(2,4) is fine, but t(3,3) already was stopped by me after 5 min. However, it is very elegant, isn't it?

// 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,(_+_))))

And now the same as above: use stinky multiplication (we even profit while rejecting the bonus of 5, because we save 7 characters: win=4 chars:)

// 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

runtime: 1ms.

Br**nfuck, 128-5=123 bytes

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

Input is in the form of characters with code points of the numbers desired as inputs. Output is the same.

An explanation is coming when I have the time below. Do I get bonus points for not using exponentiation, multiplication, OR even 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!

This works (tested) for x 0, 0 x, x 1, 1 x, x 2, 2 3, and 2 4. I tried 3 3, but it ran for several hours without finishing (in my Java implementation—probably not optimal) (EDIT: in @Timwi's EsotericIDE [It's great! Y'all should try it] as well. No luck.). In theory, this works up to the cell size of the specific implementation.

Python, 161 - 5 (no * operator) = 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

invoke:

t(2, 4)

Perl, 61 chars

here's a bizarre one

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

This doesn't quite conform to the rules but it is not in contention for the shortest code anyway, and I hope that it will be of interest to someone.

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

m[m@Sum]

This builds a "tetration" function when it is run, but the arguments must be given in reverse order. Example:

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.