Funkcja Ackermanna wyróżnia się jako jeden z najprostszych przykładów całkowitej, obliczalnej funkcji, która nie jest prymitywną rekurencyjną.
Użyjemy definicji A(m,n)
przyjmowania dwóch nieujemnych liczb całkowitych gdzie
A(0,n) = n+1
A(m,0) = A(m-1,1)
A(m,n) = A(m-1,A(m,n-1))
Możesz wdrożyć
- nazwana lub anonimowa funkcja przyjmująca dwie liczby całkowite jako dane wejściowe, zwracająca liczbę całkowitą lub
- program przyjmujący dwie liczby całkowite oddzielone spacją lub znakiem nowej linii na STDIN, drukujący wynik do STDOUT.
Nie możesz używać funkcji Ackermanna ani funkcji hipereponentyzacji z biblioteki, jeśli taka istnieje, ale możesz użyć dowolnej innej funkcji z dowolnej innej biblioteki. Dozwolone jest regularne potęgowanie.
Twoja funkcja musi być w stanie znaleźć wartość A(m,n)
dla m ≤ 3 in ≤ 10 w mniej niż minutę. Musi przynajmniej teoretycznie kończyć się na innych wejściach: biorąc pod uwagę nieskończoną przestrzeń stosu, natywny typ Biginta i dowolnie długi okres czasu, zwróci odpowiedź. Edycja: Jeśli Twój język ma domyślną głębokość rekurencji, która jest zbyt restrykcyjna, możesz ją ponownie skonfigurować bez żadnych kosztów znaków.
Zgłoszenie z najmniejszą liczbą znaków wygrywa.
Oto kilka wartości, aby sprawdzić swoją odpowiedź:
A | n=0 1 2 3 4 5 6 7 8 9 10
-----+-----------------------------------------------------------------
m=0 | 1 2 3 4 5 6 7 8 9 10 11
1 | 2 3 4 5 6 7 8 9 10 11 12
2 | 3 5 7 9 11 13 15 17 19 21 23
3 | 5 13 29 61 125 253 509 1021 2045 4093 8189
4 | 13 65533 big really big...
A(3,8)
i przewyższyć tak naiwnie jak inne? Czy muszę wymyślić rozwiązanie nierekurencyjne, czy też mogę po prostu „założyć nieskończone miejsce na stosie” w tych przypadkach? Jestem całkiem pewien, że to skończy się w ciągu minuty.Odpowiedzi:
Pyth , 19 lat
Definiuje
a
, który działa jako funkcja Ackermanna. Zauważ, że wymaga to większej głębokości rekurencji niż oficjalny kompilator Pyth, który do tej pory mógł obliczaća 3 10
, więc zwiększyłem głębokość rekurencji. To nie jest zmiana języka, tylko kompilatora.Test:
Wyjaśnienie:
Zasadniczo, najpierw
G
zależy od wartości prawdy, czy powrócić, czy zwrócić H + 1. Jeśli jest rekurencyjny, pierwszym argumentem jest zawsze G-1 i warunkuje on wartość prawdy,H
czy użyća(G,H-1)
jako drugi argument, czy użyć1
jako drugi argument.źródło
DaGHR
doM
ia
dog
. (Czy kolejność argumentów za?
zmianą?)M
zamiast tego użyć i tak,?
zmieniono kolejność argumentów. Teraz jest warunek, prawda, fałsz. To była prawda, warunek, fałsz.M
!Haskell, 35
określa to funkcję operatora
%
.to działa, zauważając, że
m%n
(gdziea
jest funkcja Ackerman) dla niezerowegom
jest(m-1)%
stosowanen+1
razy1
. na przykład3%2
jest zdefiniowane jako2%(3%1)
to2%(2%(3%0))
, co jest i to jest2%(2%(2%1))
źródło
0%n
zamiast zn+1
powodu pierwszeństwaGolfScript (30)
Demo online
Bez
1>
(w jakich przypadkach specjalnychA(1, n)
) obliczenie zajmuje 9 minutA(3, 10)
na komputerze, na którym go przetestowałem. W tym specjalnym przypadku jest wystarczająco szybki, aby demo online zajęło mniej niż 10 sekund.Zauważ, że nie jest to naiwne tłumaczenie definicji. Głębokość rekurencji jest ograniczona przez
m
.Sekcja
źródło
1>
. Po usunięciu (i zmianieif
na?
) obliczenia3 10 A
zajmują 110 sekund w przypadku interpretera online i sześć sekund w przypadku interpretera Java.Binarny rachunek lambda , 54 bity = 6,75 bajtów
Hexdump:
Dwójkowy:
To jest λ m . m (λ g . λ n . g ( n g 1)) (λ n . λ f . λ x . f ( n f x )), gdzie wszystkie liczby są reprezentowane jako liczby kościelne .
źródło
JavaScript, ES6,
4134 bajtówUruchom to w najnowszej konsoli Firefox, aby utworzyć funkcję o nazwie,
f
którą możesz wywoływać z różnymi wartościamim
in
podobnymiLUB
wypróbuj poniższy kod w najnowszym Firefoksie
źródło
Python 2.7.8 -
80, 54, 48, 4645(Kredyty xnor!)
Bardziej czytelny, ale z 1 dodatkową postacią:
Nie żebym musiał ustawić
sys.setrecursionlimit(10000)
, aby uzyskać wynikA(3,10)
. Dalsza gra w golfa przy użyciu logicznego indeksowania nie działała z powodu dramatycznie rosnącej głębokości rekurencji.źródło
1else
. Litera początkowae
powoduje problemy dla analizatora składni, ponieważ liczby można zapisywać jak1e3
.and/or
:A=lambda m,n:m and A(m-1,n<1or A(m,n-1))or-~n
1else
, większość innych wersji nie.1else
; pozwala mi wycisnąć char tutaj i prawdopodobnie w innych miejscach. Ale do cholery, to jest specyficzne dla wersji! Python 2.7.4 nie pozwala na to. Czy używasz wersji online z wersją 2.7.8, czy powinienem ją pobrać?1else
.J - 26 char
Istnieje alternatywna, bardziej funkcjonalna definicja Ackermann:
Zdarza się, że
Iter
bardzo łatwo jest napisać w J, ponieważ J ma sposób na przejściem-1
do,Ack
a także zdefiniowanie początkowej wartościIter
1. Wyjaśnione przez wybuch:Zależy to od tego, co J nazywa formą
^:
gerunda - zasadniczo sposób na większą kontrolę nad wszystkimi granicami w sposób milczący (bez punktów).W REPL:
Musimy zdefiniować
ack
po imieniu, aby móc postawić go na stole, ponieważ$:
jest okropną, brzydką bestią i rzuca się na każdego, kto próbuje to zrozumieć. Jest to odniesienie do siebie, gdzie ja jest zdefiniowane jako największa fraza czasownika zawierająca je.table
jest przysłówkiem i dlatego chciałbym stać się częścią wyrażenia czasownika, jeśli dasz mu szansę, więc musisz$:
użyć nazwanej definicji, aby go użyć.Edycja: 24 znaki?
Wiele lat później znalazłem rozwiązanie, które jest o dwa znaki krótsze.
Jest jednak o wiele wolniejszy:
3 ack 8
zajmuje ponad minutę na moim komputerze. Wynika to z tego, że (1) używam fold/
zamiast iteracji, więc J prawdopodobnie musi zapamiętać więcej rzeczy niż zwykle, i (2)0&<~
wykonując te same obliczenia(0<[)
, ponieważ faktycznie wykonujen+1
czasy przed wykonaniem kroku rekurencyjnego podczas wywoływaniam ack n
-0&<
zdarza się być idempotentnym, więc nie rujnuje obliczeń, alen
szybko się powiększa iack
jest wysoce rekurencyjny.Wątpię, czy mocniejsza maszyna mogłaby przesunąć nowy kod
3 ack 10
w mniej niż minutę, ponieważ jest to komputer, na którym stary kod może znaleźć w mniej niż 15 sekund.źródło
C - 41 bajtów
Nic z tego - małe limity oznaczają, że wszystkie wymagane wartości można obliczyć w czasie krótszym niż 1 sekunda, naiwnie przestrzegając definicji funkcji.
źródło
JavaScript ES6 (34)
Realizacja:
źródło
JavaScript (ES6) - 34
I test:
źródło
Coq, 40
Jest to funkcja typu
nat -> nat -> nat
. Ponieważ Coq pozwala jedynie na konstruowanie funkcji całkowitych, służy również jako formalny dowód, że wznowienie Ackermanna jest uzasadnione.Próbny:
Uwaga: Coq 8.5, wydany po tym wyzwaniu, został przemianowany
nat_iter
naNat.iter
.źródło
Rakieta 67
źródło
Mathematica, 46 bajtów
Zajmuje prawie dokładnie minutę
a[3,10]
. Zauważ, że domyślny limit rekurencji Mathematiki jest za mały naa[3,8]
i poza nim (przynajmniej na moim komputerze), ale można to naprawić, konfigurującźródło
If
bycie funkcją jest jeszcze wolniejsze.m_~a~n_:=m~a~n=
...JavaScript z lambdas, 34
Typowa odpowiedź: nic nie może skrócić.
źródło
Haskell,
4844 znaków (36 dla listy)Chociaż nie jest tak krótkie jak inne rozwiązanie Haskell, to jest godne uwagi, ponieważ wyraża funkcję Ackermanna jako nieskończoną listę, która moim zdaniem jest całkiem fajna. Wynikiem jest lista nieskończona (z list nieskończonych) taka, że w pozycji [m, n] zawiera wartość A (m, n) .
Sama lista nieskończona:
W funkcji (zgodnie ze specyfikacją):
Sformułowanie wyprowadzono z obserwacji, że ogólnym / powszechnym przypadkiem funkcji Ackermanna jest użycie wartości po lewej stronie jako indeksu w powyższym wierszu. Podstawowym przypadkiem tej rekurencji (tj. Skrajna lewa kolumna wiersza, tj. A (m, 0) ) polega na użyciu drugiej wartości znajdującej się najbardziej na lewo w powyższym wierszu. Podstawowym przypadkiem tej rekurencji jest przypadek A (0, n) = n + 1 , tzn. Pierwszy wiersz to
[1..]
.Tak otrzymujemy
Następnie po prostu dodajemy kolejny poziom iteracji w oparciu o ten wzorzec i przeprowadzamy bezsensowne żonglowanie.
źródło
iterate
do pojedynczej litery, tj.i=iterate;ack=i ...
Tiny Lisp , 70 (poza zawodami)
To kończy się z konkurencją, ponieważ język jest nowszy niż pytanie, a także nie udaje mu się uruchomić
(A 3 10)
zgodnie z wymaganiami w pytaniu z powodu przepełnienia stosu.(d A(q((m n)(i m(i n(A(s m 1)(A m(s n 1)))(A(s m 1)1))(s n(s 0 1))))))
Definiuje funkcję,
A
która oblicza funkcję Ackermanna. Sformatowany:Używamy tutaj wszystkich wbudowanych makr (
d
(zdefiniuj) iq
(cytat) ii
(jeśli)) oraz jednej wbudowanej funkcji (s
- odejmij).i
wykonuje swoją prawdziwą część, gdy warunkiem jest liczba> 0 (a w przeciwnym razie część fałszywa), więc nie musimy tutaj robić wyraźnego porównania.s
jest jedyną dostępną operacją arytmetyczną, używamy jej dlan-1
/m-1
, a także(s n (s 0 1))
dlan+1
.Tiny lisp korzysta z optymalizacji rekurencji ogona, ale to pomaga tylko w
A
wywołaniu zewnętrznym w wyniku, a nie wA(m, n-1)
wywołaniu, które jest używane dla parametrów.Dzięki mojej niewielkiej implementacji lisp na Cejlonie na JVM, działa
(A 3 5) = 253
, ale wydaje się, że się psuje, gdy próbuję obliczyć(A 2 125)
bezpośrednio (co powinno dać ten sam wynik). Jeśli obliczam to później(A 3 4) = 125
, JVM wydaje się być w stanie zoptymalizować funkcje na tyle, aby wstawić niektóre pośrednie wywołania funkcji w moim interpreterie, pozwalając na większą głębokość rekurencji. Dziwne.Implementacja referencyjna wstaje
(A 3 5) = 253
, a także(A 2 163) = 329
, ale nie powiedzie się(A 2 164)
, a więc nawet mniej(A 3 6) = (A 2 253)
.źródło
Idź,
260243240122 bajtówNie widziałem, żeby pytanie pozwalało na anony.
daleki od rywalizacji, ale uczę się tego języka i chciałem go przetestować.
użyj go jak,
go run ack.go
a następnie podaj dwie liczby,m
in
. jeśli m> 4 lub n> 30, czas wykonania może przekraczać pół minuty.dla
m=3 n=11
:edycja : zapisano ogółem 17 bajtów, przechodząc do
switch
overif/else
-importu i importowania kropkamiźródło
switch 0 {case m:r=n+1 case n:r=a(m-1,1) default:r=a(m-1,a(m,n-1))}
Goswitch
jest tak pięknie elastyczne!Haskell:
8169 bajtówa 3 10
zajmuje około 45 sekund.źródło
(niekonkurencyjny) Pyth, 15 bajtów
Wypróbuj online! (przykładowe użycie
g3T
dodanej funkcji , co oznaczag(3,10)
)źródło
(niekonkurencyjny) UGL ,
3130 bajtówWejście oddzielone znakami nowej linii.
Wypróbuj online!
(Został zaimplementowany jako standardowy przykład w tłumaczu.)
źródło
Julia,
343128 bajtówJest to nazwana anonimowa funkcja. Jest to prosta implementacja definicji rekurencyjnej, nadużywająca zdolności Julii do redefiniowania operatorów .
Wypróbuj online!
źródło
R -
5452Użyłem tego jako pretekstu, aby spróbować ominąć R, więc prawdopodobnie jest to naprawdę źle zrobione :)
Przykładowy przebieg
Dostaję przepełnienie stosu dla wszystkiego poza tym
T-SQL-222
Myślałem, że spróbuję również zmusić T-SQL do zrobienia tego. Zastosowano inną metodę, ponieważ rekurencja nie jest tak ładna w SQL. Wszystko powyżej 4,2 bombarduje to.
źródło
{}
chociaż nie ma limitu przepełnienia stosu, ponieważ R nie ma TCO ...pieprzenie mózgu , 90 bajtów
Wypróbuj online!
Zakłada implementację o dowolnym rozmiarze komórki, z IO jako liczbami. -6 bajtów, jeśli nie masz nic przeciwko użyciu komórek ujemnych.
Kończy się za około 30 sekund dla 3,8 w połączonym tłumaczu, pod warunkiem, że zaznaczysz prawidłowe ustawienia. Wpisz wprowadzone liczby poprzedzone
\
s, np .3,9
Jest\3\9
.źródło
Tcl , 67 bajtów
Wypróbuj online!
Tcl , 77 bajtów
Wypróbuj online!
W kompilatorze online nie działa z powodu przekroczenia limitu czasu, ale w lokalnym interpretatorze Tcl działa dobrze. Profilowałem każde wywołanie
A
funkcji root , aby zobaczyć, ile czasu zajęło obliczenie każdej{m,n}
testowanej pary :Nie powiedzie się dla ostatniej pary
{m,n}={3,10}
, ponieważ zajmuje to niewiele więcej niż minutę.Dla wyższych wartości
m
konieczne będzie zwiększenie tejrecursionlimit
wartości.Nie mogę go skrócić do 65 bajtów, ale nie spełni on wymagania pytania „Twoja funkcja musi być w stanie znaleźć wartość A (m, n) dla m ≤ 3 i n ≤ 10 w mniej niż minutę.”. Bez
{}
tego upłynie limit czasu na TIO i nie zrobi demo dwóch ostatnich wpisów.Tcl , 65 bajtów
Wypróbuj online!
źródło
J: 50
Zwraca w ułamku sekundy dla 0 ... 3 vs 0 ... 10:
PS: „0 służy do tego, aby A działało na każdym elemencie, zamiast pożerać lewą i prawą tablicę i generować błędy długości. Ale nie jest to potrzebne, np. 9 = 2 A 3.
źródło
APL, 31
Całkiem proste. Używa znaku once jeden raz, aby zapisać jeden bajt poprzez odwrócenie argumentów. Przyjmuje m jako lewy argument, a n jako prawy argument.
TryAPL.org
źródło
Ruby, 65
Wyjaśnienie
Jest to dość proste tłumaczenie algorytmu podanego w opisie problemu.
Integer
Spodziewane są .Hash
h
. The||=
Operatora jest stosowane do obliczenia wartości, która nie była poprzednio.a[3,10]
jest obliczany na ~ 0,1 sekundy na moim komputerze.Oto wersja bez golfa
źródło
a[3,10]
wrzuć SystemStackError na moją maszynę ...m<1?(n+1):(n<1?a[m-1,1]:a[m-1,a[m,n-1]])
nam<1?n+1:a[m-1,n<1?1:a[m,n-1]]
Mouse-2002 ,
9983 bajtówźródło
Java, 274 bajty
Oblicza się
A(3,10)
w ciągu kilku sekund, a biorąc pod uwagę nieskończoną pamięć i przestrzeń stosu, może obliczyć dowolną kombinacjęb
iB
dopóki wynik jest poniżej 2 2147483647 -1.źródło
import java.math.*;BigInteger A(BigInteger b,BigInteger B){return b.equals(B.ZERO)?B.add(B.ONE):B.equals(B.ZERO)?A(b.subtract(B.ONE),B.ONE):A(b.subtract(B.ONE),A(b,B.subtract(B.ONE)));}
Ceylon,
888785Jest to prosta implementacja. Sformatowany:
Alias zapisuje tylko jeden bajt, bez niego (z zapisem
Integer
zamiastI
) uzyskalibyśmy 86 bajtów. Kolejne dwa bajty można zapisać, zastępując== 0
je< 1
dwukrotnie.Przy domyślnych ustawieniach
ceylon run
będzie działał doA(3,12) = 32765
(iA(4,0) = 13
), aleA(3,13)
(i dlatego teżA(4,1)
) zgłosi błąd przepełnienia stosu. (A(3,12)
zajmuje to około 5 sekund,A(3,11)
około 3 na moim komputerze).Używanie
ceylon run-js
(tj. Uruchamianie wyniku kompilacji do JavaScript na node.js) jest znacznie wolniejsze (wymaga 1 min 19 sA(3,10)
) i już się psujeA(3, 11)
z „Przekroczeniem maksymalnego stosu wywołań” (przy użyciu ustawień domyślnych) po uruchomieniu dla 1 min 30 s.Cejlon bez rekurencji, 228
Jako bonus, tutaj jest wersja nierekurencyjna (oczywiście dłuższa, ale odporna na przepełnienie stosu - w pewnym momencie może pojawić się błąd braku pamięci).
Sformatowany:
Na moim komputerze jest on wolniejszy niż wersja rekurencyjna:
A(3,11)
zajmuje 9,5 sekundy,A(3,12)
zajmuje 34 sekundy,A(3,13)
trwa 2:08 minut,A(3,14)
zajmuje 8:25 minut. (Pierwotnie miałem wersję z leniwymi iteratorami zamiast krotek, które mam teraz, które były nawet znacznie wolniejsze, o tym samym rozmiarze).Nieco szybciej (21 sekund na
A(3,12)
) (ale także o jeden bajt dłużej) jest wersja używającas.push
zamiasts.addAll
, ale trzeba było ją kilkakrotnie wywoływać, aby dodać wiele liczb, ponieważ każda z nich zajmuje tylko jedną liczbę całkowitą. Korzystanie z LinkedList zamiast ArrayList jest znacznie wolniejsze.źródło