O desafio

Implemente a tetração (aka Power Tower ou Hyperexponentiation) com a menor quantidade de caracteres.

As condições

• Não utilizar o operador 'potência' ou seus equivalentes (tal como pow(x,y), x^y, x**y, etc.)
• Entrada fornecida como: x y(separada por um espaço)
• xé exponenciada por si mesma yvezes.
• Seu método deve ser capaz de calcular pelo menos 4 3(4 exponenciados por ele mesmo 3 vezes)

A pontuação

• Menor pontuação ganha: (# de caracteres)
• Dedução de bônus se você não usar o operador de multiplicação (-5 pontos).
• Não há requisitos de velocidade / memória. Demore o tempo que quiser.

Exemplos

x, 0 -> 1

2, 2 -> 2^2 = 4

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

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

Aberto a sugestões / alterações / perguntas

J, a pontuação é 7 (12 caracteres - 5 pontos para evitar a multiplicação)

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

uso:

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

Apenas algumas dobras aninhadas:

• Usando multiplicação seria */@$~/@$~
• Usar energia seria ^/@$~onde $~cria array, /é uma função fold.

Haskell, 87 85 - 5 == 80 82

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

Não utiliza exponenciação, multiplicação ou adição (!), Apenas lista operações. Demonstração:

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 ... você não disse nada sobre desempenho ou memória, disse? Mas, considerando bilhões de anos e alguns petabytes de RAM, isso ainda produziria o resultado correto (genericLength pode usar um bigInt para contar o comprimento da lista).

GolfScript, 15 18 caracteres

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

Sim, um dos *s é um operador de multiplicação (exercício: qual?), Por isso não me qualifico para o bônus de 5 caracteres. Ainda assim, é apenas um pouco menor que a solução de Peter .

Caso contrário, esta versão anterior de 15 caracteres é a mesma, mas não produz saída quando o segundo argumento é 0. Obrigado a res por detectar o erro.

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

J, 16 19 12 caracteres

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

ou como verbo (17 caracteres):

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

uso:

   h 2 4
65536

ou recebendo informações do teclado ( 24 27 20 caracteres):

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

com agradecimentos a FUZxxl por apontar minha estupidez. :-)

Explicação:

J é lido da direita para a esquerda, então usando 2 4:

/é usado para inserir o verbo $~entre cada par de itens na lista. $~pega o item da esquerda e forma-o $usando o item da direita ( ~inverte os argumentos) - portanto isso seria equivalente ao 4 $ 2que fornece uma lista de 2s com quatro itens 2 2 2 2.

Agora, anexamos 1 à lista 1,~e fazemos a mesma coisa novamente; /insira um verbo */@$~entre cada par de itens na lista. Esse verbo começa da mesma maneira, $~mas desta vez /insere um *entre cada item da lista recém-gerada. O @just garante que */@$~funciona como um verbo em vez de dois. Isso dá 2multiplicado por si só tempo suficiente para ser equivalente a 2^4.

Página de vocabulário de J - Acho divertido resolver problemas com J apenas por causa da maneira diferente que às vezes faz as coisas.

A adição de mais uma iteração para remover o *operador tem 2 problemas

• Ele sai com 17 caracteres ( +/@$~/,@$~/1,~$~/) que, mesmo com o bônus -5, é muito longo
• A memória fica insuficiente se o número for muito grande, por isso não atende ao requisito de poder calcular 4 3

GolfScript (24 caracteres - 5 = 19 pontos)

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

é incrivelmente lento.

(ou 20 caracteres)

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

é muito mais rápido.

Python, 70

Isso usa evalchamadas aninhadas , eventualmente produzindo uma string "a*a*a*a...*a"que é avaliada. Quase metade da pontuação é desperdiçada em obter os argumentos ... embora eu tenha notado que algumas outras soluções não se incomodam com isso.

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

explicação:

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

além disso, mul, high (: = pow), a tetração funciona da mesma maneira. O padrão comum pode ser extraído como método recursivo, que requer dois BigInts e uma função 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(_,_, (_+_))))

Os sublinhados são espaços reservados para algo que é chamado nessa sequência, por exemplo, a adição mais (a, b) = (a + b); portanto ( + ) é uma função que recebe dois argumentos e os adiciona (a + b).

infelizmente, tenho problemas com o tamanho da pilha. Funciona com valores pequenos para 4 (por exemplo: 2) ou se eu reduzir a profundidade em uma etapa:

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

O código original tem 112 caracteres e teria pontuação, se válida, 107. Talvez eu descubra como aumentar a pilha.

O algoritmo expandido pode ser transformado em chamadas recursivas:

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

A chamada tailrecursive é mais longa que o método original, mas não gerou um fluxo de empilhamento na versão longa - no entanto, não gera um resultado em tempo razoável. t (2,4) está bom, mas t (3,3) já foi interrompido por mim após 5 minutos. No entanto, é muito elegante, não é?

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

E agora o mesmo que acima: use a multiplicação fedida (nós até lucramos ao rejeitar o bônus de 5, porque economizamos 7 caracteres: 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,(_*_)))

invocação:

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

tempo de execução: 1ms.

Br ** nfuck, 128-5 = 123 bytes

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

A entrada está na forma de caracteres com pontos de código dos números desejados como entradas. A saída é a mesma.

Uma explicação está chegando quando eu tiver o tempo abaixo. Recebo pontos de bônus por não usar exponenciação, multiplicação ou adição mesmo?

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!

Isso funciona (testado) para x 0, 0 x, x 1, 1 x, x 2, 2 3, e 2 4. Eu tentei 3 3, mas ele durou várias horas sem terminar (na minha implementação em Java - provavelmente não é o ideal) (EDIT: no EsotericIDE de @ Timwi [É ótimo! Vocês devem tentar] também. Sem sorte.). Em teoria, isso funciona até o tamanho da célula da implementação específica.

Python, 161 - 5 (sem * 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

aqui está um bizarro

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

Isso não está de acordo com as regras, mas não está de acordo com o código mais curto, e espero que seja do interesse de alguém.

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

m[m@Sum]

Isso cria uma função de "tetração" quando é executada, mas os argumentos devem ser dados em ordem inversa. Exemplo:

m[m@Sum][3, 4]

1340780792994259709957402499820584612747936582059239337772356144372176 4030073546976801874298166903427690031858186486050853753882811946569946 433649006084096

Haskell:  58.  51 caracteres, com ou sem multiplicação.

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

A definição mais curta vem do inline "bump" e da definição de uma versão personalizada do "iterate". Infelizmente, o resultado é impossivelmente ineficiente, mas começar com (*) em vez de (+) fornece uma velocidade decente. Em 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

Os números devem ser o 1º e o 2º argumento: python this.py 4 3
**operador não usado.
*usava. É bastante trivial de implementar, exatamente como **, mas custa mais 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

EDIT: Mesclou as duas funções pe rem uma, salvando alguns caracteres.
Dos 99 caracteres, 52 fazem o cálculo real (incluindo definições de variáveis). Os outros 47 são para manipulação de entrada e saída.
ERRO: Lida mal com potências de 0 (por exemplo 0 2). Deve encontrar uma correção de custo mínimo. Este não é um bug, eu esqueci que 0 2é indefinido.

Lida com sucesso 4 3e até fornece um resultado exato. No entanto, pode ser impreciso para alguns números menores.
Imprime o número com um 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());
}

Fator, 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 do golfe:

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.

Não removi o operador de multiplicação *. Se fizesse isso, precisaria adicionar alguma lógica, expressando que a soma de uma sequência vazia é 0, não 1. Essa lógica extra custaria mais do que o bônus -5.

Disjuntor de regras, 124 + 10 = 134 caracteres

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

Este programa tem uma pontuação mais baixa, mas o operador de exponenciação ^quebra as regras. As regras dizem "(número de caracteres) + (10 * (número de operadores 'poderosos'))", então apliquei a penalidade de +10. No entanto, as regras também dizem "Não use o operador 'power'"; portanto, qualquer programa que cumpra essa penalidade infringe as regras. Portanto, esse programa de 134 caracteres não é uma resposta correta e devo apresentar meu programa mais longo de 187 caracteres como resposta.

Haskell 110 - 5 = 105

Estilo Peano de Tetração. Esta é a solução mais insana possível, apenas um aviso, mas também evita a adição.

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)

Isso depende de você ter a paciência para digitar os números Peano (e não mostrará a resposta. Se você realmente deseja executá-lo, adicione estas poucas linhas (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

Ruby, 47 46 45

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

Lua: 133 caracteres, sem multiplicação

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)

Inicialmente, eu usava hacks de repetição de string para fazer multiplicação falsa, mas ele gosta de falhar em valores grandes. Eu poderia usar compilação dinâmica e loadstring para torná-lo menor, mas está ficando tarde aqui ... Preciso dormir.

Digitando "4 3" nas saídas stdin:

1.3407807929943e+154

VBA, 90 caracteres

* Talvez o bônus de não multiplicação não seja bom o suficiente. Eu acho que a resposta de não multiplicação é muito mais interessante, mas isso é código de golfe, então não é o melhor. Aqui está uma resposta sem *, e uma resposta melhor (menor e com melhor pontuação) com ela:

90 caracteres, sem operadores de energia, usa multiplicação = 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, sem operadores de energia, sem bônus de multiplicação (-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

OBSERVAÇÃO: O VBA tem problemas para imprimir o número quando o resultado é muito grande (ou seja 4, 3), mas é calculado corretamente; portanto, se, por exemplo, você deseja USAR esse número, é bom seguir em frente. Além disso, até números maiores aumentam (ou seja 3, 4).

Perl 6 , 32 bytes

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

Experimente online!

(1, { [*] a xx $_ } ... *)é uma sequência lenta que gera a torre de energia, cada elemento sendo a lista que consiste no primeiro parâmetro de entrada areplicado ( xx) um número de vezes igual ao elemento anterior ( $_), sendo essa lista reduzida com multiplicação ( [*]). A partir dessa sequência, simplesmente extraímos o b-ésimo elemento.

Cálculo lambda, 10-5

(usando codificação da Igreja e indeces De Bruijn )
λλ(1λ13)λ1

Explicação

Sem 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

Se você definir exp_a(x)=a^xeste programa, define a↑↑b=exp_a^b(1)onde ^bdenota a iteração da função.

Não tenho certeza se isso é permitido, porque caé tecnicamente equivalente a a^ccomo não é um verdadeiro built-in e apenas um efeito colateral da maneira como os números inteiros são codificados no 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') Saídas:

1.3407807929942597e+154

Python (111) (113) não *

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: Tem que adicionar valor inicial, para ajustar t (X, 0) = 1

Haskell: 88-5 caracteres sem multiplicação, 59 caracteres com multiplicação

Sem multiplicação:

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

Provavelmente existem maneiras de jogar um pouco de golfe.

Com multiplicação:

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

E, finalmente, o programa não destruído:

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)

Essa é provavelmente a maneira mais simples de resolver esse problema, que é definir multiplicação como adição repetida, exponenciação como multiplicação repetida e tetração como exponenciação repetida.

Raquete 58 (não *)

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

Lisp comum, 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)))))))

Tentei fazer as multiplicações através da adição repetida, mas eram mais de 5 caracteres. A mesma coisa com macroletes, as declarações não valeram os ganhos.

Outra solução, inspirada na solução python de boothby. É 1 caractere menor que a solução acima.

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

Python 3-68

(incluindo a penalidade de 10 pontos para o operador de energia)

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

Yabasic , 71 bytes

Uma função que recebe entrada ae bcomo uma sequência delimitada por espaço.

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

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

Experimente online!

-5 por evitar *, o que foi mais difícil do que eu esperava. Explode muito rápido e não funciona (a menos que tenha mais memória), mas atende a todos os critérios necessários.