La función de Ackermann es notable por ser uno de los ejemplos más simples de una función total y computable que no es primitiva recursiva.
Usaremos la definición de A(m,n)
tomar dos enteros no negativos donde
A(0,n) = n+1
A(m,0) = A(m-1,1)
A(m,n) = A(m-1,A(m,n-1))
Puedes implementar
- una función con nombre o anónima que toma dos enteros como entrada, devuelve un entero o
- un programa que toma dos enteros separados por espacios o líneas nuevas en STDIN, imprimiendo un resultado en STDOUT.
No puede usar una función de Ackermann o una función de hiperexponenciación de una biblioteca, si existe, pero puede usar cualquier otra función de cualquier otra biblioteca. Se permite la exponenciación regular.
Su función debe poder encontrar el valor de A(m,n)
para m ≤ 3 yn ≤ 10 en menos de un minuto. Al menos debe terminar teóricamente en cualquier otra entrada: dado un espacio de pila infinito, un tipo Bigint nativo y un período de tiempo arbitrariamente largo, devolvería la respuesta. Editar: si su idioma tiene una profundidad de recursión predeterminada que es demasiado restrictiva, puede reconfigurarla sin costo de caracteres.
La presentación con el menor número de caracteres gana.
Aquí hay algunos valores, para verificar su respuesta:
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)
y es tan ingenuo como los demás? ¿Tengo que encontrar una solución que no sea de recursión, o también puedo "asumir un espacio de pila infinito" en estos casos? Estoy bastante seguro de que terminaría en un minuto.Respuestas:
Pyth , 19
Define
a
, que funciona como la función de Ackermann. Tenga en cuenta que esto requiere una mayor profundidad de recursión que el compilador pyth oficial permitido hasta hoy para calculara 3 10
, por lo que aumenté la profundidad de recursión. Esto no es un cambio en el idioma, solo en el compilador.Prueba:
Explicación:
Esencialmente, primero condiciona el valor de verdad de
G
si recurrir o devolver H + 1. Si es recurrente, el primer argumento siempre es G-1, y condiciona el valor de verdad deH
si usarloa(G,H-1)
como segundo argumento o usarlo1
como segundo argumento.fuente
DaGHR
aM
ya
parag
. (¿Cambió el orden de los argumentos a favor?
?)M
en su lugar, y sí, el?
orden de los argumentos cambió. Ahora es condición, verdadero, falso. Era cierto, condición, falso.M
!Haskell, 35
Esto define la función del operador
%
.esto funciona al darse cuenta de que
m%n
(dondea
está la función ackerman) para tiempos distintos de cerom
se(m-1)%
aplica . por ejemplo, se define como cuál es , y esto esn+1
1
3%2
2%(3%1)
2%(2%(3%0))
2%(2%(2%1))
fuente
0%n
lugar den+1
por precedenciaGolfScript (30)
Demostración en línea
Sin el
1>
(qué casos especialesA(1, n)
) toma 9 minutos calcularA(3, 10)
en la computadora en la que lo he probado. Con ese caso especial, es lo suficientemente rápido como para que la demostración en línea demore menos de 10 segundos.Tenga en cuenta que esta no es una traducción ingenua de la definición. La profundidad de recursión está limitada por
m
.Disección
fuente
1>
. Después de la eliminación (y el cambioif
a?
), la informática3 10 A
tarda 110 segundos con el intérprete en línea y seis segundos con el intérprete de Java.Cálculo binario lambda , 54 bits = 6,75 bytes
Hexdump:
Binario:
Esto es λ m . m (λ g . λ n . g ( n g 1)) (λ n . λ f . λ x . f ( n f x )), donde todos los números se representan como números de la Iglesia .
fuente
JavaScript, ES6,
4134 bytesEjecute esto en la última consola de Firefox y creará una función llamada a la
f
que puede llamar con diferentes valores dem
yn
similaresO
prueba el siguiente código en un último Firefox
fuente
Python 2.7.8 -
80, 54, 48, 4645(Créditos a xnor!)
Más legible, pero con 1 personaje más:
No es que tuviera que configurar
sys.setrecursionlimit(10000)
para obtener un resultadoA(3,10)
. El golf adicional con indexación lógica no funcionó debido a la profundidad de recursión que crece dramáticamente.fuente
1else
. La letra de inicioe
causa problemas al analizador porque los números se pueden escribir como1e3
.and/or
:A=lambda m,n:m and A(m-1,n<1or A(m,n-1))or-~n
1else
, la mayoría de las otras versiones no.1else
; me permite exprimir un char aquí y probablemente en otros lugares. Pero maldita sea, ¿es específico de la versión! Python 2.7.4 no lo permite. ¿Está utilizando una versión en línea con 2.7.8 o tendría que descargarla?1else
.J - 26 char
Hay una definición alternativa y más funcional de Ackermann:
Sucede que
Iter
es muy fácil escribir en J, porque J tiene una forma de pasarm-1
aAck
y también para definir el valor inicial deIter
ser 1. Explicado por explosión:Esto se basa en lo que J llama la forma
^:
gerundia, básicamente una forma de tener más control sobre todos los límites de una manera tácita (sin puntos).En la REPL:
Necesitamos definir
ack
por nombre para poder ponerlo en una tabla, porque$:
es una bestia horrible, fea y arremete contra cualquiera que intente entenderlo. Es autorreferencia, donde self se define como la frase verbal más grande que lo contiene.table
es un adverbio y, por lo tanto, me encantaría formar parte de la frase verbal si le da la oportunidad, por lo que debe atrapar$:
una definición con nombre para usarla.Editar: 24 char?
Años más tarde, encontré una solución que es dos caracteres más corta.
Sin embargo, es mucho más lento:
3 ack 8
toma más de un minuto en mi máquina. Esto se debe a que (1) uso un pliegue en/
lugar de iteración, por lo que J probablemente tenga que recordar más cosas de lo habitual, y (2) mientras0&<~
realiza el mismo cálculo(0<[)
, en realidad se ejecutan+1
veces antes de dar el paso recursivo cuando se invocam ack n
-0&<
sucede ser idempotente, por lo que no arruina el cálculo, pero sen
hace grande rápidamente yack
es altamente recursivo.Dudo que una máquina más poderosa pueda empujar el nuevo código en menos de un minuto, porque esta es una computadora donde el código antiguo puede encontrar
3 ack 10
en menos de 15 segundos.fuente
C - 41 bytes
Nada importante: los pequeños límites significan que todos los valores requeridos se pueden calcular en menos de 1 segundo siguiendo ingenuamente la definición de la función.
fuente
Javascript ES6 (34)
Implementación:
fuente
JavaScript (ES6) - 34
Y una prueba:
fuente
Coq, 40
Esta es una función de tipo
nat -> nat -> nat
. Dado que Coq solo permite la construcción de funciones totales, también sirve como una prueba formal de que la recurrencia de Ackermann está bien fundada.Manifestación:
Nota: Coq 8.5, lanzado después de este desafío, cambió
nat_iter
su nombre aNat.iter
.fuente
Raqueta 67
fuente
Mathematica, 46 bytes
Toma casi exactamente un minuto para
a[3,10]
. Tenga en cuenta que el límite de recursión predeterminado de Mathematica es demasiado pequeño paraa[3,8]
y más allá (al menos en mi máquina), pero eso se puede solucionar configurandofuente
If
ser una función es aún más lenta.m_~a~n_:=m~a~n=
...Javascript con lambdas, 34
Una respuesta típica, no puede acortar nada.
fuente
Haskell,
4844 caracteres (36 para la lista)Si bien no es tan breve como la otra solución de Haskell, esta es notable porque expresa la función de Ackermann como una lista infinita, lo que creo que es bastante ordenado. El resultado es una lista infinita (de listas infinitas) tal que en la posición [m, n] contiene el valor A (m, n) .
La lista infinita misma:
Como una función (para cumplir con la especificación):
La formulación se obtuvo al observar que el caso general / común para la función de Ackermann es usar el valor a la izquierda como índice en la fila de arriba. El caso base para esta recursión (es decir, la columna más a la izquierda de una fila, es decir, A (m, 0) ) es utilizar el segundo valor más a la izquierda en la fila de arriba. El caso base para esa recursión es el caso A (0, n) = n + 1 , es decir, la primera fila es
[1..]
.Por lo tanto, obtenemos
Luego simplemente agregamos otro nivel de iteración basado en ese patrón, y hacemos algunos malabarismos sin sentido .
fuente
iterate
i=iterate;ack=i ...
Tiny Lisp , 70 (fuera de competencia)
Esto se agota en la competencia, ya que el lenguaje es más nuevo que la pregunta, y tampoco se puede ejecutar
(A 3 10)
como se requiere en la pregunta, debido a un desbordamiento de pila.(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))))))
Esto define una función
A
que calcula la función de Ackermann. Formateado:Estamos utilizando todas las macros integradas (
d
(definir) yq
(cita) yi
(si)) y una función integrada (s
- restar) aquí.i
ejecuta su parte verdadera cuando la condición es un número> 0 (y de lo contrario la parte falsa), por lo que no tenemos que hacer una comparación explícita aquí.s
es la única operación aritmética disponible, la usamos tanto paran-1
/m-1
como(s n (s 0 1))
paran+1
.Tiny lisp está utilizando la optimización de recursión de cola, pero esto solo ayuda para la
A
llamada externa en el resultado, no para laA(m, n-1)
llamada que se usa para los parámetros.Con mi pequeña implementación de lisp en Ceylon en la JVM, funciona
(A 3 5) = 253
, pero parece descomponerse cuando intento calcular(A 2 125)
directamente (lo que debería dar el mismo resultado). Si calculo eso después(A 3 4) = 125
, la JVM parece poder optimizar las funciones lo suficiente como para incorporar algunas llamadas a funciones intermedias en mi intérprete, lo que permite una mayor profundidad de recursión. Extraño.La implementación de referencia se levanta
(A 3 5) = 253
y también(A 2 163) = 329
, pero no tiene éxito(A 2 164)
y, por lo tanto, aún menos(A 3 6) = (A 2 253)
.fuente
Ir,
260243240122 bytesNo vi que la pregunta permitiera anon funcs.
lejos de ser competitivo, pero estoy aprendiendo este idioma y quería probarlo.
úsalo como
go run ack.go
y luego proporciona dos números,m
yn
. si m> 4 o n> 30, el tiempo de ejecución puede ser superior a medio minuto.para
m=3 n=11
:editar : total guardado 17 bytes cambiando a
switch
más deif/else
punto e importacionesfuente
switch 0 {case m:r=n+1 case n:r=a(m-1,1) default:r=a(m-1,a(m,n-1))}
¡Laswitch
declaración de Go es tan bellamente flexible!Haskell:
8169 bytesa 3 10
Tarda unos 45 segundos.fuente
(no competidor) Pyth, 15 bytes
Pruébalo en línea! (uso de muestra de la función
g3T
agregada, lo que significag(3,10)
)fuente
(no competitiva) UGL ,
3130 bytesEntrada separada por nuevas líneas.
Pruébalo en línea!
(Se ha implementado como un ejemplo estándar en el intérprete).
fuente
Julia,
343128 bytesEsta es una función anónima con nombre. Es una implementación directa de la definición recursiva, que abusa de la capacidad de Julia para redefinir operadores .
Pruébalo en línea!
fuente
R -
5452He usado esto como una excusa para tratar de entender a R, por lo que probablemente esté muy mal hecho :)
Ejecución de ejemplo
Tengo un desbordamiento de pila para cualquier cosa más allá de eso
T-SQL- 222
Pensé que trataría de hacer que T-SQL lo hiciera también. Usé un método diferente porque la recursión no es tan agradable en SQL. Algo más de 4,2 lo bombardea.
fuente
{}
aunque no hay ayuda para el límite de desbordamiento de la pila, ya que R no tiene TCO ...brainfuck , 90 bytes
Pruébalo en línea!
Asume una implementación con un tamaño de celda de tamaño arbitrario, con IO como números. -6 bytes si no te importa usar celdas negativas.
Termina en aproximadamente 30 segundos durante 3,8 en el intérprete vinculado, siempre que marque la configuración correcta. Escriba los números ingresados antepuestos con
\
s, por ejemplo,3,9
is\3\9
.fuente
Tcl , 67 bytes
Pruébalo en línea!
Tcl , 77 bytes
Pruébalo en línea!
En el compilador en línea no se puede ejecutar debido al tiempo de espera, pero en un intérprete local de Tcl funciona bien. Realicé un perfil de cada llamada a la raíz para
A
funcionar, para ver cuánto tiempo tomó el cálculo para cada par{m,n}
sujeto para ser probado:Falla en el último par
{m,n}={3,10}
, ya que lleva un poco más de un minuto.Para valores más altos de
m
, será necesario aumentar elrecursionlimit
valor.Podría acortarlo a 65 bytes, pero no cumplirá con el requisito de la pregunta "Su función debe poder encontrar el valor de A (m, n) para m ≤ 3 yn ≤ 10 en menos de un minuto". Sin el
{}
tiempo de espera en TIO y no hacer la demostración de las últimas dos entradas.Tcl , 65 bytes
Pruébalo en línea!
fuente
J: 50
Devuelve en una fracción de segundo para 0 ... 3 vs 0 ... 10:
PD: el "0 sirve para hacer que A funcione en cada elemento individual, en lugar de engullir la matriz izquierda y derecha, y generar errores de longitud. Pero no es necesario para, por ejemplo, 9 = 2 A 3.
fuente
APL, 31
Muy claro. Utiliza el carácter once una vez para guardar un byte invirtiendo argumentos. Toma m como argumento izquierdo yn como argumento derecho.
TryAPL.org
fuente
Rubí, 65
Explicación
Esta es una traducción bastante sencilla del algoritmo dado en la descripción del problema.
Integer
esperan dos s.Hash
h
. El||=
operador se utiliza para calcular un valor que no se calculó previamente.a[3,10]
se calcula en ~ 0.1 segundos en mi máquina.Aquí hay una versión sin golf
fuente
a[3,10]
lanzar un SystemStackError en mi máquina ...m<1?(n+1):(n<1?a[m-1,1]:a[m-1,a[m,n-1]])
am<1?n+1:a[m-1,n<1?1:a[m,n-1]]
Mouse-2002 ,
9983 bytesfuente
Java, 274 bytes
Calcula
A(3,10)
en unos pocos segundos, y dada la memoria infinita y el espacio de pila, puede calcular cualquier combinación deb
yB
siempre que el resultado sea inferior a 2 2147483647 -1.fuente
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)));}
Ceilán,
888785Esta es una implementación sencilla. Formateado:
El alias guarda solo un byte, sin él (con escritura en
Integer
lugar deI
) obtendríamos 86 bytes. Se pueden guardar otros dos bytes reemplazándolos== 0
por< 1
dos veces.Con la configuración predeterminada de
ceylon run
, funcionará hastaA(3,12) = 32765
(yA(4,0) = 13
), peroA(3,13)
(y, por lo tanto, tambiénA(4,1)
) arrojará un error de desbordamiento de pila. (A(3,12)
Toma alrededor de 5 segundos,A(3,11)
alrededor de 3 en mi computadora).El uso
ceylon run-js
(es decir, ejecutar el resultado de la compilación de JavaScript en node.js) es mucho más lento (necesita 1 min 19 s paraA(3,10)
), y ya se interrumpeA(3, 11)
con un »Tamaño máximo de pila de llamadas excedido« (usando la configuración predeterminada) después de ejecutar 1 min 30 s.Ceilán sin recursión, 228
Como beneficio adicional, aquí hay una versión no recursiva (más larga, por supuesto, pero inmune a los desbordamientos de la pila, podría obtener un error de falta de memoria en algún momento).
Formateado:
Es bastante más lento en mi computadora que la versión recursiva:
A(3,11)
toma 9.5 segundos,A(3,12)
toma 34 segundos,A(3,13)
toma 2:08 minutos,A(3,14)
toma 8:25 minutos. (Originalmente tenía una versión que usaba iterables perezosos en lugar de las tuplas que tengo ahora, que era mucho más lenta, con el mismo tamaño).Un poco más rápido (21 segundos para
A(3,12)
) (pero también un byte más largo) es una versión que usa ens.push
lugar des.addAll
, pero que necesitaba llamarse varias veces para agregar múltiples números, ya que solo se necesita un solo número entero cada uno. Usar una LinkedList en lugar de una ArrayList es mucho más lento.fuente