La función de Ackermann

35

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...
Algoritmo de tiburón
fuente
15
¿Cómo no se ha preguntado esto antes?
Hobbies de Calvin
99
Creo que sería más divertido hacer este código más rápido
Sp3000
22
Votación negativa porque no hay desafío aquí. La respuesta obvia, simplemente implementando ingenuamente la función exactamente de acuerdo con su definición, siempre será la mejor respuesta. Entonces, la pregunta es simplemente "¿Qué idioma tiene el menor número de caracteres en la expresión obvia de la función de Ackermann?" El verdadero ganador es el lenguaje de programación, no la persona que escribió el programa obvio en él.
David Richerby
1
¿Qué sucede si el límite de recursión de mi idioma es demasiado bajo para calcular 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.
Martin Ender
55
@DavidRicherby "La respuesta obvia [...] siempre será la mejor respuesta". Esto no es cierto para todos los idiomas. Me siento un poco sucio por tener solo un ejemplo en el idioma de mi hogar, pero hay varias formas de expresar Ackermann y en algunos idiomas puede obtener ahorros al usar ese hecho. Esta era mi intención para el desafío.
algorithmshark

Respuestas:

7

Pyth , 19

DaGHR?atG?aGtHH1GhH

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 calcular a 3 10, por lo que aumenté la profundidad de recursión. Esto no es un cambio en el idioma, solo en el compilador.

Prueba:

$ time pyth -c "DaGHR?atG?aGtHH1GhH           ;a 3 10"
8189

real    0m0.092s
user    0m0.088s
sys     0m0.000s

Explicación:

DaGH                     def a(G,H):
    R                    return
    ?          G                (if G:
     atG                              (a(G-1,
        ?    H                               (if H:
         aGtH                                      a(G,H-1)
              1                               else:1)
                hH               else:H+1)

Esencialmente, primero condiciona el valor de verdad de Gsi recurrir o devolver H + 1. Si es recurrente, el primer argumento siempre es G-1, y condiciona el valor de verdad de Hsi usarlo a(G,H-1)como segundo argumento o usarlo 1como segundo argumento.

isaacg
fuente
En Pyth moderno (supongo que esto se agregó después de este desafío) creo que puedes cambiar más o menos DaGHRa My apara g. (¿Cambió el orden de los argumentos a favor ??)
Lynn
@Mauris Sí, puede usar Men su lugar, y sí, el ?orden de los argumentos cambió. Ahora es condición, verdadero, falso. Era cierto, condición, falso.
isaacg
Hechos de la historia de @Lynn Fun Pyth: Esta pregunta realmente influyó en el cambio (al menos) de dos cosas sobre Pyth: ¡ el límite de recurrencia y el cambio aM !
FryAmTheEggman
23

Haskell, 35

0%n=1+n
m%n=iterate((m-1)%)1!!(n+1)

Esto define la función del operador %.

esto funciona al darse cuenta de que m%n(donde aestá la función ackerman) para tiempos distintos de cero mse (m-1)%aplica . por ejemplo, se define como cuál es , y esto esn+113%22%(3%1)2%(2%(3%0))2%(2%(2%1))

orgulloso Haskeller
fuente
lástima que no puedo usar en 0%nlugar de n+1por precedencia
orgulloso haskeller
wow, esto ha estado mal por tanto tiempo, y nadie, incluyéndome a mí, ¿lo notó? buen trabajo. Parece que copié por error la primera versión de la respuesta, que era defectuosa, tal vez por error o porque pensé que funcionaba.
orgulloso Haskeller
12

GolfScript (30)

{1$1>{1\){1$(\A}*\;}{+)}if}:A;

Demostración en línea

Sin el 1>(qué casos especiales A(1, n)) toma 9 minutos calcular A(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

{             # Function boilerplate
  1$          # Get a copy of m: stack holds m n m
  1>{         # (Optimisation): if m is greater than 1
    1         #   Take this as the value of A(m, -1)
    \){       #   Repeat n+1 times:
              #     Stack: m A(m, i-1)
      1$(\    #     Stack: m m-1 A(m, i-1)
      A       #     Stack: m A(m, i)
    }*
    \;        #   Lose that unwanted copy of m
  }{          # Else
    +)        #   A(m in {0, 1}, n) = m + n + 1
  }if
}:A;          # Function boilerplate
Peter Taylor
fuente
En CJam, no lo necesitarías 1>. Después de la eliminación (y el cambio ifa ?), la informática 3 10 Atarda 110 segundos con el intérprete en línea y seis segundos con el intérprete de Java.
Dennis
7

Cálculo binario lambda , 54 bits = 6,75 bytes

Hexdump:

00000000: 1607 2d88 072f 68                        ..-../h

Binario:

000101100000011100101101100010000000011100101111011010

Esto es λ m . mg . λ 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 .

Anders Kaseorg
fuente
6

JavaScript, ES6, 41 34 bytes

f=(m,n)=>m?f(m-1,!n||f(m,n-1)):n+1

Ejecute esto en la última consola de Firefox y creará una función llamada a la fque puede llamar con diferentes valores de my nsimilares

f(3,2) // returns 29

O

prueba el siguiente código en un último Firefox

f=(m,n)=>m?f(m-1,!n||f(m,n-1)):n+1

B.onclick=_=>alert(f(+M.value, +N.value))
#M,#N{max-width:15px;border: 1px solid;border-width:0 0 1px 0}
<div>f(<input id=M />,<input id=N />)</div><br><button id=B>Evaluate</button>

Optimizador
fuente
Probar esto con 0,1 en Chrome no da resultado.
Nzall
3
Por favor lea, esto solo funciona en el último Firefox debido a ES6
Optimizer
Wow ... tenemos 4 soluciones JS prácticamente idénticas, todas a 34 bytes. Nunca he visto eso antes.
ETHproductions
6

Python 2.7.8 - 80, 54, 48, 46 45

A=lambda m,n:m and A(m-1,n<1or A(m,n-1))or-~n

(Créditos a xnor!)

Más legible, pero con 1 personaje más:

A=lambda m,n:n+(m<1or A(m-1,n<1or A(m,n-1))-n)

No es que tuviera que configurar sys.setrecursionlimit(10000)para obtener un resultado A(3,10). El golf adicional con indexación lógica no funcionó debido a la profundidad de recursión que crece dramáticamente.

Falko
fuente
Me sale un error de sintaxis en el 1else. La letra de inicio ecausa problemas al analizador porque los números se pueden escribir como 1e3.
xnor
Guardado algunos caracteres cambiando a and/or:A=lambda m,n:m and A(m-1,n<1or A(m,n-1))or-~n
xnor
@xnor: ¡Gracias por el consejo! Vea esta discusión para el problema de análisis. Python 2.7.8 acepta 1else, la mayoría de las otras versiones no.
Falko
Gracias por puntero sobre 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?
xnor
@xnor: es una instalación fuera de línea. ideone.com , por ejemplo, tampoco se analiza 1else.
Falko
6

J - 26 char

($:^:(<:@[`]`1:)^:(0<[)>:)

Hay una definición alternativa y más funcional de Ackermann:

Ack 0 n = n+1
Ack m n = Iter (Ack (m-1)) n
Iter f 0 = f 1
Iter f n = f (Iter f (n-1))

Sucede que Iteres muy fácil escribir en J, porque J tiene una forma de pasar m-1a Acky también para definir el valor inicial de Iterser 1. Explicado por explosión:

(                      >:)  NB. increment n
                ^:(0<[)     NB. if m=0, do nothing to n+1; else:
   ^:                       NB. iterate...
($:                      )  NB.   self ($: is recursion)
     (<:@[     )            NB.   with left arg m-1
          `]                NB.   n+1 times
            `1:             NB.   starting on 1

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:

   3 ($:^:(<:@[`]`1:)^:(0<[)>:) 3
61
   ack =: ($:^:(<:@[`]`1:)^:(0<[)>:)
   (i.4) ack"0 table (i.11)
+-----+------------------------------------------+
|ack"0|0  1  2  3   4   5   6    7    8    9   10|
+-----+------------------------------------------+
|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|
+-----+------------------------------------------+
   6!:2 '3 ($:^:(<:@[`]`1:)^:(0<[)>:) 10'  NB. snugly fits in a minute
58.5831

Necesitamos definir ackpor 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. tablees 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.

(0&<~(<:@#~$:/@,1:^:)>:)

Sin embargo, es mucho más lento: 3 ack 8toma 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) mientras 0&<~realiza el mismo cálculo (0<[), en realidad se ejecuta n+1veces antes de dar el paso recursivo cuando se invoca m ack n- 0&<sucede ser idempotente, por lo que no arruina el cálculo, pero se nhace grande rápidamente y ackes 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 10en menos de 15 segundos.

Algoritmo de tiburón
fuente
5

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.

A(m,n){return!m?n+1:A(m-1,n?A(m,n-1):1);}


int main()
{
    int m,n;
    for(m = 0; m <= 3; m++)
    for(n = 0; n <= 10; n++)
    printf("%d %d %d\n", m,n,A(m,n));
    return 0;
}
Feersum
fuente
5

Javascript ES6 (34)

a=(m,n)=>m?a(m-1,n?a(m,n-1):1):n+1

Implementación:

a=(m,n)=>m?a(m-1,n?a(m,n-1):1):n+1
td[colspan="2"] input{width: 100%;}
<table><tbody><tr><td>m=</td><td><input id="m" type="number" value="0" /></td></tr><tr><td>n=</td><td><input id="n" type="number" value="0" /></td></tr><tr><td colspan="2"><input type="button" value="Calculate!" onclick="document.getElementById('out').value=a(document.getElementById('m').value, document.getElementById('n').value)" /></td></tr><tr><td colspan="2"><input id="out" disabled="disabled" type="text" /></td></tr></tbody></table>

kitcar2000
fuente
4

JavaScript (ES6) - 34

A=(m,n)=>m?A(m-1,!n||A(m,n-1)):n+1

Y una prueba:

> A=(m,n)=>m?A(m-1,!n||A(m,n-1)):n+1;s=new Date().getTime();console.log(A(3,10),(new Date().getTime() - s)/1000)
8189 16.441
core1024
fuente
3

Coq, 40

nat_rec _ S(fun _ b n=>nat_iter(S n)b 1)

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:

Welcome to Coq 8.4pl6 (November 2015)

Coq < Compute nat_rec _ S(fun _ b n=>nat_iter(S n)b 1) 3 10.
     = 8189
     : nat

Nota: Coq 8.5, lanzado después de este desafío, cambió nat_itersu nombre a Nat.iter.

Anders Kaseorg
fuente
2

Raqueta 67

(define(a m n)(if(= m 0)(+ n 1)(a(- m 1)(if(= n 0)1(a m(- n 1))))))
Matthew Butterick
fuente
2

Mathematica, 46 bytes

0~a~n_:=n+1
m_~a~n_:=a[m-1,If[n<1,1,a[m,n-1]]]

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 para a[3,8]y más allá (al menos en mi máquina), pero eso se puede solucionar configurando

$RecursionLimit = Infinity
Martin Ender
fuente
1
Wow, ¿estás diciendo que JS es más de 25 veces más rápido que Mathematica?
Optimizador
@Optimizer Al menos en lo que respecta a la recursividad ... Supongo que, en parte, es porque tiene que descubrir cada vez qué definición usar, y Ifser una función es aún más lenta.
Martin Ender
1
Con la memorización, lleva 0.07 segundos. Es decir m_~a~n_:=m~a~n=...
Mark Adler
@MarkAdler ¡Esa es una muy buena manera de hacer una memorización en Mathematica!
Martin Ender
2

Javascript con lambdas, 34

A=(m,n)=>m?A(m-1,n?A(m,n-1):1):n+1

Una respuesta típica, no puede acortar nada.

Qwertiy
fuente
2

Haskell, 48 44 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:

iterate(tail.(`iterate`1).(!!))[1..]

Como una función (para cumplir con la especificación):

i=iterate;m%n=i(tail.(`i`1).(!!))[1..]!!m!!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

let a0 = [1..]
let a1 = tail $ iterate (a0 !!) 1  -- 'tail' because iterate starts by applying
let a2 = tail $ iterate (a1 !!) 1  -- the function 0 times
-- etc

Luego simplemente agregamos otro nivel de iteración basado en ese patrón, y hacemos algunos malabarismos sin sentido .

Luciérnaga
fuente
Puede iteratei=iterate;ack=i ...
usar
@proudhaskeller oh sí, no pensé en eso. ¡Gracias! Pedir prestado el uso de su nombre de operador también.
FireFly
2

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 Aque calcula la función de Ackermann. Formateado:

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

Estamos utilizando todas las macros integradas ( d(definir) y q(cita) y i(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í.

ses la única operación aritmética disponible, la usamos tanto para n-1/ m-1como (s n (s 0 1))para n+1.

Tiny lisp está utilizando la optimización de recursión de cola, pero esto solo ayuda para la Allamada externa en el resultado, no para la A(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) = 253y 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).

Paŭlo Ebermann
fuente
esto podría ser competitivo, excepto para el espacio en blanco y el paréntesis;)
cat
2

Ir, 260 243 240 122 bytes

No vi que la pregunta permitiera anon funcs.

lejos de ser competitivo, pero estoy aprendiendo este idioma y quería probarlo.

func (m,n int)int{r:=0
switch{case m==0&&n!=0:r=n+1
case m!=0&&n==0:r=a(m-1,1)
case m!=0&&n!=0:r=a(m-1,a(m,n-1))}
return r}

úsalo como go run ack.goy luego proporciona dos números, my n. si m> 4 o n> 30, el tiempo de ejecución puede ser superior a medio minuto.

para m=3 n=11:

$ time go run ack
16381
real    0m1.434s
user    0m1.432s
sys     0m0.004s

editar : total guardado 17 bytes cambiando a switchmás de if/elsepunto e importaciones

gato
fuente
1
¡Puedes hacerlo aún mejor! switch 0 {case m:r=n+1 case n:r=a(m-1,1) default:r=a(m-1,a(m,n-1))}¡La switchdeclaración de Go es tan bellamente flexible!
EMBLEMA
@EMBLEM Gracias, ha pasado tanto tiempo desde que escribí una línea de Go, pero me alegra ver que hay otros jugadores de Go-golf sobre: ​​D
cat
1

Haskell: 81 69 bytes

a::Int->Int->Int
a 0 n=n+1
a m 0=a (m-1) 1
a m n=a (m-1) a m (n-1)

a 3 10 Tarda unos 45 segundos.

SophR
fuente
1
este es el código de golf, por lo que debe intentar tener el código más corto posible. por ejemplo, eliminar espacios innecesarios y el tipo explícito
orgulloso haskeller
también estás extrañando a los padres en la cuarta línea
orgulloso haskeller
1

(no competidor) Pyth, 15 bytes

M?GgtG?HgGtH1hH

Pruébalo en línea! (uso de muestra de la función g3Tagregada, lo que significa g(3,10))

Monja permeable
fuente
1

(no competitiva) UGL , 31 30 bytes

iiRuldr%l%lR$d%rd:u%d:%+uRu:ro

Entrada separada por nuevas líneas.

Pruébalo en línea!

(Se ha implementado como un ejemplo estándar en el intérprete).

Monja permeable
fuente
1

Julia, 34 31 28 bytes

m\n=m>0?~-m\(n<1||m\~-n):n+1

Esta 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!

Dennis
fuente
1

R - 54 52

He usado esto como una excusa para tratar de entender a R, por lo que probablemente esté muy mal hecho :)

a=function(m,n)"if"(m,a(m-1,"if"(n,a(m,n-1),1)),n+1)

Ejecución de ejemplo

> a(3,8)
[1] 2045

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.

DECLARE @m INT=4,@n INT=1;WITH R AS(SELECT 2 C, 1 X UNION ALL   SELECT POWER(2,C),X+1FROM R)SELECT IIF(@m=0,@n+1,IIF(@m=1,@n+2,IIF(@m=2,2*@n+3,IIF(@m=3,POWER(2,@n+3)-3,IIF(@m=4,(SELECT TOP(1)C FROM R WHERE x= @n+3)-3,-1)))))
MickyT
fuente
para su presentación de R, parece que no necesita, {}aunque no hay ayuda para el límite de desbordamiento de la pila, ya que R no tiene TCO ...
Giuseppe
@Giuseppe gracias ... en mi defensa, era nuevo en eso entonces :)
MickyT
1

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,9is \3\9.

Jo King
fuente
1

Tcl , 67 bytes

proc tcl::mathfunc::A m\ n {expr {$m?A($m-1,$n?A($m,$n-1):1):$n+1}}

Pruébalo en línea!


Tcl , 77 bytes

proc A m\ n {expr {$m?[A [expr $m-1] [expr {$n?[A $m [expr $n-1]]:1}]]:$n+1}}

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 Afuncionar, para ver cuánto tiempo tomó el cálculo para cada par {m,n}sujeto para ser probado:

m=0, n=0, A=1, time=3.5e-5 seconds
m=0, n=1, A=2, time=2e-6 seconds
m=0, n=2, A=3, time=8e-6 seconds
m=0, n=3, A=4, time=1e-6 seconds
m=0, n=4, A=5, time=2e-6 seconds
m=0, n=5, A=6, time=1e-6 seconds
m=0, n=6, A=7, time=1e-6 seconds
m=0, n=7, A=8, time=1e-6 seconds
m=0, n=8, A=9, time=1e-6 seconds
m=0, n=9, A=10, time=0.0 seconds
m=0, n=10, A=11, time=1e-6 seconds
m=1, n=0, A=2, time=4e-6 seconds
m=1, n=1, A=3, time=6e-6 seconds
m=1, n=2, A=4, time=1e-5 seconds
m=1, n=3, A=5, time=1.2e-5 seconds
m=1, n=4, A=6, time=1.5e-5 seconds
m=1, n=5, A=7, time=2e-5 seconds
m=1, n=6, A=8, time=2e-5 seconds
m=1, n=7, A=9, time=2.6e-5 seconds
m=1, n=8, A=10, time=3e-5 seconds
m=1, n=9, A=11, time=3e-5 seconds
m=1, n=10, A=12, time=3.3e-5 seconds
m=2, n=0, A=3, time=8e-6 seconds
m=2, n=1, A=5, time=2.2e-5 seconds
m=2, n=2, A=7, time=3.9e-5 seconds
m=2, n=3, A=9, time=6.3e-5 seconds
m=2, n=4, A=11, time=9.1e-5 seconds
m=2, n=5, A=13, time=0.000124 seconds
m=2, n=6, A=15, time=0.000163 seconds
m=2, n=7, A=17, time=0.000213 seconds
m=2, n=8, A=19, time=0.000262 seconds
m=2, n=9, A=21, time=0.000316 seconds
m=2, n=10, A=23, time=0.000377 seconds
m=3, n=0, A=5, time=2.2e-5 seconds
m=3, n=1, A=13, time=0.000145 seconds
m=3, n=2, A=29, time=0.000745 seconds
m=3, n=3, A=61, time=0.003345 seconds
m=3, n=4, A=125, time=0.015048 seconds
m=3, n=5, A=253, time=0.059836 seconds
m=3, n=6, A=509, time=0.241431 seconds
m=3, n=7, A=1021, time=0.971836 seconds
m=3, n=8, A=2045, time=3.908884 seconds
m=3, n=9, A=4093, time=15.926341 seconds
m=3, n=10, A=8189, time=63.734713 seconds

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 el recursionlimitvalor.


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

proc tcl::mathfunc::A m\ n {expr $m?A($m-1,$n?A($m,$n-1):1):$n+1}

Pruébalo en línea!

sergiol
fuente
0

J: 50

>:@]`(1$:~<:@[)`(<:@[$:[$:_1+])@.(0>.[:<:@#.,&*)M.

Devuelve en una fracción de segundo para 0 ... 3 vs 0 ... 10:

   A=:>:@]`(1$:~<:@[)`(<:@[$:[$:_1+])@.(0>.[:<:@#.,&*)M.
   timespacex 'res=:(i.4) A"0 table (i.11)'
0.0336829 3.54035e6
   res
┌───┬──────────────────────────────────────────┐
│A"0│0  1  2  3   4   5   6    7    8    9   10│
├───┼──────────────────────────────────────────┤
│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│
└───┴──────────────────────────────────────────┘

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.

jpjacobs
fuente
codegolf.stackexchange.com/a/40174/48934 ¡ Has sido golpeado!
Leaky Nun
0

APL, 31

{⍺=0:⍵+1⋄⍵=0:1∇⍨⍺-1⋄(⍺-1)∇⍺∇⍵-1}

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

Shujal
fuente
0

Rubí, 65

h,a={},->m,n{h[[m,n]]||=m<1?(n+1):(n<1?a[m-1,1]:a[m-1,a[m,n-1]])}

Explicación

Esta es una traducción bastante sencilla del algoritmo dado en la descripción del problema.

  • La entrada se toma como argumentos para una lambda. Se Integeresperan dos s.
  • Para la velocidad y evitar errores de desbordamiento de pila, las respuestas están en el memoized 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

h = {}
a = lambda do |m,n|
  h[[m,n]] ||= if m < 1 
    n + 1
  elsif n < 1
    a[m-1,1]
  else
    a[m-1,a[m,n-1]]
  end
end
britishtea
fuente
a[3,10]lanzar un SystemStackError en mi máquina ...
TuxCrafting
Nitpicks de golf: podría cambiar 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]]
Simply Beautiful Art el
0

Mouse-2002 , 99 83 bytes

$Y1%j:j.0=m:2%k:k.0=n:m.n.>[k.1+!|m.n.<[#Y,j.1-,1;|m.n.*0=[#Y,j.1-,#Y,j.,k.1+;;]]]@
gato
fuente
0

Java, 274 bytes

import java.math.*;class a{BigInteger A(BigInteger b,BigInteger B){if(b.equals(BigInteger.ZERO))return B.add(BigInteger.ONE);if(B.equals(BigInteger.ZERO))return A(b.subtract(BigInteger.ONE),BigInteger.ONE);return A(b.subtract(BigInteger.ONE),A(b,B.subtract(BigInteger.ONE)));}}

Calcula A(3,10)en unos pocos segundos, y dada la memoria infinita y el espacio de pila, puede calcular cualquier combinación de by Bsiempre que el resultado sea inferior a 2 2147483647 -1.

dorukayhan quiere a Monica de vuelta
fuente
Sé que ha pasado un tiempo, pero puedes jugar esto a 185 bytes :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)));}
Kevin Cruijssen
0

Ceilán, 88 87 85

alias I=>Integer;I a(I m,I n)=>m<1then n+1else(n<1then a(m-1,1)else a(m-1,a(m,n-1)));

Esta es una implementación sencilla. Formateado:

alias I => Integer;
I a(I m, I n) =>
        m < 1
        then n + 1
        else (n < 1
            then a(m - 1, 1)
            else a(m - 1, a(m, n - 1)));

El alias guarda solo un byte, sin él (con escritura en Integerlugar de I) obtendríamos 86 bytes. Se pueden guardar otros dos bytes reemplazándolos == 0por < 1dos veces.

Con la configuración predeterminada de ceylon run, funcionará hasta A(3,12) = 32765(y A(4,0) = 13), pero A(3,13)(y, por lo tanto, también A(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 para A(3,10)), y ya se interrumpe A(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).

import ceylon.collection{A=ArrayList}Integer a(Integer[2]r){value s=A{*r};value p=s.addAll;while(true){if(exists m=s.pop()){if(exists n=s.pop()){if(n<1){p([m+1]);}else if(m<1){p([n-1,1]);}else{p([n-1,n,m-1]);}}else{return m;}}}}

Formateado:

import ceylon.collection {
    A=ArrayList
}

Integer a(Integer[2] r) {
    value s = A { *r };
    value p = s.addAll;
    while (true) {
        if (exists m = s.pop()) {
            if (exists n = s.pop()) {
                if (n < 1) {
                    p([m + 1]);
                } else if (m < 1) {
                    p([n - 1, 1]);
                } else {
                    p([n - 1, n, m - 1]);
                }
            } else {
                // stack is empty
                return m;
            }
        }
    }
}

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 en s.pushlugar de s.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.

Paŭlo Ebermann
fuente