Wyzwanie

Zaimplementuj tetrację (inaczej Power Tower lub Hyperexponentiation) z najmniejszą liczbą postaci.

Warunki

• Nie używać określenia „moc” operatora lub jego odpowiedniki (takie jak pow(x,y), x^y, x**yetc.)
• Dane wejściowe podane jako: x y(oddzielone spacją)
• xjest potęgowany przez siebie yrazy.
• Twoja metoda musi być w stanie obliczyć co najmniej 4 3(4 wykładniki samodzielnie 3 razy)

Punktacja

• Najniższy wynik wygrywa: (liczba znaków)
• Odliczenie premii, jeśli nie korzystasz z operatora mnożenia (-5 punktów).
• Brak wymagań prędkości / pamięci. Zajmij tyle, ile chcesz.

Przykłady

x, 0 -> 1

2, 2 -> 2^2 = 4

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

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

Otwarty na sugestie / zmiany / pytania

J, wynik to 7 (12 znaków - 5 punktów za uniknięcie pomnożenia)

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

stosowanie:

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

Tylko kilka zagnieżdżonych fałd:

• Przy użyciu mnożenia byłoby to */@$~/@$~
• Używając mocy byłoby to, ^/@$~gdzie $~tworzy tablicę, /jest funkcją składania.

Haskell, 87 85 - 5 == 80 82

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

Nie używa potęgowania, mnożenia ani dodawania (!), Wystarczy wyświetlić listę operacji. Demonstracja:

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 ... nie mówiłeś nic o wydajności ani pamięci, prawda? Ale biorąc pod uwagę wystarczającą ilość miliardów lat i kilka petabajtów pamięci RAM, nadal dawałoby to poprawny wynik (genericLength może użyć bigInt do zliczenia długości listy).

GolfScript, 15 18 znaków

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

Tak, jeden ze *znaków to operator mnożenia (ćwiczenie: który?), Więc nie kwalifikuję się do otrzymania premii 5 znaków. Mimo to jest tylko trochę krótszy niż rozwiązanie Petera .

Wcześniejsza 15-znakowa wersja jest inaczej taka sama, ale nie generuje danych wyjściowych, gdy drugi argument ma wartość 0. Dzięki res za wykrycie błędu.

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

J, 16 19 12 znaków

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

lub jako czasownik (17 znaków):

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

stosowanie:

   h 2 4
65536

lub pobieranie danych z klawiatury ( 24 27 20 znaków):

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

z podziękowaniami dla FUZxxl za zwrócenie uwagi na moją głupotę. :-)

Wyjaśnienie:

J jest odczytywany od prawej do lewej, więc używając 2 4:

/służy do wstawiania czasownika $~między każdą parą elementów na liście. $~bierze lewy element i kształtuje go $za pomocą odpowiedniego elementu ( ~odwraca argumenty) - więc byłoby to równoważne z tym, 4 $ 2co daje listę 2s, która ma cztery elementy 2 2 2 2.

Teraz dodajemy 1 do listy, 1,~a następnie robimy to samo ponownie; /wstaw czasownik */@$~między każdą parą elementów na liście. Ten czasownik zaczyna się w ten sam sposób, $~ale tym razem /wstawia *między każdą pozycję nowo wygenerowanej listy. @Tylko zapewnia, że */@$~prace jako jeden czasownik zamiast dwóch. Daje to 2pomnożone przez siebie wystarczającą ilość razy, aby być równoważnym 2^4.

Strona słownictwa J. - Rozwiązywanie problemów z J sprawia mi przyjemność tylko dlatego, że czasami robi różne rzeczy.

Dodanie jednej kolejnej iteracji w celu usunięcia *operatora ma 2 problemy

• Wychodzi na 17 znaków ( +/@$~/,@$~/1,~$~/), co, nawet z bonusem -5, jest za długie
• Skończy się jej pamięć, jeśli liczba będzie zbyt duża, więc nie spełnia wymogu możliwości obliczenia 4 3

GolfScript (24 znaki - 5 = 19 punktów)

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

jest niesamowicie wolny.

(lub 20 znaków)

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

jest znacznie szybszy.

Python, 70

Używa zagnieżdżonych evalwywołań, w końcu generując ciąg, "a*a*a*a...*a"który jest analizowany. Prawie połowa wyniku jest marnowana na uzyskiwanie argumentów ... chociaż zauważyłem, że kilka innych rozwiązań nie przeszkadza w tym.

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

bez golfa:

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

wyjaśnienie:

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 działają wszystkie w ten sam sposób. Wspólny wzorzec można wyodrębnić jako metodę rekurencyjną, która wymaga dwóch BigIntów i podstawowej funkcji:

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

Podkreślenia są symbolami zastępczymi dla czegoś, co zostanie wywołane w tej sekwencji, na przykład dodanie plus (a, b) = (a + b); dlatego ( + ) jest funkcją, która pobiera dwa argumenty i dodaje je (a + b).

niestety mam problemy z rozmiarem stosu. Działa dla małych wartości dla 4 (na przykład: 2) lub jeśli zmniejszę głębokość o jeden krok:

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

Oryginalny kod składa się z 112 znaków i, jeśli jest poprawny, wyniósłby 107. Może dowiem się, jak zwiększyć stos.

Rozszerzony algorytm można przekształcić w wywołania tailrecursive:

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

Wywołanie tailrecursive jest dłuższe niż oryginalna metoda, ale nie spowodowało przepełnienia stosu w długiej wersji - jednak nie daje wyniku w rozsądnym czasie. t (2,4) jest w porządku, ale t (3,3) już mnie zatrzymał po 5 minutach. Jest jednak bardzo elegancki, prawda?

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

A teraz to samo co powyżej: użyj śmierdzącego mnożenia (nawet zyskujemy, odrzucając premię 5, ponieważ oszczędzamy 7 znaków: wygrana = 4 znaki :)

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

wezwanie:

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

czas pracy: 1ms.

Br ** nfuck, 128-5 = 123 bajtów

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

Dane wejściowe mają postać znaków z punktami kodowymi liczb pożądanych jako dane wejściowe. Dane wyjściowe są takie same.

Wyjaśnienie nadchodzi, kiedy mam czas poniżej. Czy dostaję punkty bonusowe za niestosowanie potęgowania, mnożenia, a nawet dodawania?

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!

Działa (testowane) do x 0, 0 x, x 1, 1 x, x 2, 2 3, i 2 4. Próbowałem 3 3, ale działało przez kilka godzin bez ukończenia (w mojej implementacji Java - prawdopodobnie nie optymalne) (EDYCJA: w EsotericIDE @ Timwi [To świetnie! Powinniście też spróbować]. Nie mam szczęścia.) Teoretycznie działa to do wielkości komórki konkretnej implementacji.

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

odwołać się:

t(2, 4)

Perl, 61 znaków

tutaj jest dziwny

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

stosowanie:

print t(2,4,1)

Mathematica , 40 33

Nie jest to do końca zgodne z regułami, ale i tak nie jest sprzeczne z najkrótszym kodem i mam nadzieję, że będzie to dla kogoś interesujące.

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

m[m@Sum]

To buduje funkcję „tetracji” po uruchomieniu, ale argumenty muszą być podawane w odwrotnej kolejności. Przykład:

m[m@Sum][3, 4]

1340780792994259709957402499820584612747936582059239337772356144372176 4030073546976801874298166903427690031858186486050853753882811946569946 433649006084096

Haskell:  58  51 znaków, z pomnożeniem lub bez.

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

Nie golfowany:

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

Krótsza definicja pochodzi od wstawienia „wypukłości” i zdefiniowania niestandardowej wersji „iteracji”. Niestety wynik jest niemożliwie nieefektywny, ale rozpoczęcie od (*) zamiast (+) daje przyzwoitą prędkość. W 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 znaków

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

Python, 112 znaków

Liczby powinny być pierwszym i drugim argumentem: python this.py 4 3
**operator nie jest używany.
*używany. Jest dość trywialny do wdrożenia, dokładnie tak **, ale kosztuje więcej niż 5 znaków.

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 znaków

EDIT: połączył dwie funkcje pi rdo jednego, oszczędzając kilka znaków.
Z 99 znaków 52 wykonuje rzeczywiste obliczenia (w tym definicje zmiennych). Pozostałe 47 służą do obsługi danych wejściowych i wyjściowych.
BŁĄD: Źle obsługuje moce 0 (np 0 2.). Powinien znaleźć ustalenie minimalnego kosztu. To nie jest błąd, zapomniałem, że 0 2jest niezdefiniowany.

Z powodzeniem radzi sobie 4 3, a nawet daje dokładny wynik. Może być jednak niedokładny w przypadku niektórych mniejszych liczb.
Drukuje liczbę ze znakiem końcowym .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());
}

Współczynnik, 187 znaków

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 .

Przed golfem:

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.

Nie usunąłem operatora mnożenia *. Gdybym to zrobił, musiałbym dodać logikę wyrażającą, że suma pustej sekwencji wynosi 0, a nie 1. Ta dodatkowa logika kosztowałaby więcej niż premia -5.

Łamacz reguł, 124 + 10 = 134 znaków

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

Ten program ma niższy wynik, ale operator potęgowania ^łamie reguły. Reguły mówią „(liczba znaków) + (10 * (liczba operatorów„ mocy ”))”, więc zastosowałem karę +10. Jednak zasady mówią również: „Nie używaj operatora„ mocy ”, więc każdy program, który przyjmuje tę karę, łamie zasady. Dlatego ten program składający się z 134 znaków nie jest poprawną odpowiedzią i muszę przedstawić mój dłuższy program składający się z 187 znaków jako moją odpowiedź.

Haskell 110-5 = 105

Tetration Peano Style. Jest to najbardziej szalenie wolne rozwiązanie, tylko ostrzeżenie, ale także pozwala uniknąć nawet dodawania.

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)

To zależy od tego, czy masz cierpliwość do wpisywania liczb Peano (i nie pokaże odpowiedzi. Jeśli naprawdę chcesz ją uruchomić, dodaj kilka wierszy (90 znaków):

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 znaki, bez mnożenia

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)

Pierwotnie zamierzałem użyć hacków do powtarzania ciągów, aby zrobić fałszywe pomnożenie, ale lubi zawodzić przy dużych wartościach. Mógłbym użyć dynamicznej kompilacji i łańcucha ładującego, aby zmniejszyć, ale robi się już późno ... Potrzebuję snu.

Wprowadzanie „4 3” do wyjść standardowego wejścia:

1.3407807929943e+154

VBA, 90 znaków

* Być może premia za brak pomnożenia nie jest wystarczająca. Myślę, że odpowiedź na pomnożenie nie jest o wiele bardziej interesująca, ale to jest golf golfowy, więc nie jest najlepszy. Oto odpowiedź bez *i lepsza (krótsza i lepsza ocena) odpowiedź:

90 znaków, brak operatorów mocy, używa mnożenia = 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 znaków, brak operatorów mocy, brak premii za pomnożenie (-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

UWAGA: VBA ma problemy z wydrukowaniem liczby, gdy wynik jest bardzo duży (tj. 4, 3), Ale oblicza się poprawnie, więc jeśli na przykład chcesz użyć tej liczby, dobrze byś poszedł. Również przepełnione (WIĘCEJ) liczby są większe 3, 4.

Perl 6 , 32 bajty

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

Wypróbuj online!

(1, { [*] a xx $_ } ... *)jest leniwą sekwencją, która generuje wieżę mocy, przy czym każdy element jest listą, która składa się z pierwszego parametru wejściowego azreplikowanego ( xx) kilka razy równego poprzedniemu elementowi ( $_), a następnie ta lista jest pomniejszana przez mnożenie ( [*]). Z tej sekwencji po prostu wyciągamy b-ty element.

Rachunek Lambda, 10-5

(przy użyciu kodowania Church i De Bruijn indeces )
λλ(1λ13)λ1

Wyjaśnienie

Bez indeksu De Bruijn λ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

Jeśli zdefiniujesz exp_a(x)=a^xten program, określa a↑↑b=exp_a^b(1)gdzie ^boznacza iterację funkcji.

Nie jestem pewien, czy jest to dozwolone, ponieważ cajest technicznie równoważne z a^ctym, jak to nigdy nie jest prawdziwym wbudowanym i tylko efektem ubocznym sposobu, w jaki liczby całkowite są kodowane w rachunku lambda.

JavaScript: 116 znaków

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”) Wyjścia:

1.3407807929942597e+154

Python (111) (113) nie *

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

Aktualizacja: należy dodać wartość początkową, aby dopasować t (X, 0) = 1

Haskell: 88-5 znaków bez mnożenia, 59 znaków z mnożeniem

Bez mnożenia:

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

Są prawdopodobnie sposoby, w które mógłbym trochę pograć w golfa.

Z mnożeniem:

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

I wreszcie program bez golfa:

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)

Jest to prawdopodobnie najprostszy sposób rozwiązania tego problemu, polegającego na zdefiniowaniu mnożenia jako powtarzanego dodawania, potęgowania jako powtarzanego mnożenia i tetracji jako powtarzanego potęgowania.

Rakieta 58 (nie *)

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

Common Lisp, 85 znaków

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

Próbowałem robić multiplikacje poprzez wielokrotne dodawanie, ale było to o wiele więcej niż 5 znaków. To samo dotyczy makroletów, deklaracje nie były warte zysków.

Kolejne rozwiązanie, zainspirowane rozwiązaniem Python firmy Boothby. To o 1 znak mniej niż powyższe rozwiązanie.

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

Python 3-68

(w tym 10-punktowa kara dla operatora)

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

Yabasic , 71 bajtów

Funkcja, która pobiera dane wejściowe ai bjest ciągiem rozdzielanym spacjami.

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

Wypróbuj online!

R , 71 - 5 = 66 bajtów

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

Wypróbuj online!

-5 za unikanie *, co było trudniejsze niż się spodziewałem. Eksploduje naprawdę szybko i nie będzie działać (chyba że będzie miał więcej pamięci), ale spełnia wszystkie niezbędne kryteria.