Saya menyadari bahwa ini sedikit matematika-y, tetapi - begini saja.

Dalam matematika, urutan hiperoperasi adalah urutan tak terbatas dari operasi aritmatika (disebut hiperoperasi) yang dimulai dengan operasi penerus unary, kemudian dilanjutkan dengan operasi biner penambahan, perkalian, dan eksponensial, setelah itu urutan dilanjutkan dengan operasi biner lebih lanjut yang melampaui eksponensial, menggunakan asosiatif-kanan.

Tujuan Anda adalah untuk menulis sebuah program yang mengambil tiga bilangan bulat x, y dan n sebagai input dan output hasil dari n operasi ke-n pada x dan y.

Misalnya

1 1 1 output 2

2 4 4 keluaran 65536

3 3 4 keluaran 7625597484987

• Program harus ditulis dalam bit kode terpendek.
• Anda dapat mengambil input baik dari STDINatau dari file.
• Fungsi perpustakaan tidak diizinkan.
• Batasan input: n akan menjadi ≥ 1.

http://en.wikipedia.org/wiki/Tetration memiliki penjelasan yang baik jika Anda tidak dapat memahami hal ini.

Ruby, lambat, 86 84 83 karakter

def f x,y,n
n>1?(c=x;2.upto(y){c=f(x,c,n-1)};c):x+y
end
p f *gets.split.map(&:to_i)

Ruby, cepat, 96 94 93 karakter

def f x,y,n
n>1?(n>2?(c=x;2.upto(y){c=f(x,c,n-1)};c):x*y):x+y
end
p f *gets.split.map(&:to_i)

Versi pertama adalah cara terlalu lambat dengan kasus tes terakhir, jadi saya menambahkan versi yang menggunakan perkalian sebagai kasus dasar bukan penambahan. Versi pertama membutuhkan waktu lama untuk menghitung 3 3 4; yang kedua adalah instan (di konsol IRB asli; versi web sedikit lebih lambat).

Beberapa keindahan Ruby muncul di sini:

Hampir setiap pernyataan adalah ekspresi dalam ruby. Dengan demikian, Anda dapat memasukkan titik koma di dalam operator ternary, asalkan Anda memiliki cukup tanda kurung di sekitarnya. Coffeescript meminjam yang itu. Itu juga meminjam sintaks panggilan "tidak perlu paren" Ruby.

Pengembalian tersirat: ini adalah fitur keren, dan mengikuti dari sebelumnya. Memang, memulai baris terakhir dari suatu fungsi dengan returndianggap lumpuh, bahkan ketika tidak bermain golf.

Bilangan adalah objek dalam ruby ​​(bahkan nullobjek). Dalam ruby, integer memiliki metode times, yang mengeksekusi blok yang diteruskan ke sana beberapa kali. Ini hanyalah salah satu dari banyak metode iterator Ruby. Di sini, uptometode ini memungkinkan kita menyimpan dua karakter lebih dari apa yang timesmemungkinkan kita.

unary *adalah operator percikan di sini. Itu mengubah array menjadi daftar argumen. Sama seperti Javascript Function#apply, tetapi lebih pendek dan lebih baik.

unary &mengubah prosedur menjadi blok. Meskipun :to_imerupakan simbol, itu dikonversi menjadi prosedur yang cukup baik. Yaitu, itu berubah menjadi prosedur yang memanggil to_iargumennya dan mengembalikan hasilnya. Informasi lebih lanjut tentang Stack Overflow.

Mungkin saja untuk membuatnya lebih cepat dengan menggunakan n=3sebagai alas, tapi saya khawatir tidak diperlukan. Namun, ini hanya membutuhkan 11 karakter, berkat keindahan ruby ​​lainnya: operator eksponensial **. Python memiliki operator ini, tetapi ini bukan yang pertama (seperti yang dicatat @ alias.nice - terima kasih -, Fortran sudah memiliki operator ini).

juru ruby ​​online tersedia di sini: http://repl.it/Ikj/1

APL, 62

{1=3⌷⍵:2⌷+\⍵⋄0=2⌷⍵:(⍵[3]⌊3)⌷⍵[1],0,1⋄∇⍵[1],(∇⍵-0 1 0),3⌷⍵-1}⎕

{...}⎕: Mengambil input yang dievaluasi (angka-angka yang dipisahkan spasi mengevaluasi ke array numerik) dan menerapkan fungsinya.

1=3⌷⍵:: Jika n sama dengan 1 ...
2⌷+\⍵: Kembalikan jumlah dari 2 elemen pertama (x + y) ...
⋄0=2⌷⍵:: Lain jika y sama dengan 0 ...
(⍵[3]⌊3)⌷⍵[1],0,1: Buat array numerik [x, 0,1] dan indeks pengembalian min(n,3)...
⋄∇⍵[1],(∇⍵-0 1 0),3⌷⍵-1: Kembalikan ∇ (x, ∇ (x, y-1, n), n-1). (∇ adalah referensi diri)

Saya telah mendapatkan operator "penambah-hiper", yang mengambil fungsi dan mengembalikan hiperoperasi berikutnya

{⍺⍺/⊃⍴/⌽⍵}

Misalnya, +{⍺⍺/⊃⍴/⌽⍵}akan menjadi fungsi perkalian dan +{⍺⍺/⊃⍴/⌽⍵}5 3keluaran 15.

Tapi tidak bisa kambuh lagi. Mungkin orang lain bisa melakukannya.

Python, 83

(Berdasarkan jawaban flornquake )

def h(x,y,n):r=n>2;exec"r=h(x,r,n-1);"*y*(n>1);return(x+y,r)[n>1]
print h(*input())

Sangat lambat untuk hasil yang besar.

Untuk 2, 4, 4outputnya adalah 65536.

Python, 96 92

def h(x,y,n):r=1;exec(n>2)*y*"r=h(x,r,n-1);";return(r,(x+y,x*y)[n>1])[n<3]
print h(*input())

Input: 3, 3, 4
Keluaran:7625597484987

Dipersingkat menggunakan beberapa ide @ WolframH .

Skrip golf, lambat, 39 karakter

 ~{\(.{3${[4$\2$4$.~}4$(*}{;;+}if])\;}.~

(tautan langsung)

Ini adalah algoritma rekursif standar dengan kasus dasar n = 1 (penambahan) (yaitu lambat). Hal yang sama saya gunakan dalam solusi Ruby saya

Berikut ini adalah versi dengan anotasi saya (kebanyakan penumpukan). Itu tidak termasuk satu optimasi yang saya tambahkan nanti:

~{            #read the input and do (x y n f)
 \(.{         #(x y f n-1); if(n-1)
  3${         #(x y f n-1 c)
   4$\2$4$.~  #(x y f n-1 x c n-1 f); call
  }3$(*       #y-1 times
  {\;}4*
 }{           #else
  ;;+         #return (x+y)
 }if
}.~           #once

~adalah operator eval. Dalam hal string, ini memperlakukan string sebagai program GolfScript. Untungnya, daftar bilangan bulat yang dipisahkan oleh ruang adalah program GolfScript yang valid yang mendorong bilangan bulat tersebut di tumpukan. Dibandingkan dengan ini, versi rutin input saya sebelumnya ( " "/{~}/masing-masing dipisahkan oleh spasi dan eval) cukup timpang. Dalam hal fungsi, ini memanggil fungsi. Ketika didahului oleh .(klon), ia memanggil fungsi itu sendiri sebagai argumen pertama.

Golfscript tampaknya tidak cocok untuk membuat algoritma rekursif. Jika Anda menginginkan algoritme rekursif yang tidak dapat dioptimalkan dengan tail-call, Anda perlu membuat dan memusnahkan frame stack untuk menjaga variabel Anda. Dalam sebagian besar bahasa, ini dilakukan secara otomatis. Dalam skrip golf, Anda harus benar-benar mengkloning variabel (sebenarnya, entri tumpukan), dan menghancurkan entri tumpukan yang tidak lagi Anda perlukan. Golfscript tidak memiliki konsep stack frames. Sudahkah saya mengatakan GolfScript adalah bahasa berbasis stack?

Persyaratan pertama bisa dimengerti. Anda harus menentukan argumennya entah bagaimana. Hanya baik jika mereka mempertahankan posisi asli mereka juga. Persyaratan kedua sangat disayangkan, terutama karena nilai kembali berada di atas tumpukan, dan skrip golf tidak memiliki kemampuan untuk menghapus sembarang elemen tumpukan. Anda dapat memutar tumpukan dan membuang elemen teratas baru, tetapi itu dengan cepat menumpuk. \;baik-baik saja. \;\;\;\;\;bukan. Anda dapat melakukannya \;dalam satu lingkaran ( {\;}9*; biaya: 6 karakter untuk membuang hingga 9 elemen, atau 7 karakter untuk membuang hingga 99 elemen), tetapi kami dapat melakukan yang lebih baik:

Golfscript memiliki array kelas satu. Ia juga memiliki sintaks literal array [1 2 3 4]. Yang tidak terduga adalah itu [dan ]sebenarnya bukan bagian dari sintaksis. Mereka hanyalah dua operator: [menandai posisi saat ini di tumpukan, dan ]mengumpulkan setiap elemen hingga menemukan tanda awal array atau kehabisan tumpukan, dan membuang tanda. Anda bahkan dapat memisahkan keduanya dan melihat apa yang terjadi. Nah, hal yang cukup menarik:

Apakah saya mengatakan golfscript tidak memiliki konsep stack frames? Aku berbohong. Ini adalah stack frame: [. Anda bisa membuang semuanya sekaligus: ];. Tetapi bagaimana jika kita ingin mempertahankan nilai pengembalian? Anda dapat menutup bingkai tumpukan pada entri fungsi (maka kami memiliki versi pass-by-array yang sedikit rusak - bukan konsep yang menarik), atau kami dapat menutup bingkai tumpukan dan mengambil elemen terakhir alih-alih membuangnya sepenuhnya: ]-1=atau kami dapat uncons elemen terakhir sebaliknya, dan kemudian membuang frame: ])\;. Panjangnya sama, tetapi yang terakhir sedikit lebih dingin, jadi saya menggunakannya.

Jadi, alih-alih 6 atau 7 karakter untuk melakukan pembersihan, kita bisa melakukannya dengan 5. Saya masih merasa ini bisa lebih golf, tapi hei, kami sudah menyelamatkan satu karakter.

Smalltalk Squeak 4.x rasa banyak byte!

Saya bisa menerapkan salah satu bentuk rekursif dalam Integer di 71 char

f:y n:n n=1or:[^(2to:y)inject:self into:[:x :i|self f:x n:n-1]].^self+y

Kemudian membaca dari file atau FileStream stdin akan dikenakan biaya lengan saya ... Mencicit jelas tidak dirancang sebagai bahasa scripting. Jadi saya akan menghabiskan banyak byte untuk membuat utilitas keperluan umum saya sendiri yang tidak terkait dengan masalah:

Terapkan metode 21 char ini di Stream (untuk melewati pelaut)

s self skipSeparators

Terapkan metode 20 karakter ini dalam Perilaku (untuk membaca sebuah instance dari Stream)

<s^self readFrom:s s

Kemudian 28 karakter dalam String (untuk membuat file handle)

f^FileDirectory default/self

Kemudian 59 karakter di FileDirectory (untuk membuat readStream)

r^FileStream concreteStream readOnlyFileNamed:self fullName

Kemudian 33 karakter di BlockClosure (untuk mengevaluasinya n kali)

*n^(1to:n)collect:[:i|self value]

Kemudian 63 karakter dalam Array (mengevaluasi argumen dengan penerima dan argumen yang diambil dari Array)

`s^self first perform:s asSymbol withArguments:self allButFirst

kemudian selesaikan masalahnya dengan mengevaluasi 31 char snippet ini di mana saja untuk dibaca dari file bernama x

|s|s:='x'f r.[0class<s]*3`#f:n:

Bahkan tanpa menghitung utilitas, itu 71 + 31 = 102 karakter sudah ...

Sekarang, karena saya yakin akan kehilangan codeGolf, saya memiliki implementasi yang lebih lucu di Integer:

doesNotUnderstand:m
    (m selector allSatisfy:[:c|c=$+])or:[^super doesNotUnderstand:m].
    self class compile:
        m selector,'y y=0or:[^(2to:y)inject:self into:[:x :i|self'
        ,m selector allButLast,'x]].^'
        ,(Character digitValue:()asBit)
        ,(m selector size-2min:1)hex last.
    thisContext sender restart

Metode ini akan mendefinisikan (kompilasi) pesan biner yang terbuat dari n + jika tidak ada (tidak dipahami oleh penerima pesan m), dan akan memulai kembali eksekusi di awal konteks pengirim. Saya memasukkan tambahan carriage return dan ruang untuk keterbacaan.

Perhatikan bahwa itu (m selector size-2min:1)hex lastadalah bentuk kependekan dari (m selector size>2)asBit printString.

Jika bukan untuk menunjukkan kekuatan super Smalltalk jahat, pernyataan terakhir bisa digantikan oleh lebih pendek dan lebih sederhana

^m sendTo:self

Sekarang mengimplementasikan utilitas 28 karakter dalam Karakter (untuk mengulanginya n kali dalam sebuah String)

*n^String new:n withAll:self

Kemudian evaluasi ungkapan 43 karakter ini:

|i s|i:=0class.s:='x'f r.[i<s]*2`($+*(i<s))

Kami dapat mempercepat dengan 10 karakter lagi dengan menerapkan Integer:

++y^self*y

dan dalam hal ini kami juga memiliki kode yang lebih pendek karena kami dapat mengganti ^',(m selector size-2min:1)hex lastdengan^1'

Untuk harga setinggi itu, kodenya bekerja dengan integer kedua = 0 :)

Groovy - 77

h={x,y,n->n<2?x+y:y<2?x:h(x,h(x,y-1,n),n-1)}
print h(args.collect{it as int})

Catatan: memerlukan sejumlah tumpukan (dan waktu) yang tidak senonoh untuk argumen yang tidak kecil.

Sistem Aljabar Komputer AXIOM, byte 69

p(x,y,n)==(n<=1=>y+x^n;n=2=>y*x;n=3=>x^y;y<=0=>1;p(x,p(x,y-1,n),n-1))

uji:

(2) -> p(1,1,1)
   (2)  2
                                                 Type: Expression Integer
                                   Time: 0.05 (IN) + 0.03 (OT) = 0.08 sec
(3) -> p(2,4,4)
   (3)  65536
                                                 Type: Expression Integer
                                                              Time: 0 sec
(4) -> p(3,3,4)
   (4)  7625597484987
                                                 Type: Expression Integer
                                                              Time: 0 sec

Ini akan menghilangkan beberapa rekursi ... Kemungkinan saya menukar di x dan y di beberapa pengembalian ... apakah ada nilai tes lainnya?

APL (NARS), karakter 61, byte 122

{(x y n)←⍵⋄n≤1:y+x*n⋄n=2:x×y⋄n=3:x*y⋄y≤0:1⋄∇x,(∇x(y-1)n),n-1}

uji:

  h←{(x y n)←⍵⋄n≤1:y+x*n⋄n=2:x×y⋄n=3:x*y⋄y≤0:1⋄∇x,(∇x(y-1)n),n-1}
  h 1 1 1
2
  h 2 4 4
65536
  h 3 4 4
∞
  h 3 3 4
7625597484987