A função Ackermann é notável por ser um dos exemplos mais simples de uma função computável total que não é recursiva primitiva.
Usaremos a definição de A(m,n)
obter dois números inteiros não negativos onde
A(0,n) = n+1
A(m,0) = A(m-1,1)
A(m,n) = A(m-1,A(m,n-1))
Você pode implementar
- uma função nomeada ou anônima, recebendo dois números inteiros como entrada, retornando um número inteiro ou
- um programa que usa dois números inteiros separados por espaço ou nova linha em STDIN, imprimindo um resultado em STDOUT.
Você não pode usar uma função Ackermann ou uma função de hiperexponenciação de uma biblioteca, se houver, mas você pode usar qualquer outra função de qualquer outra biblioteca. Exponenciação regular é permitida.
Sua função deve ser capaz de encontrar o valor de A(m,n)
para m ≤ 3 en n ≤ 10 em menos de um minuto. Ele deve pelo menos terminar teoricamente em quaisquer outras entradas: dado o espaço infinito da pilha, um tipo nativo de Bigint e um período arbitrariamente longo, ele retornaria a resposta. Editar: se o seu idioma tiver uma profundidade de recursão padrão muito restritiva, você poderá reconfigurá-lo sem nenhum custo de caracteres.
A submissão com o menor número de caracteres vence.
Aqui estão alguns valores, para verificar sua resposta:
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)
e acima tão ingênuo quanto os outros? Preciso criar uma solução sem recursão ou também posso "assumir espaço de pilha infinito" nesses casos? Estou bastante certo de que terminaria em um minuto.Respostas:
Pyth , 19
Define
a
, que funciona como a função Ackermann. Observe que isso requer uma profundidade de recursão mais alta do que o compilador pyth oficial permitiu até hojea 3 10
, então eu aumentei a profundidade de recursão. Isso não é uma alteração no idioma, apenas no compilador.Teste:
Explicação:
Essencialmente, ele primeiro condiciona o valor verdadeiro de
G
se deve recursar ou devolver H + 1. Se for recorrente, o primeiro argumento é sempre G-1 e condiciona o valor verdadeiro deH
usara(G,H-1)
ou não o segundo argumento ou1
o segundo argumento.fonte
DaGHR
toM
anda
tog
. (Did the order of arguments for?
change?)M
, e sim, a?
ordem dos argumentos alterada. Agora é condição, verdadeira, falsa. Era verdade, condição, falsa.M
!Haskell, 35
isso define a função do operador
%
.this works by noticing that
m%n
(wherea
is the ackerman function) for nonzerom
is(m-1)%
appliedn+1
times to1
. for example,3%2
is defined as2%(3%1)
which is2%(2%(3%0))
, and this is2%(2%(2%1))
fonte
0%n
instead ofn+1
because of precedenceGolfScript (30)
Online demo
Without the
1>
(which special-casesA(1, n)
) it takes 9 minutes to computeA(3, 10)
on the computer I've tested it on. With that special case it's fast enough that the online demo takes less than 10 seconds.Note that this isn't a naïve translation of the definition. The recursion depth is bounded by
m
.Dissection
fonte
1>
. After removal (and changingif
to?
), computing3 10 A
takes 110 seconds with the online interpreter and six seconds with the Java interpreter.Binary lambda calculus, 54 bits = 6.75 bytes
Hexdump:
Binary:
This is λm. m (λg. λn. g (n g 1)) (λn. λf. λx. f (n f x)), where all numbers are represented as Church numerals.
fonte
JavaScript, ES6,
4134 bytesRun this in a latest Firefox Console and it will create a function called
f
which you can call with different values ofm
andn
likeOR
try the code below in a latest Firefox
fonte
Python 2.7.8 -
80, 54, 48, 4645(Credits to xnor!)
More readable, but with 1 more character:
Not that I had to set
sys.setrecursionlimit(10000)
in order to get a result forA(3,10)
. Further golfing using logical indexing did not work due to the dramatically growing recursion depth.fonte
1else
. The start lettere
causes trouble for the parser because numbers can be written like1e3
.and/or
:A=lambda m,n:m and A(m-1,n<1or A(m,n-1))or-~n
1else
, most other versions don't.1else
; it lets me squeeze out a char here and probably other places. But darn is it version-specific! Python 2.7.4 doesn't allow it. Are you using an online version with 2.7.8 or would I have to download it?1else
as well.J - 26 char
There is an alternate, more functional definition of Ackermann:
It so happens that
Iter
is very easy to write in J, because J has a way of passing in them-1
toAck
and also to define the initial value ofIter
to be 1. Explained by explosion:This relies on what J calls the gerund form of
^:
—basically a way to have more control over all the bounds in a tacit (point-free) fashion.At the REPL:
We need to define
ack
by name to be able to put it in a table, because$:
is a horrible, ugly beast and lashes out at anyone who attempts to understand it. It is self-reference, where self is defined as the largest verb phrase containing it.table
is an adverb and so would love to become part of the verb phrase if you give it the chance, so you have to trap$:
in a named definition to use it.Edit: 24 char?
Years later, I found a solution which is two characters shorter.
It's a lot slower, though:
3 ack 8
takes over a minute on my machine. This is because (1) I use a fold/
instead of iteration, so J probably has to remember more things than usual, and (2) while0&<~
performs the same calculation as(0<[)
, it actually gets executedn+1
times before taking the recursive step when invokingm ack n
—0&<
happens to be idempotent, so it doesn't ruin the calculation, butn
gets big fast andack
is highly recursive.I am doubtful that a more powerful machine could push the new code under a minute, because this is a computer where the old code can find
3 ack 10
in less than 15 seconds.fonte
C - 41 bytes
Nothing to it--the small limits mean that all the required values can be calculated in less than 1 second by naively following the function definition.
fonte
Javascript ES6 (34)
Implementation:
fonte
JavaScript (ES6) - 34
And a test:
fonte
Coq, 40
This is a function of type
nat -> nat -> nat
. Since Coq only allows the construction of total functions, it also serves as a formal proof that the Ackermann recurrence is well-founded.Demo:
Note: Coq 8.5, released after this challenge, renamed
nat_iter
toNat.iter
.fonte
Racket 67
fonte
Mathematica, 46 bytes
Takes pretty much exactly a minute for
a[3,10]
. Note that Mathematica's default recursion limit is too small fora[3,8]
and beyond (at least on my machine), but that can be fixed by configuringfonte
If
being a function is even slower.m_~a~n_:=m~a~n=
...Javascript with lambdas, 34
A tipical answer, can't make anything shorter.
fonte
Haskell,
4844 chars (36 for the list)While not as short as the other Haskell solution, this one is notable because it expresses the Ackermann function as an infinite list, which I think is kinda neat. The result is an infinite list (of infinite lists) such that at position [m,n] it holds the value A(m,n).
The infinite list itself:
As a function (to comply with the specification):
The formulation was derived by observing that the general/common case for the Ackermann function is to use the value to the left as an index in the row above. The base case for this recursion (i.e. the leftmost column of a row, i.e. A(m,0)) is to use the second left-most value in the row above. The base case for that recursion is the A(0,n) = n+1 case, i.e. the first row is
[1..]
.Thus, we get
Then we simply add another level of iteration based on that pattern, and do some pointless juggling.
fonte
iterate
to a single letter name i.e.i=iterate;ack=i ...
Tiny Lisp, 70 (out of competition)
This runs out of competition, as the language is newer than the question, and it also doesn't succeed to run the
(A 3 10)
as required in the question, due to a stack overflow.(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))))))
This defines a function
A
which calculates the Ackermann function. Formatted:We are using all builtin macros (
d
(define) andq
(quote) andi
(if)) and one builtin function (s
– subtract) here.i
executes its true part when the condition is a number > 0 (and otherwise the false part), so we don't have to do an explicit comparison here.s
is the only arithmetic operation available, we use it for then-1
/m-1
, as well as as(s n (s 0 1))
forn+1
.Tiny lisp is using tail recursion optimization, but this only helps for the outer
A
call in the result, not for theA(m, n-1)
call which is used for the parameters.With my tiny lisp implementation in Ceylon on the JVM, it works up to
(A 3 5) = 253
, but it seems to break down when trying to calculate(A 2 125)
directly (which should give the same result). If calculating that after(A 3 4) = 125
, the JVM seems to got to optimize the functions enough to inline some intermediate function calls in my interpreter, allowing more recursion depth. Strange.The reference implementation gets up to
(A 3 5) = 253
and also(A 2 163) = 329
, but doesn't succeed(A 2 164)
, and therefore even less(A 3 6) = (A 2 253)
.fonte
Go,
260243240122 bytesI didn't see that the question allowed anon funcs.
far from competitive but i'm learning this language and i wanted to test it out.
use it like
go run ack.go
and then supply two numbers,m
andn
. if m>4 or n>30, execution time may be in excess of half a minute.for
m=3 n=11
:edit: saved total 17 bytes by switching to
switch
overif/else
and dot-importsfonte
switch 0 {case m:r=n+1 case n:r=a(m-1,1) default:r=a(m-1,a(m,n-1))}
Go'sswitch
statement is so beautifully flexible!Haskell:
8169 bytesa 3 10
takes about 45 seconds.fonte
(non-competing) Pyth, 15 bytes
Try it online! (sample usage of the function
g3T
added, which meansg(3,10)
)fonte
(non-competing) UGL,
3130 bytesInput separated by newlines.
Try it online!
(It has been implemented as a standard example in the interpreter.)
fonte
Julia,
343128 bytesThis is a named anonymous function. It is a straightforward implementation of the recursive definition, abusing Julia's ability to redefine operators.
Try it online!
fonte
R -
5452I've used this as an excuse to try and get my head around R, so this is probably really badly done:)
Example run
I get a stack overflow for anything beyond that
T-SQL- 222
I thought I would try to get T-SQL to do it as well. Used a different method because recursion isn't that nice in SQL. Anything over 4,2 bombs it.
fonte
{}
although there's no helping the stack overflow limit, since R doesn't have TCO...brainfuck, 90 bytes
Try it online!
Assumes an implementation with arbitrary sized cell size, with IO as numbers. -6 bytes if you don't mind using negative cells.
Finishes in about 30 seconds for 3,8 in the linked interpreter, provided you tick the correct settings. Type inputted numbers prepended with
\
s, e.g.3,9
is\3\9
.fonte
Tcl, 67 bytes
Try it online!
Tcl, 77 bytes
Try it online!
In the online compiler it fails to run due to time-out, but in a local Tcl interpreter it runs well. I profiled of each root call to
A
function, to see how much time the calculation took for each pair{m,n}
subject to be tested:It fails for the last pair
{m,n}={3,10}
, as it takes a very little more than one minute.For higher values of
m
, it will be needed to increase therecursionlimit
value.I coult get it shorter to 65 bytes, but it will not meet the question's requirement "Your function must be able to find the value of A(m,n) for m ≤ 3 and n ≤ 10 in less than a minute.". Without the
{}
it will timeout on TIO and not do the demo of the last two entries.Tcl, 65 bytes
Try it online!
fonte
J : 50
Returns in a fraction of a second for 0...3 vs 0 ... 10:
PS: the "0 serves to make A work on each single element, instead of gobbling up the left and right array, and generating length errors. But it's not needed for eg. 9 = 2 A 3 .
fonte
APL, 31
Pretty straightforward. Uses the ⍨ character once to save one byte by reversing arguments. Takes m as the left argument and n as the right argument.
TryAPL.org
fonte
Ruby, 65
Explanation
This is a pretty straightforward translation of the algorithm given in the problem description.
Integer
s are expected.Hash
h
. The||=
operator is used to calculate a value that wasn't previously calculated.a[3,10]
is calculated in ~0.1 sec on my machine.Here's an ungolfed version
fonte
a[3,10]
throw a SystemStackError on my machine...m<1?(n+1):(n<1?a[m-1,1]:a[m-1,a[m,n-1]])
tom<1?n+1:a[m-1,n<1?1:a[m,n-1]]
Mouse-2002,
9983 bytesfonte
Java, 274 bytes
It calculates
A(3,10)
in a few seconds, and given infinite memory and stack space, it can calculate any combination ofb
andB
as long as the result is below 22147483647-1.fonte
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,
888785This is a straightforward implementation. Formatted:
The alias saves just one byte, without it (with writing
Integer
instead ofI
) we would get to 86 bytes. Another two bytes can be saved by replacing== 0
by< 1
twice.With the default settings of
ceylon run
, it will work up toA(3,12) = 32765
(andA(4,0) = 13
), butA(3,13)
(and therefore alsoA(4,1)
) will throw a stack overflow error. (A(3,12)
takes about 5 seconds,A(3,11)
about 3 on my computer.)Using
ceylon run-js
(i.e. running the result of compiling to JavaScript on node.js) is a lot slower (needs 1 min 19 s forA(3,10)
), and breaks already forA(3, 11)
with a »Maximum call stack size exceeded« (using default settings) after running for 1 min 30 s.Ceylon without recursion, 228
As a bonus, here is a non-recursive version (longer, of course, but immune to stack overflows – might get an out-of-memory error at some point).
Formatted:
It is quite slower on my computer than the recursive version:
A(3,11)
takes 9.5 seconds,A(3,12)
takes 34 seconds,A(3,13)
takes 2:08 minutes,A(3,14)
takes 8:25 minutes. (I originally had a version using lazy iterables instead of the tuples I now have, which was even much slower, with the same size).A bit faster (21 seconds for
A(3,12)
) (but also one byte longer) is a version usings.push
instead ofs.addAll
, but that needed to be called several times to add multiple numbers, as it takes just a single Integer each. Using a LinkedList instead of an ArrayList is a lot slower.fonte