El reto

Implemente la tetración (también conocida como Power Tower o Hyperexponentiation) con la menor cantidad de caracteres.

Las condiciones

• No utilice el operador 'poder' o sus equivalentes (como por ejemplo pow(x,y), x^y, x**y, etc.)
• Entrada dada como: x y(separada por un espacio)
• xse expone por sí mismo yveces.
• Su método debe poder calcular al menos 4 3(4 exponenciado por sí mismo 3 veces)

La puntuación

• La puntuación más baja gana: (# de caracteres)
• Deducción de bonificación si no utiliza el operador de multiplicación (-5 puntos).
• No hay requisitos de velocidad / memoria. Tome todo el tiempo que sea necesario.

Ejemplos

x, 0 -> 1

2, 2 -> 2^2 = 4

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

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

Abierto a sugerencias / alteraciones / preguntas

J, el puntaje es 7 (12 caracteres - 5 puntos por evitar la multiplicación)

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

uso:

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

Solo algunos pliegues anidados:

• Usando la multiplicación sería */@$~/@$~
• El uso de energía sería ^/@$~donde $~crea una matriz, /es una función de plegado.

Haskell 87 85 - 5 == 80 82

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

No utiliza exponenciación, multiplicación o suma (!), Solo enumera las operaciones. Demostración:

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 ... no dijiste nada sobre rendimiento o memoria, ¿verdad? Pero dados suficientes miles de millones de años y algunos petabytes de RAM, esto aún arrojaría el resultado correcto (genericLength puede usar un bigInt para contar la longitud de la lista).

GolfScript, 15 18 caracteres

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

Sí, uno de los *s es un operador de multiplicación (ejercicio: ¿cuál?), Así que no califico para el bono de 5 char. Aún así, es apenas más corto que la solución de Peter .

Esta versión anterior de 15 caracteres es igual, pero no produce resultados cuando el segundo argumento es 0. Gracias a res por detectar el error.

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

J, 16 19 12 caracteres

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

o como verbo (17 caracteres):

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

uso:

   h 2 4
65536

o tomando la entrada del teclado ( 24 27 20 caracteres):

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

Gracias a FUZxxl por señalar mi estupidez. :-)

Explicación:

J se lee de derecha a izquierda, así que usa 2 4:

/se usa para insertar el verbo $~entre cada par de elementos en la lista. $~toma el elemento izquierdo y lo forma $usando el elemento correcto ( ~invierte los argumentos), por lo que esto sería equivalente a lo 4 $ 2que le da una lista de 2s que tiene cuatro elementos de largo 2 2 2 2.

Ahora agregamos 1 a la lista 1,~y luego hacemos lo mismo nuevamente; /inserte un verbo */@$~entre cada par de elementos en la lista. Este verbo comienza de la misma manera, $~pero esta vez /inserta un *entre cada elemento de la lista recién generada. El @solo se asegura de que */@$~funcione como un verbo en lugar de dos. Esto da 2multiplicado por sí mismo suficientes veces para ser equivalente a 2^4.

Página de vocabulario de J : encuentro que resolver problemas con J es divertido solo por la forma diferente en que a veces hace las cosas.

Agregar una iteración adicional para eliminar el *operador tiene 2 problemas

• Sale con 17 caracteres ( +/@$~/,@$~/1,~$~/) que, incluso con el bonus de -5, es demasiado largo
• Se queda sin memoria si el número es demasiado grande, por lo que no cumple con el requisito de poder calcular 4 3

GolfScript (24 caracteres - 5 = 19 puntos)

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

es increíblemente lento

(o 20 caracteres)

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

Es mucho más rápido.

Python, 70

Esto usa evalllamadas anidadas , y finalmente produce una cadena "a*a*a*a...*a"que se evalúa. Casi la mitad del puntaje se desperdicia en obtener los argumentos ... aunque he notado que algunas otras soluciones no se molestan con eso.

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

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

explicación:

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, todos funcionan de la misma manera. El patrón común se puede extraer como método recursivo, que requiere dos BigInts y una función básica:

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

Los subrayados son marcadores de posición para algo que se llama en esta secuencia, por ejemplo, la suma más (a, b) = (a + b); por lo tanto ( + ) es una función que toma dos argumentos y los agrega (a + b).

desafortunadamente, tengo problemas con el tamaño de la pila. Funciona para valores pequeños para 4 (por ejemplo: 2) o si reduzco la profundidad en un paso:

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

El código original tiene 112 caracteres y, si es válido, su puntaje sería 107. Quizás descubra cómo aumentar la pila.

El algoritmo expandido se puede transformar en llamadas recursivas de cola:

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

La llamada tailrecursive es más larga que el método original, pero no aumentó el flujo de stackover en la versión larga; sin embargo, no produce un resultado en un tiempo razonable. t (2,4) está bien, pero t (3,3) ya fue detenido por mí después de 5 min. Sin embargo, es muy elegante, ¿no?

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

Y ahora lo mismo que antes: use una multiplicación apestosa (incluso nos beneficiamos al rechazar la bonificación de 5, porque ahorramos 7 caracteres: win = 4 caracteres :)

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

invocación:

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

Tiempo de ejecución: 1 ms.

Br ** nfuck, 128-5 = 123 bytes

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

La entrada es en forma de caracteres con puntos de código de los números deseados como entradas. La salida es la misma.

Viene una explicación cuando tengo el tiempo a continuación. ¿Recibo puntos de bonificación por no usar exponenciación, multiplicación O incluso suma?

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!

Estos trabajos (pruebas) para x 0, 0 x, x 1, 1 x, x 2, 2 3, y 2 4. Lo intenté 3 3, pero funcionó durante varias horas sin terminar (en mi implementación de Java, probablemente no sea óptima) (EDITAR: en @ Timwi EsotericIDE [¡Es genial! Todos deberían intentarlo] también. Sin suerte). En teoría, esto funciona hasta el tamaño de celda de la implementación específica.

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

invocar:

t(2, 4)

Perl, 61 caracteres

aquí hay una extraña

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

uso:

print t(2,4,1)

Mathematica , 40 33

Esto no se ajusta a las reglas, pero de todos modos no está en disputa por el código más corto, y espero que sea de interés para alguien.

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

m[m@Sum]

Esto crea una función de "tetración" cuando se ejecuta, pero los argumentos deben darse en orden inverso. Ejemplo:

m[m@Sum][3, 4]

1340780792994259709957402499820584612747936582059239337772356144372176 4030073546976801874298166903427690031858186486050853753882811946569946 433649006084096

Haskell  58  51 caracteres, con o sin multiplicación.

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

Sin golf:

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

La definición más corta proviene de la inclusión de "bump" y de la definición de una versión personalizada de "iterate". Desafortunadamente, el resultado es imposiblemente ineficiente, pero comenzar con (*) en lugar de (+) da una velocidad decente. En 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 caracteres

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

Python, 112 caracteres

Los números deben ser el primer y segundo argumento: python this.py 4 3
**operador no utilizado.
*usado. Es bastante trivial de implementar, exactamente igual **, pero cuesta más de 5 caracteres.

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 caracteres

EDITAR: se ha unido las dos funciones py ren uno, ahorrando algunos caracteres.
De 99 caracteres, 52 hacen el cálculo real (incluidas las definiciones de variables). Los otros 47 son para manejar entradas y salidas.
ERROR: Maneja mal las potencias de 0 (por ejemplo 0 2). Debería encontrar una solución de costo mínimo. Esto no es un error, olvidé que 0 2no está definido.

Maneja con éxito 4 3, e incluso da un resultado exacto. Sin embargo, puede ser inexacto para algunos números más pequeños.
Imprime el número con un final .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 caracteres

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 .

Antes del 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.

No eliminé el operador de multiplicación *. Si lo hiciera, necesitaría agregar algo de lógica que exprese que la suma de una secuencia vacía es 0, no 1. Esta lógica adicional costaría más que la bonificación de -5.

Rompe reglas, 124 + 10 = 134 caracteres

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

Este programa tiene una puntuación más baja, pero el operador de exponenciación ^rompe las reglas. Las reglas dicen "(# de caracteres) + (10 * (# de operadores 'poderosos'))", así que apliqué la penalización +10. Sin embargo, las reglas también dicen "No use el operador 'poderoso' ', por lo que cualquier programa que tome esta penalidad infringe las reglas. Por lo tanto, este programa de 134 caracteres no es una respuesta correcta, y debo presentar mi programa más largo de 187 caracteres como respuesta.

Haskell 110 - 5 = 105

Tetración Estilo Peano. Esta es la solución más lenta posible, solo una advertencia, pero también evita incluso la adición.

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)

Esto depende de que tengas paciencia para escribir números de Peano (y no mostrará la respuesta, si realmente quieres ejecutarlo, agrega estas pocas líneas (90 caracteres):

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

Rubí, 47 46 45

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

Lua: 133 caracteres, sin multiplicación

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)

Originalmente iba a usar hacks de repetición de cuerdas para hacer una multiplicación falsa, pero le gusta fallar en valores grandes. Posiblemente podría usar la compilación dinámica y la cadena de carga para hacerlo más pequeño, pero se está haciendo tarde aquí ... Necesito dormir.

Ingresando "4 3" en salidas stdin:

1.3407807929943e+154

VBA, 90 caracteres

* Quizás el bono sin multiplicación no sea lo suficientemente bueno. Creo que la respuesta sin multiplicación es mucho más interesante, pero este es el código de golf, por lo que no es el mejor. Aquí hay una respuesta sin ella *, y una mejor (más corta y mejor puntuación) con ella:

90 caracteres, sin operadores de potencia, usa multiplicación = 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 caracteres, sin operadores de potencia, sin bonificación de multiplicación (-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

NOTA: VBA tiene problemas para imprimir el número cuando el resultado es muy grande (es decir 4, 3), pero se calcula correctamente, por lo que si, por ejemplo, quisiera USAR ese número, estaría listo. Además, incluso los números MÁS GRANDES se desbordan (es decir 3, 4).

Perl 6 , 32 bytes

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

Pruébalo en línea!

(1, { [*] a xx $_ } ... *)es una secuencia perezosa que genera la torre de energía, cada elemento es una lista que consiste en el primer parámetro de entrada areplicado ( xx) varias veces igual al elemento anterior ( $_), esa lista luego se reduce con multiplicación ( [*]). De esa secuencia simplemente sacamos el belemento -th.

Cálculo lambda, 10-5

(usando la codificación de Church y De Bruijn indeces )
λλ(1λ13)λ1

Explicación

Sin 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

Si define exp_a(x)=a^xeste programa, define a↑↑b=exp_a^b(1)dónde ^bdenota la función iteración.

No estoy seguro de si esto está permitido porque caes técnicamente equivalente a la a^cforma en que no es un verdadero incorporado y solo un efecto secundario de la forma en que los enteros se codifican en el cálculo lambda.

Javascript: 116 caracteres

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') Salidas:

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 dígitos))

Upd: tiene que agregar valor inicial, para ajustar t (X, 0) = 1

Haskell: 88-5 caracteres sin multiplicación, 59 caracteres con multiplicación

Sin multiplicación:

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

Probablemente hay maneras en que podría jugar golf un poco más abajo.

Con multiplicación:

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

Y finalmente, el programa sin golf:

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)

Esta es probablemente la forma más simple de resolver este problema, que es definir la multiplicación como suma repetida, la exponenciación como multiplicación repetida y la tetración como exponenciación repetida.

Raqueta 58 (no *)

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

Lisp común, 85 caracteres

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

Intenté hacer las multiplicaciones mediante la suma repetida, pero tenía más de 5 caracteres. Lo mismo con los macrolets, las declaraciones no valían las ganancias.

Otra solución, inspirada en la solución de pitón de boothby. Es 1 carácter menos que la solución anterior.

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

Python 3 - 68

(incluida la penalización de 10 puntos para el operador eléctrico)

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

Yabasic , 71 bytes

Una función que toma entrada ay bcomo una cadena delimitada por espacios.

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

Pruébalo en línea!

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)}

Pruébalo en línea!

-5 por evitar *, que fue más difícil de lo que esperaba. Explota muy rápido y no funcionará (a menos que tenga más memoria) pero satisface todos los criterios necesarios.