Tantangan

Terapkan tetrasi (alias Power Tower atau Hyperexponentiation) dengan jumlah karakter paling sedikit.

Ketentuannya

• Jangan menggunakan 'kekuatan' operator atau setara (seperti pow(x,y), x^y, x**y, dll)
• Input diberikan sebagai: x y(dipisahkan oleh spasi)
• xadalah eksponensial dengan ywaktu itu sendiri .
• Metode Anda harus dapat menghitung setidaknya 4 3(4 kali dengan sendirinya 3 kali)

Skor

• Kemenangan skor terendah: (# karakter)
• Pengurangan bonus jika Anda tidak menggunakan operator perkalian (-5 poin).
• Tidak ada persyaratan Kecepatan / Memori. Ambil selama yang Anda inginkan.

Contohnya

x, 0 -> 1

2, 2 -> 2^2 = 4

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

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

Terbuka untuk saran / perubahan / pertanyaan

J, skor 7 (12 karakter - 5 poin untuk menghindari perkalian)

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

pemakaian:

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

Hanya beberapa lipatan bersarang:

• Menggunakan perkalian akan menjadi */@$~/@$~
• Menggunakan kekuatan itu akan menjadi ^/@$~tempat $~menciptakan array, /adalah fungsi lipat.

Haskell, 87 85 - 5 == 80 82

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

Tidak menggunakan eksponensial, perkalian, atau penambahan (!), Cukup daftarkan operasi. Demonstrasi:

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 ... Anda tidak mengatakan apa-apa tentang kinerja atau memori, bukan? Tetapi mengingat cukup milyaran tahun dan beberapa petabyte RAM, ini masih akan menghasilkan hasil yang benar (genericLength dapat menggunakan bigInt untuk menghitung panjang daftar).

GolfScript, 15 18 karakter

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

Ya, salah satunya *adalah operator perkalian (latihan: yang mana?) Jadi saya tidak memenuhi syarat untuk bonus 5 char. Meski begitu, ini hanya lebih pendek dari solusi Peter .

Versi 15-char sebelumnya ini adalah sama, tetapi tidak menghasilkan output ketika argumen kedua adalah 0. Terima kasih kepada res karena telah menemukan bug.

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

J, 16 19 12 karakter

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

atau sebagai kata kerja (17 karakter):

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

pemakaian:

   h 2 4
65536

atau mengambil input dari keyboard ( 24 27 20 karakter):

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

dengan terima kasih kepada FUZxxl untuk menunjukkan kebodohan saya. :-)

Penjelasan:

J dibaca dari kanan ke kiri, jadi gunakan 2 4:

/digunakan untuk menyisipkan kata kerja $~antara setiap pasangan item dalam daftar. $~mengambil item kiri dan membentuknya $menggunakan item kanan ( ~membalikkan argumen) - jadi ini akan setara dengan 4 $ 2yang memberi Anda daftar 2s yang panjangnya empat item 2 2 2 2.

Sekarang kita menambahkan 1 ke daftar 1,~dan kemudian melakukan hal yang sama lagi; /masukkan kata kerja di */@$~antara setiap pasangan item dalam daftar. Kata kerja ini dimulai dengan cara yang sama $~tetapi kali ini /menyisipkan *antara setiap item dari daftar yang baru dibuat. The @hanya memastikan bahwa */@$~karya-karya sebagai salah satu kata kerja bukan dua. Ini memberi 2dikalikan dengan sendirinya cukup waktu untuk menjadi setara dengan 2^4.

Halaman kosa kata J - Saya menemukan pemecahan masalah dengan J fun hanya karena perbedaan cara terkadang melakukan sesuatu.

Menambahkan satu iterasi lebih lanjut untuk menghapus *operator memiliki 2 masalah

• Itu muncul di 17 karakter ( +/@$~/,@$~/1,~$~/) yang, bahkan dengan bonus -5, terlalu lama
• Kehabisan memori jika jumlahnya terlalu besar sehingga tidak memenuhi persyaratan untuk dapat menghitung 4 3

GolfScript (24 karakter - 5 = 19 poin)

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

sangat lambat.

(atau 20 karakter)

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

jauh lebih cepat.

Python, 70

Ini menggunakan evalpanggilan bersarang , akhirnya menghasilkan string "a*a*a*a...*a"yang dievaluasi. Hampir setengah dari skor terbuang untuk mendapatkan argumen ... meskipun saya perhatikan bahwa beberapa solusi lain tidak peduli dengan itu.

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

penjelasan:

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

ditambah, mul, tinggi (: = pow), tetrasi semua bekerja dengan cara yang sama. Pola umum dapat diekstraksi sebagai metode rekursif, yang membutuhkan dua BigInts dan fungsi dasar:

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

Garis bawah adalah placeholder untuk sesuatu yang dipanggil dalam urutan ini, misalnya penambahan plus (a, b) = (a + b); Oleh karena itu ( + ) adalah fungsi yang mengambil dua argumen dan menambahkannya (a + b).

sayangnya, saya mendapatkan masalah dengan ukuran tumpukan. Ini berfungsi untuk nilai kecil untuk 4 (misalnya: 2) atau jika saya mengurangi kedalaman untuk satu langkah:

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

Kode asli adalah 112 karakter dan akan mencetak skor, jika valid, 107. Mungkin saya mencari tahu cara meningkatkan tumpukan.

Algoritma yang diperluas dapat ditransformasikan menjadi panggilan berulang:

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

Panggilan tailrecursive lebih panjang dari metode asli, tetapi tidak meningkatkan aliran stackover dalam versi lama - namun tidak menghasilkan hasil dalam waktu yang wajar. t (2,4) baik-baik saja, tetapi t (3,3) sudah dihentikan oleh saya setelah 5 menit. Namun, ini sangat elegan, bukan?

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

Dan sekarang sama seperti di atas: gunakan perkalian bau (kita bahkan untung sambil menolak bonus 5, karena kita menyimpan 7 karakter: win = 4 karakter :)

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

doa:

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 byte

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

Input berupa karakter dengan titik kode angka yang diinginkan sebagai input. Outputnya sama.

Penjelasan akan datang ketika saya memiliki waktu di bawah ini. Apakah saya mendapatkan poin bonus karena tidak menggunakan eksponensial, multiplikasi, ATAU bahkan penambahan?

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!

Ini bekerja (diuji) untuk x 0, 0 x, x 1, 1 x, x 2, 2 3, dan 2 4. Saya mencoba 3 3, tetapi itu berjalan selama beberapa jam tanpa menyelesaikan (dalam implementasi Java saya - mungkin tidak optimal) (EDIT: di @ Timwi's EsotericIDE [Ini hebat! Kalian harus mencobanya] juga. Tidak beruntung.). Secara teori, ini bekerja hingga ukuran sel dari implementasi spesifik.

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

memohon:

t(2, 4)

Perl, 61 karakter

ini yang aneh

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

pemakaian:

print t(2,4,1)

Mathematica , 40 33

Ini tidak cukup sesuai dengan aturan tetapi tidak dalam pertentangan untuk kode terpendek, dan saya harap itu akan menarik bagi seseorang.

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

m[m@Sum]

Ini membangun fungsi "tetrasi" ketika dijalankan, tetapi argumen harus diberikan dalam urutan terbalik. Contoh:

m[m@Sum][3, 4]

1340780792994259709957402499820584612747936582059239337772356144372176 40300735469768018742981669034276900318581864860508537538828119465660604040

Haskell:  58  51 karakter, dengan atau tanpa perkalian.

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

Tidak Terkumpul:

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

Definisi yang lebih pendek berasal dari inlining "bump", dan mendefinisikan versi kustom "iterate". Sayangnya hasilnya sangat tidak efisien, tetapi mulai dengan (*) bukannya (+) memberikan kecepatan yang layak. Di 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 karakter

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

Python, 112 karakter

Angka-angka harus menjadi argumen 1 dan 2: python this.py 4 3
**operator tidak digunakan.
*bekas. Ini cukup sepele untuk diterapkan, persis seperti **, tetapi biaya lebih dari 5 karakter.

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 karakter

EDIT: Menggabungkan dua fungsi pdan rmenjadi satu, menghemat beberapa karakter.
Dari 99 karakter, 52 melakukan perhitungan aktual (termasuk definisi variabel). 47 lainnya untuk menangani input dan output.
BUG: Buruk menangani kekuatan 0 (misalnya 0 2). Harus menemukan perbaikan biaya minimum. Ini bukan bug, saya lupa itu 0 2tidak terdefinisi.

Berhasil menangani 4 3, dan bahkan memberikan hasil yang tepat. Namun, bisa jadi tidak akurat untuk beberapa nomor yang lebih kecil.
Mencetak nomor dengan 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());
}

Faktor, 187 karakter

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 .

Sebelum 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.

Saya tidak menghapus operator perkalian *. Jika saya melakukannya, maka saya perlu menambahkan beberapa logika yang menyatakan bahwa jumlah urutan kosong adalah 0, bukan 1. Logika ekstra ini akan menelan biaya lebih dari -5 bonus.

Pemutus aturan, 124 + 10 = 134 karakter

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

Program ini memiliki skor lebih rendah, tetapi operator eksponensial ^melanggar aturan. Aturan mengatakan "(# karakter) + (10 * (# operator 'kekuatan'))", jadi saya menerapkan penalti +10. Namun, aturan itu juga mengatakan "Jangan gunakan operator 'kekuatan', jadi setiap program yang mengambil penalti ini melanggar aturan. Oleh karena itu, program dengan 134 karakter ini bukan jawaban yang benar, dan saya harus menyajikan program saya yang lebih panjang dari 187 karakter sebagai jawaban.

Haskell 110 - 5 = 105

Gaya Tetano Peano. Ini adalah solusi paling lambat yang mungkin, hanya sebuah peringatan, tetapi juga menghindari penambahan.

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)

Ini bergantung pada Anda memiliki kesabaran untuk mengetikkan angka Peano (dan tidak akan menunjukkan jawabannya, Jika Anda benar-benar ingin menjalankannya, tambahkan beberapa baris ini (90 karakter):

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 karakter, tanpa perkalian

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)

Saya awalnya akan menggunakan peretasan pengulangan string untuk melakukan perkalian palsu, tetapi suka gagal pada nilai-nilai besar. Saya mungkin bisa menggunakan kompilasi dinamis dan loadstring untuk membuatnya lebih kecil, tetapi sudah terlambat di sini ... Saya perlu tidur.

Memasukkan "4 3" ke dalam output stdin:

1.3407807929943e+154

VBA, 90 Karakter

* Mungkin bonus no multiplication tidak cukup baik. Saya pikir jawaban tidak ada multiplikasi jauh lebih menarik, tapi ini kode golf, jadi itu bukan yang terbaik. Inilah jawaban tanpa *, dan jawaban yang lebih baik (lebih pendek, dan skor lebih baik):

90 karakter, tanpa operator daya, menggunakan perkalian = 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 karakter, tidak ada operator daya, tidak ada bonus multiplikasi (-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

CATATAN: VBA memiliki masalah mencetak nomor ketika hasilnya sangat besar (yaitu 4, 3), tetapi menghitung dengan benar, jadi jika, misalnya, Anda ingin MENGGUNAKAN nomor itu, Anda akan baik untuk pergi. Juga, bahkan angka yang LEBIH BESAR melimpah (yaitu 3, 4).

Perl 6 , 32 byte

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

Cobalah online!

(1, { [*] a xx $_ } ... *)adalah urutan malas yang menghasilkan menara listrik, setiap elemen menjadi daftar yang terdiri dari parameter input pertama adireplikasi ( xx) beberapa kali sama dengan elemen sebelumnya ( $_), daftar itu kemudian dikurangi dengan perkalian ( [*]). Dari urutan itu kita cukup mencabut belemen -th.

Kalkulus Lambda, 10-5

(Menggunakan encoding Gereja dan indeces De Bruijn )
λλ(1λ13)λ1

Penjelasan

Tanpa 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

Jika Anda mendefinisikan exp_a(x)=a^xprogram ini menentukan di a↑↑b=exp_a^b(1)mana ^bmenunjukkan itterasi fungsi.

Saya tidak yakin apakah ini diizinkan karena casecara teknis setara dengan a^cseberapa pernah itu bukan built-in dan hanya efek samping dari cara bilangan bulat dikodekan dalam kalkulus lambda.

Javascript: 116 karakter

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

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

Pembaruan: Harus menambahkan nilai awal, agar sesuai dengan t (X, 0) = 1

Haskell: 88-5 karakter tanpa multiplikasi, 59 karakter dengan multiplikasi

Tanpa multiplikasi:

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

Mungkin ada beberapa cara yang bisa saya lakukan untuk bermain golf.

Dengan multiplikasi:

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

Dan akhirnya, program tanpa kulit:

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)

Ini mungkin cara paling sederhana untuk melakukan masalah ini, yang mendefinisikan perkalian sebagai penambahan berulang, eksponensial sebagai perkalian berulang, dan tetrasi sebagai eksponensial berulang.

Racket 58 (no *)

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

Common Lisp, 85 karakter

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

Saya mencoba melakukan perkalian melalui penambahan berulang, tapi itu jauh lebih dari 5 karakter. Hal yang sama dengan macrolets, deklarasi tidak sebanding dengan keuntungannya.

Solusi lain, terinspirasi oleh solusi python boothby. Ini 1 karakter kurang dari solusi di atas.

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

Python 3 - 68

(termasuk penalti 10 poin untuk operator listrik)

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

Yabasic , 71 byte

Fungsi yang mengambil input adan bsebagai string yang dibatasi ruang.

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

Cobalah online!

R , 71 - 5 = 66 byte

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

Cobalah online!

-5 untuk menghindari *, yang lebih sulit dari yang saya harapkan. Ini meledak sangat cepat dan tidak akan berfungsi (kecuali jika memiliki lebih banyak memori) tetapi memenuhi semua kriteria yang diperlukan.