Zdaję sobie sprawę, że to trochę matematyka, ale - proszę bardzo.

W matematyce sekwencja hiperoperacji jest nieskończoną sekwencją operacji arytmetycznych (zwanych hiperoperacjami), która rozpoczyna się od jednoargumentowej operacji następcy, a następnie kontynuuje binarne operacje dodawania, mnożenia i potęgowania, po których sekwencja przechodzi do dalszych operacji binarnych wykraczających poza potęgowanie, przy użyciu asocjatywności prawej.

Twoim celem jest napisanie programu, który przyjmuje trzy liczby całkowite x, y i n jako dane wejściowe i wyprowadza wynik n-tej hiperoperacji na x i y.

Na przykład

1 1 1 wyjścia 2

2 4 4 wyjścia 65536

3 3 4 wyjścia 7625597484987

• Program musi być napisany w najkrótszym kawałku kodu.
• Możesz pobierać dane wejściowe STDINz pliku lub z pliku.
• Funkcje biblioteczne są niedozwolone.
• Ograniczenia wejściowe: n będzie ≥ 1.

http://en.wikipedia.org/wiki/Tetration ma dobre wytłumaczenie na wypadek, gdybyś nie był w stanie tego otulić.

Rubinowy, wolny, 86 84 83 znaki

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)

Rubinowy, szybki, 96 94 93 znaki

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)

Pierwsza wersja jest sposób zbyt powolny z ostatniego testu, więc dodałem wersję zastosowania mnożenie jak w przypadku podstawowej zamiast dodawania. Pierwsza wersja wymaga wieków do obliczenia 3 3 4; drugi jest natychmiastowy (w natywnej konsoli IRB; wersja internetowa jest nieco wolniejsza).

Pojawia się tutaj kilka piękności Ruby:

Prawie każde zdanie jest wyrażeniem w rubinie. W ten sposób możesz wstawiać średniki do operatora trójskładnikowego, pod warunkiem, że masz wystarczająco dużo nawiasów wokół. Coffeescript pożyczył to. Pożyczył także składnię wywołania Ruby „nie trzeba nic robić”.

Niejawne zwroty: jest to fajna funkcja i wynika z poprzedniego. Rzeczywiście, rozpoczęcie ostatniej linii funkcji returnjest uważane za kiepskie, nawet gdy nie gra w golfa.

Liczby są obiektami w rubinie (nawet nulljest obiektem). W języku ruby ​​liczby całkowite mają metodę times, która wykonuje przekazany do niej blok kilka razy. To tylko jedna z wielu metod iteracji Ruby. Tutaj uptometoda pozwala nam zaoszczędzić jeszcze dwa znaki nad tym, co timespozwala nam.

unary *jest tutaj operatorem splat. Zamienia tablicę w listę argumentów. Podobnie jak Javascript Function#apply, ale jest krótszy i lepszy.

unary &zamienia procedurę w blok. Chociaż :to_ijest symbolem, całkiem dobrze przekształca się w procedurę. Mianowicie zamienia się w procedurę, która wywołuje to_iswój argument i zwraca wynik. Więcej informacji o przepełnieniu stosu.

Byłoby możliwe, aby uzyskać go jeszcze szybciej, używając n=3jako podstawy, ale obawiam się, że nie jest to potrzebne. Kosztowałoby to jednak tylko 11 znaków, dzięki innej urodzie rubinu: operatorowi potęgowania **. Python ma ten operator, ale nie jest to pierwszy (jak zauważył @ aka.nice - dzięki - Fortran miał już tego operatora).

internetowy tłumacz ruby ​​dostępny tutaj: http://repl.it/Ikj/1

APL, 62

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

{...}⎕: Pobiera obliczone dane wejściowe (liczby rozdzielone spacjami są przetwarzane na tablicę numeryczną) i stosuje do nich funkcję.

1=3⌷⍵:: Jeśli n jest równe 1 ...
2⌷+\⍵ : Zwraca sumę pierwszych 2 elementów (x + y) ...
⋄0=2⌷⍵:: W przeciwnym razie, jeśli y jest równe 0 ...
(⍵[3]⌊3)⌷⍵[1],0,1: Utwórz tablicę numeryczną [x, 0,1] i zwróć indeks min(n,3)...
⋄∇⍵[1],(∇⍵-0 1 0),3⌷⍵-1: W innym przypadku ∇ (x, ∇ (x, y-1, n), n-1). (∇ jest samodzielnym odniesieniem)

Mam operatora „hyper-raiser”, który przyjmuje funkcję i zwraca następną hiperoperację

{⍺⍺/⊃⍴/⌽⍵}

Na przykład +{⍺⍺/⊃⍴/⌽⍵}byłaby funkcja mnożenia i +{⍺⍺/⊃⍴/⌽⍵}5 3wyjścia 15.

Ale nie mogę tego powtórzyć. Może ktoś inny może to zrobić.

Python, 83

(Na podstawie odpowiedzi trzęsienia ziemi )

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

Bardzo wolno dla dużych wyników.

Na 2, 4, 4wyjściu jest 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())

Wejście: 3, 3, 4
Wyjście:7625597484987

Skrócono za pomocą kilku pomysłów @ WolframH .

Golfscript, wolny, 39 znaków

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

(link na żywo)

Jest to standardowy algorytm rekurencyjny z przypadkiem podstawowym n = 1 (dodawanie) (tzn. Powolny). To samo, którego użyłem w moim rozwiązaniu Ruby

Oto wersja z moimi adnotacjami (głównie przechowywanie stosów). Nie obejmuje jednej optymalizacji, którą dodałem później:

~{            #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

~jest operatorem eval. W przypadku ciągów traktuje ciąg znaków jako program GolfScript. Na szczęście rozdzielona spacjami lista liczb całkowitych jest poprawnym programem GolfScript, który wypycha te liczby całkowite na stos. W porównaniu z tym moja poprzednia wersja procedury wprowadzania ( " "/{~}/podzielona spacją i eval każda) jest dość kiepska. W przypadku funkcji wywołuje funkcję. Poprzedzona przez .(klon) wywołuje funkcję z samym sobą jako pierwszym argumentem.

Golfscript wydaje się nie nadawać się do tworzenia algorytmów rekurencyjnych. Jeśli chcesz algorytmu rekurencyjnego, który nie jest zoptymalizowany do wywołania ogona, musisz utworzyć i zniszczyć ramki stosu, aby zachować zmienne. W większości języków odbywa się to automatycznie. W golfscript musisz sklonować zmienne (właściwie wpisy stosu) i zniszczyć wpisy stosu, których już nie potrzebujesz. Golfscript nie ma pojęcia o stosach ramek. Czy powiedziałem, że GolfScript jest językiem stosowym?

Pierwszy wymóg jest zrozumiały. Musisz jakoś podać argumenty. To miłe tylko wtedy, gdy zachowują swoje oryginalne pozycje. Drugie wymaganie jest niefortunne, zwłaszcza że wartość zwracana jest na górze stosu, a golfscript nie ma możliwości usunięcia dowolnego elementu stosu. Możesz obrócić stos i odrzucić nowy górny element, ale to szybko się powiększa. \;jest w porządku. \;\;\;\;\;nie jest. Możesz to zrobić \;w pętli ( {\;}9*; koszt: 6 znaków, aby odrzucić do 9 elementów lub 7 znaków, aby odrzucić do 99 elementów), ale możemy zrobić to lepiej:

Golfscript ma pierwszorzędne tablice. Ma również składnię literalną tablicę [1 2 3 4]. Co znajduje się nieoczekiwane jest to, że [i ]w rzeczywistości nie są częścią składni. Są to tylko dwa operatory: [oznacza bieżącą pozycję na stosie i] zbiera każdy element, aż znajdzie znak początku tablicy lub skończy się stos, i odrzuca znak. Możesz nawet rozerwać te dwie części i zobaczyć, co się stanie. Cóż, całkiem interesująca rzecz:

Czy powiedziałem, że golfscript nie ma pojęcia o stosach ramek? Kłamałem. To rama stosu: [. Można go wyrzucić wszystko na raz: ];. Ale co, jeśli chcemy zachować wartość zwracaną? Możesz zamknąć ramkę stosu przy wprowadzaniu funkcji (wtedy mamy nieco zniekształconą wersję pass-by-array - nie jest to interesująca koncepcja), lub możemy zamknąć ramkę stosu i wziąć jej ostatni element zamiast całkowicie ją odrzucić: ]-1=lub możemy można uncons ostatni element, a nie, a następnie usunąć ramkę: ])\;. Są tej samej długości, ale ta druga jest nieco fajniejsza, więc używam jej.

Więc zamiast 6 lub 7 postaci, aby zrobić porządek, możemy zrobić z 5. Nadal uważam, że można by to bardziej zagrać w golfa, ale hej, ocaliliśmy postać.

Smalltalk Squeak 4.x posmakuj wielu bajtów!

Mógłbym zaimplementować jedną z rekurencyjnych postaci w Integer w 71 znakach

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

Wtedy czytanie z pliku lub standardowego FileStream będzie mnie kosztować ramię ... Squeak oczywiście nie został zaprojektowany jako język skryptowy. Dlatego spędzę wiele bajtów, aby stworzyć własne narzędzia ogólnego przeznaczenia niezwiązane z problemem:

Zaimplementuj tę metodę 21 znaków w Streamie (aby pominąć separatory)

s self skipSeparators

Zaimplementuj tę metodę 20 znaków w zachowaniu (aby odczytać instancję ze strumienia)

<s^self readFrom:s s

Następnie 28 znaków w ciągu (aby utworzyć uchwyt pliku)

f^FileDirectory default/self

Następnie 59 znaków w FileDirectory (aby utworzyć readStream)

r^FileStream concreteStream readOnlyFileNamed:self fullName

Następnie 33 znaki w BlockClosure (aby ocenić to n razy)

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

Następnie 63 znaki w tablicy (oceń argument za pomocą odbiornika i argumenty pobrane z tablicy)

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

następnie rozwiąż problem, oceniając ten fragment 31 znaków w dowolnym miejscu do odczytu z pliku o nazwie x

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

Nawet nie licząc narzędzi, to już 71 + 31 = 102 znaków ...

Teraz, ponieważ na pewno stracę kod Golf, mam zabawniejszą implementację w 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

Ta metoda zdefiniuje (skompiluje) binarne wiadomości wykonane z n +, jeśli nie istnieje (nie jest rozumiane przez odbiorcę wiadomości m), i ponownie uruchomi wykonywanie na początku kontekstu nadawcy. Wstawiłem dodatkowy znak powrotu karetki i spacje dla czytelności.

Zauważ, że (m selector size-2min:1)hex lastjest to zwarta forma (m selector size>2)asBit printString.

Gdyby nie demonstrowanie złych supermocarstw Smalltalk, ostatnie stwierdzenie można by zastąpić krótszym i prostszym

^m sendTo:self

Teraz zaimplementuj narzędzie 28 znaków w Postaci (aby powtórzyć to n razy w ciągu)

*n^String new:n withAll:self

Następnie oceń to wyrażenie 43 znaków:

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

Możemy przyspieszyć z 10 dodatkowymi znakami, implementując w Integer:

++y^self*y

iw tym przypadku mamy również krótszy kod, ponieważ możemy wymienić ^',(m selector size-2min:1)hex lastz^1'

Za tak wysoką cenę kod działa z drugą liczbą całkowitą = 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})

Uwaga: wymaga nieprzyzwoitych ilości stosu (i czasu) dla niemałych argumentów.

System komputerowej algebry AXIOM, bajty 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))

test:

(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

To wyeliminowałoby pewną rekurencję ... Możliwe, że w zamian zamieniłem xiy y ... czy są inne wartości testowe?

APL (NARS), znaki 61, bajty 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}

test:

  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