La fonction Ackermann

35

La fonction Ackermann est remarquable pour être l’un des exemples les plus simples d’une fonction totale calculable qui n’est pas récursive primitive.

Nous allons utiliser la définition de la A(m,n)prise en deux entiers non négatifs où

A(0,n) = n+1
A(m,0) = A(m-1,1)
A(m,n) = A(m-1,A(m,n-1))

Vous pouvez implémenter

  • une fonction nommée ou anonyme prenant deux entiers en entrée, renvoyant un entier, ou
  • un programme prenant deux entiers séparés par une ligne ou un espace sur STDIN, en imprimant un résultat vers STDOUT.

Vous ne pouvez pas utiliser une fonction Ackermann ou une fonction d'hyperexponentiation d'une bibliothèque, s'il en existe une, mais vous pouvez utiliser toute autre fonction d'une autre bibliothèque. Une exponentiation régulière est autorisée.

Votre fonction doit pouvoir trouver la valeur de A(m,n)pour m ≤ 3 et n ≤ 10 en moins d'une minute. Il doit au moins théoriquement se terminer par toute autre entrée: avec un espace de pile infini, un type Bigint natif et une période de temps arbitrairement longue, la réponse sera renvoyée. Éditer: Si votre langue a une profondeur de récursion par défaut trop restrictive, vous pouvez la reconfigurer sans frais de caractères.

La soumission avec le plus petit nombre de caractères gagne.

Voici quelques valeurs pour vérifier votre réponse:

  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...
algorithmeshark
la source
15
Comment cela n'a-t-il pas été demandé auparavant ??
Les passe-temps de Calvin
9
Je pense que ce serait plus amusant de faire ce code le plus rapide
Sp3000
22
Votez parce qu'il n'y a pas de défi ici. La réponse évidente - appliquer naïvement la fonction exactement selon sa définition - restera toujours la meilleure solution. La question est donc simplement "Quelle langue a le moins de caractères dans l'expression évidente de la fonction d'Ackermann?" Le vrai gagnant est le langage de programmation, pas la personne qui a écrit le programme le plus évident.
David Richerby
1
Et si la limite de récursion de ma langue est trop basse pour être calculée A(3,8)et supérieure aussi naïvement que les autres? Dois-je proposer une solution de non-récursion ou puis-je simplement "supposer un espace infini" dans ces cas? Je suis assez certain, cela se terminerait dans une minute.
Martin Ender
5
@DavidRicherby "La réponse évidente [...] sera toujours la meilleure réponse." Ce n'est pas le cas de toutes les langues. Je me sens un peu sale de n'avoir qu'un exemple dans ma langue maternelle, mais il existe de nombreuses manières d'exprimer Ackermann et dans certaines langues, vous pouvez réaliser des économies en utilisant ce fait. C'était mon intention pour le défi.
algorithmshark

Réponses:

7

Pyth , 19

DaGHR?atG?aGtHH1GhH

Définit ace qui fonctionne comme la fonction Ackermann. Notez que cela nécessite une profondeur de récursion supérieure à celle calculée par le compilateur pyth officiel jusqu'à ce jour a 3 10, donc j'ai augmenté la profondeur de récursivité. Ce n'est pas un changement de langage, mais uniquement pour le compilateur.

Tester:

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

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

Explication:

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)

Essentiellement, il conditionne d'abord la valeur de vérité, Gqu'il s'agisse de récidiver ou de renvoyer H + 1. S'il est récurrent, le premier argument est toujours G-1 et conditionne la valeur de vérité, à Hsavoir s'il doit être utilisé a(G,H-1)comme second argument ou s'il doit être utilisé 1comme second argument.

isaacg
la source
Dans Pyth moderne (je suppose que cela a été ajouté après ce défi) Je pense que vous pouvez plus ou moins de changements DaGHRà Met aà g. (L'ordre des arguments en faveur du ?changement est-il correct?)
Lynn
@Mauris Oui, vous pouvez utiliser à la Mplace, et oui, l' ?ordre des arguments a changé. C'est maintenant condition, vrai, faux. C'était vrai, condition, faux.
isaacg
Faits historiques sur l'histoire de Pyth @Lynn Fun: Cette question a en fait incité isaacg à modifier (au moins) deux choses à propos de Pyth: la limite de récursivité et le changement deM !
FryAmTheEggman
23

Haskell, 35 ans

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

ceci définit la fonction d'opérateur %.

cela fonctionne en remarquant que m%n(où aest la fonction ackerman) mest (m-1)%appliqué à des n+1temps différents de zéro 1. par exemple, 3%2est défini comme 2%(3%1)ce qui est 2%(2%(3%0)), et c'est2%(2%(2%1))

fier haskeller
la source
dommage que je ne puisse pas utiliser 0%nau lieu de à n+1cause de la précédence
fier haskeller
wow, cela a été mal pendant si longtemps, et personne, y compris moi-même, remarqué? bon travail. il semble donc que j'ai copié par erreur la première version de la réponse, qui était erronée, peut-être par erreur ou parce que je pensais que cela fonctionnait.
fier haskeller
12

GolfScript (30)

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

Démo en ligne

Sans le 1>(cas particuliers A(1, n)), A(3, 10)le calcul sur l'ordinateur sur lequel je l'ai testé prend 9 minutes . Avec ce cas spécial, il est assez rapide que la démonstration en ligne prenne moins de 10 secondes.

Notez que ce n'est pas une traduction naïve de la définition. La profondeur de récursivité est délimitée par m.

Dissection

{             # 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
la source
Dans CJam, vous n'en auriez pas besoin 1>. Après le retrait (et le passage ifà ?), l'informatique 3 10 Aprend 110 secondes avec l'interprète en ligne et six secondes avec l'interpréteur Java.
Dennis
7

Calcul lambda binaire , 54 bits = 6,75 octets

Hexdump:

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

Binaire:

000101100000011100101101100010000000011100101111011010

C'est λ m . mg . λ n . g ( n g 1)) (λ n . λ f . λ x . f ( n f x )), où tous les nombres sont représentés par des chiffres Eglise .

Anders Kaseorg
la source
6

JavaScript, ES6, 41 à 34 octets

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

Exécutez ceci dans une dernière console de Firefox et cela créera une fonction appelée fque vous pouvez appeler avec différentes valeurs de mand nlike

f(3,2) // returns 29

OU

essayez le code ci-dessous dans un dernier 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>

Optimiseur
la source
Le test avec 0,1 dans Chrome ne donne aucun résultat.
Nzall
3
En lecture, cela ne fonctionne que dans le dernier Firefox en raison de ES6
Optimizer
Wow ... nous avons 4 solutions JS pratiquement identiques, toutes à 34 octets. Je n'ai jamais vu ça auparavant.
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édits à xnor!)

Plus lisible, mais avec 1 caractère supplémentaire:

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

Non pas que je devais régler sys.setrecursionlimit(10000)pour obtenir un résultat A(3,10). La poursuite de la pratique du golf à l'aide d'une indexation logique n'a pas fonctionné en raison de la profondeur de plus en plus grande de la récursion.

Falko
la source
Je reçois une erreur de syntaxe le 1else. La lettre einitiale pose des problèmes à l'analyseur, car les nombres peuvent être écrits comme suit 1e3.
xnor
Enregistré quelques caractères en passant à and/or:A=lambda m,n:m and A(m-1,n<1or A(m,n-1))or-~n
xnor
@xnor: Merci pour le tuyau! Voir cette discussion pour le problème de l'analyse syntaxique. Python 2.7.8 accepte 1else, la plupart des autres versions ne le font pas.
Falko
Merci pour le pointeur à propos de 1else; cela me permet de faire sortir un omble ici et probablement ailleurs. Mais c'est vraiment spécifique à la version! Python 2.7.4 ne le permet pas. Utilisez-vous une version en ligne avec 2.7.8 ou devrais-je la télécharger?
xnor
@xnor: C'est une installation hors ligne. ideone.com , par exemple, ne parvient pas à analyser 1elseégalement.
Falko
6

J - 26 caractères

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

Il existe une autre définition, plus fonctionnelle, d’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))

Il se trouve qu’il Iterest très facile d’écrire en J, parce que J a le moyen de transmettre le m-1à Acket de définir la valeur initiale de Iter1. Expliqué par explosion:

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

Cela repose sur ce que J appelle la forme générale de ^:- un moyen fondamental d'avoir plus de contrôle sur toutes les limites de manière tacite (sans point).

Au 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

Nous devons définir ackpar nom pour pouvoir le mettre dans un tableau, car $:c'est une bête horrible et laide qui frappe furieusement tous ceux qui tentent de le comprendre. C'est une référence à soi, où self est défini comme la phrase du verbe le plus grand qui la contient. tableest un adverbe et aimerait donc faire partie de la phrase du verbe si vous lui en donnez la chance. Vous devez donc vous en tenir $:à une définition nommée pour l'utiliser.


Edit: 24 caractères?

Des années plus tard, j'ai trouvé une solution composée de deux caractères plus courts.

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

C'est beaucoup plus lent, cependant: cela 3 ack 8prend plus d'une minute avec ma machine. C'est parce que (1) j'utilise un repli /au lieu de l'itération, donc J doit probablement se rappeler plus de choses que d'habitude, et (2) tout en 0&<~effectuant le même calcul que (0<[), il est en réalité exécuté plusieurs n+1fois avant de passer à l'étape récursive lors de l'appel m ack n- 0&<cela se produit être idempotent, cela ne gâche donc pas le calcul, mais ndevient rapide et acktrès récursif.

Je doute qu'une machine plus puissante puisse afficher le nouveau code en moins d'une minute, car il s'agit d'un ordinateur sur lequel l'ancien code peut être trouvé 3 ack 10en moins de 15 secondes.

algorithmeshark
la source
5

C - 41 octets

Rien à faire - les petites limites signifient que toutes les valeurs requises peuvent être calculées en moins de 1 seconde en suivant naïvement la définition de la fonction.

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
la source
5

Javascript ES6 (34)

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

La mise en oeuvre:

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
la source
4

JavaScript (ES6) - 34

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

Et un test:

> 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
la source
3

Coq, 40

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

C'est une fonction de type nat -> nat -> nat. Coq n'autorisant que la construction de fonctions globales, il sert également de preuve formelle du bien-fondé de la récurrence d'Ackermann.

Démo:

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

Note: Coq 8.5, publié après ce défi, renommé nat_iterpour Nat.iter.

Anders Kaseorg
la source
2

Raquette 67

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

Mathematica, 46 octets

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

Prend à peu près exactement une minute pour a[3,10]. Notez que la limite de récursivité par défaut de Mathematica est trop petite pour a[3,8]et au-delà (du moins sur ma machine), mais cela peut être corrigé en configurant

$RecursionLimit = Infinity
Martin Ender
la source
1
Wow, vous dites donc que JS est plus de 25 fois plus rapide que Mathematica?
Optimiseur
@Optimizer Au moins quand il s’agit de récursivité ... J'imagine en partie s'il faut qu'il détermine à chaque fois quelle définition utiliser, et If être une fonction est encore plus lent.
Martin Ender
1
Avec la mémorisation, cela prend 0,07 seconde. C'est-à-dire m_~a~n_:=m~a~n=...
Mark Adler
@MarkAdler C'est un très bon moyen de mémoriser dans Mathematica!
Martin Ender
2

Javascript avec lambdas, 34

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

Une réponse typique, ne peut rien raccourcir.

Qwertiy
la source
2

Haskell, 48 44 caractères (36 pour la liste)

Bien que n'étant pas aussi courte que l'autre solution Haskell, celle-ci est remarquable car elle exprime la fonction Ackermann sous la forme d'une liste infinie, ce qui, à mon avis, est plutôt génial. Le résultat est une liste infinie (de listes infinies) telle que, à la position [m, n] elle contienne la valeur A (m, n) .

La liste infinie elle-même:

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

En fonction (pour se conformer à la spécification):

i=iterate;m%n=i(tail.(`i`1).(!!))[1..]!!m!!n

La formulation a été dérivée en observant que le cas général / commun de la fonction Ackermann consiste à utiliser la valeur à gauche comme index dans la ligne ci-dessus. Le cas de base de cette récursivité (c'est-à-dire la colonne la plus à gauche d'une ligne, c'est-à-dire A (m, 0) ) consiste à utiliser la deuxième valeur la plus à gauche de la ligne ci-dessus. Le cas de base pour cela récurrence est le cas A (0, n) = n + 1 , c'est-à-dire que la première ligne est [1..].

Ainsi, nous obtenons

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

Ensuite, nous ajoutons simplement un autre niveau d'itération basé sur ce modèle et faisons des jongles inutiles .

Luciole
la source
Vous pourriez alias iterateà un nom de lettre -à- direi=iterate;ack=i ...
fier haskeller
@ Proudhaskeller oh ouais, je n'ai pas pensé à ça. Merci! Emprunter votre nom d'opérateur également.
FireFly
2

Tiny Lisp , 70 ans (hors compétition)

Ceci est hors compétition, car le langage est plus récent que la question et ne réussit pas non plus à exécuter le (A 3 10)code requis dans la question, en raison d'un débordement de pile.

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

Ceci définit une fonction Aqui calcule la fonction Ackermann. Formaté:

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

Nous utilisons toutes les macros internes ( d(définir) et q(quote) et i(if)) et une fonction intégrée (s - soustraire) ici.

i exécute sa vraie partie quand la condition est un nombre> 0 (sinon la fausse partie), nous n'avons donc pas à faire de comparaison explicite ici.

sest la seule opération arithmétique disponible, nous l’utilisons pour le n-1/ m-1, ainsi que(s n (s 0 1)) pour n+1.

Lisp minuscule utilise l'optimisation de la récursion de la queue, mais cela n'aide que pour l'extérieur A appel dans le résultat, pas pour l' A(m, n-1)appel utilisé pour les paramètres.

Avec ma toute petite implémentation de lisp à Ceylan sur la machine virtuelle, cela fonctionne (A 3 5) = 253, mais il semble s’effondrer lorsque je tente de calculer(A 2 125) directement (ce qui devrait donner le même résultat). En calculant cela après (A 3 4) = 125, la JVM semble avoir suffisamment optimisé les fonctions pour intégrer des appels de fonction intermédiaires dans mon interpréteur, ce qui permet une plus grande profondeur de récursivité. Étrange.

L' implémentation de référence se lève pour (A 3 5) = 253et aussi (A 2 163) = 329, mais ne réussit pas (A 2 164), et donc encore moins (A 3 6) = (A 2 253).

Paŭlo Ebermann
la source
cela pourrait être compétitif, sauf pour les espaces et les parenthèses;)
cat
2

Go, 260 243 240 122 octets

Je n'ai pas vu que la question permettait anon funcs.

loin d'être compétitif, mais j'apprends cette langue et je voulais le tester.

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}

utilisez-le comme go run ack.goet ensuite fournissez deux nombres, metn . si m> 4 ou n> 30, le temps d'exécution peut être supérieur à une demi-minute.

pour m=3 n=11:

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

edit : total enregistré 17 octets en passant aux importations de switchsur if/elseet de points

chat
la source
1
Vous pouvez faire encore mieux! switch 0 {case m:r=n+1 case n:r=a(m-1,1) default:r=a(m-1,a(m,n-1))}La switchdéclaration de Go est si merveilleusement flexible!
EMBLEM
@EMBLEM Merci, ça fait si longtemps que je n'ai pas écrit une ligne de Go, mais je suis heureux de voir qu'il y a d'autres golfeurs de golf sur: D
cat
1

Haskell: 81 69 octets

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 prend environ 45 secondes.

SophR
la source
1
c'est du code golf, vous devriez donc essayer d'avoir le code le plus court possible. par exemple, supprimez les espaces inutiles et le type explicite
fier haskeller
vous manquez également les parens sur la quatrième ligne
fier haskeller
1

Pyth (non concurrent), 15 octets

M?GgtG?HgGtH1hH

Essayez-le en ligne! (exemple d'utilisation de la fonction g3Tajoutée, ce qui signifie g(3,10))

Fuite, nonne
la source
1

UGL (non concurrent) , 31 à 30 octets

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

Entrée séparée par des nouvelles lignes.

Essayez-le en ligne!

(Il a été implémenté comme exemple standard dans l'interpréteur.)

Fuite, nonne
la source
1

R - 54 52

J'ai utilisé cela comme une excuse pour essayer de comprendre R, alors c'est probablement très mal fait :)

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

Exemple d'exécution

> a(3,8)
[1] 2045

Je reçois un débordement de pile pour quoi que ce soit au-delà

T-SQL- 222

Je pensais que j'essaierais de faire en sorte que T-SQL le fasse également. Utilisé une méthode différente parce que la récursivité n'est pas très agréable en SQL. Tout ce qui dépasse 4,2 le bombe.

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
la source
pour votre submisson R, on dirait que vous n'en avez pas besoin {}bien que la limite de débordement de pile ne soit d'aucun secours, car R n'a pas de coût total de possession ...
Giuseppe
@ Giuseppe merci ... dans ma défense, j'étais nouveau à ce moment-là :)
MickyT
1

brainfuck , 90 octets

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

Essayez-le en ligne!

Suppose une implémentation avec une taille de cellule de taille arbitraire, avec IO en tant que nombres. -6 octets si cela ne vous dérange pas d'utiliser des cellules négatives.

Termine en environ 30 secondes pour 3,8 dans l’interprète lié, à condition de cocher les paramètres appropriés. Tapez les nombres entrés précédés de \s, par exemple 3,9est \3\9.

Jo King
la source
1

Tcl , 67 octets

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

Essayez-le en ligne!


Tcl , 77 octets

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

Essayez-le en ligne!

Dans le compilateur en ligne, son exécution échoue, mais dans un interpréteur Tcl local, il fonctionne bien. Je me suis profilé de chaque appel racine à Afonction, pour voir combien de temps le calcul a pris pour chaque paire de {m,n}sujets à tester:

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

Cela échoue pour la dernière paire {m,n}={3,10}, car cela prend un peu plus d'une minute.

Pour des valeurs plus élevées de m, il sera nécessaire d'augmenter la recursionlimitvaleur.


Je ne peux pas l'obtenir plus court à 65 octets, mais cela ne répondra pas à l'exigence de la question "Votre fonction doit pouvoir trouver la valeur de A (m, n) pour m ≤ 3 et n ≤ 10 en moins d'une minute.". Sans {}cela, le délai d'attente sur TIO sera dépassé et la démonstration des deux dernières entrées ne sera pas effectuée.

Tcl , 65 octets

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

Essayez-le en ligne!

sergiol
la source
0

J: 50

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

Revient en une fraction de seconde pour 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│
└───┴──────────────────────────────────────────┘

PS: le "0 sert à faire un travail sur chaque élément, au lieu de dévorer les tableaux gauche et droit, et de générer des erreurs de longueur. Mais ce n'est pas nécessaire pour, par exemple, 9 = 2 A 3.

jpjacobs
la source
codegolf.stackexchange.com/a/40174/48934 Vous avez été battu!
Leaky Nun
0

APL, 31

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

Assez simple. Utilise le caractère une fois pour sauvegarder un octet en inversant les arguments. Prend m comme argument de gauche et n comme argument de droite.

TryAPL.org

Shujal
la source
0

Ruby, 65 ans

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

Explication

Ceci est une traduction assez simple de l'algorithme donné dans la description du problème.

  • L'entrée est considérée comme l'argument d'un lambda. DeuxInteger s sont attendus.
  • Pour plus de rapidité et pour éviter les erreurs de débordement de pile, les réponses sont mémorisées dans le Hash h. le||= opérateur est utilisé pour calculer une valeur qui n'avait pas été calculée auparavant.

a[3,10] est calculé en ~ 0.1 secondes sur ma machine.

Voici une version non-golfée

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
la source
a[3,10]jette un SystemStackError sur ma machine ...
TuxCrafting
Nippicks de golf: Vous pourriez changer m<1?(n+1):(n<1?a[m-1,1]:a[m-1,a[m,n-1]])pourm<1?n+1:a[m-1,n<1?1:a[m,n-1]]
Simply Beautiful Art
0

Mouse-2002 , 99 83 octets

$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+;;]]]@
chat
la source
0

Java, 274 octets

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)));}}

Il calcule A(3,10)en quelques secondes, et compte tenu de l'espace mémoire et de la pile infinis, il peut calculer n'importe quelle combinaison de bet Baussi longtemps que le résultat est inférieur à 2 2147483647 -1.

Dorukayhan veut récupérer Monica
la source
Je sais que ça fait longtemps, mais vous pouvez 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)));}
jouer au
0

Ceylan, 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)));

Ceci est une implémentation simple. Formaté:

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

L'alias enregistre un seul octet, sans lui (avec l'écriture Integerau lieu de I), nous aurions 86 octets. Deux autres octets peuvent être sauvegardés en les remplaçant == 0par < 1deux fois.

Avec les paramètres par défaut de ceylon run, cela fonctionnera jusqu’à A(3,12) = 32765(et A(4,0) = 13), mais A(3,13)(et donc aussi A(4,1)) jettera une erreur de débordement de pile. ( A(3,12)prend environ 5 secondes, A(3,11)environ 3 sur mon ordinateur.)

Utiliser ceylon run-js(c.-à-d. Exécuter le résultat de la compilation en JavaScript sur node.js) est beaucoup plus lent (nécessite 1 min 19 s A(3,10)), et fonctionne déjà A(3, 11)avec une »Taille maximale de la pile d'appels dépassée« (avec les paramètres par défaut) après une exécution de 1 min 30 s.


Ceylan sans récursivité, 228

En bonus, voici une version non-récursive (plus longue, bien sûr, mais à l'abri des débordements de pile - peut provoquer une erreur d'insuffisance de mémoire à un moment donné).

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;}}}}

Formaté:

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;
            }
        }
    }
}

Il est assez lent sur mon ordinateur que la version récursive: A(3,11)prend 9,5 secondes, A(3,12)prend 34 secondes, A(3,13)prend 2:08 minutes, A(3,14)prend 8:25 minutes. (J'avais initialement une version utilisant des iterables paresseux au lieu des tuples que j'ai maintenant, qui était même beaucoup plus lente, avec la même taille).

Un peu plus rapide (21 secondes pour A(3,12)) (mais aussi un octet plus) est une version en utilisant au s.pushlieu de s.addAll, mais qui devait être appelé à plusieurs reprises pour ajouter plusieurs numéros, car il faut un seul entier chacun. L'utilisation d'une LinkedList au lieu d'une ArrayList est beaucoup plus lente.

Paŭlo Ebermann
la source