Écrivez un programme de brainfuck de pas plus de 256 caractères qui prend autant d'étapes que possible, mais ne boucle pas indéfiniment. Le programme ne peut prendre aucune entrée.
Plus précisement:
- Supposons un nombre infini de cellules à droite.
- Un
<quand à la cellule la plus à gauche ne fait rien. - Un
-lorsque la valeur de la cellule est nulle définit la cellule sur255. - Les instructions
+-<>.comptent toutes comme une étape lorsqu'elles sont exécutées. - Lorsqu'un
[ou]est rencontré, cela compte comme une étape. Toutefois, si la condition est vraie et saute flux de contrôle, le correspondant]ou[ne pas compter à nouveau comme une étape. - La solution qui prend le plus de pas gagne.
- S'il existe une sorte de modèle dans votre solution, donner une fonction pour le nombre de pas qu'un programme similaire de longueur
nprendrait est apprécié mais pas obligatoire. - Pour compter les instructions, vous pouvez utiliser cet interpréteur modifié :
Exemple:
++[-]
Les instructions rencontrées le sont ++[-]-]et le programme s'est exécuté en 7 étapes.
code-challenge
brainfuck
busy-beaver
Anton Golov
la source
la source
floatou lesdoubleprimitives utilisées pour l'informatique quotidienne générale. (À ce stade, l'ordinateur manipule principalement des chaînes qui représentent l'équation)Réponses:
Voici un programme de 41 caractères qui s'arrête finalement, laissant plus de 10 ↑ (10 ↑ 28) cellules contiguës définies égales à 1 (le nombre d'instructions exécutées est donc bien supérieur à cela):
Si je ne me trompe pas, c'est une traduction correcte du programme suivant dans le langage de variante BF qui utilise un seul bit pour chaque cellule de mémoire (c'est-à-dire, le contenu de la cellule 0..1 au lieu de 0..255, donc '+' agit simplement pour inverser la valeur du bit):
La valeur exacte (le nombre de bits adjacents 1) produite par ce dernier programme est
Le programme ci-dessus initialise et calcule une fonction qui grandit comme 2 ↑↑ x (en notation de flèche vers le haut de Knuth ). Une conversion similaire d'un programme variant-BF qui initialise et calcule une fonction qui grandit comme 2 ↑ 23 x fournit le programme de 256 caractères suivant:
qui s'arrête finalement, laissant plus de 2 ↑ 23 6 cellules adjacentes définies égales à 1 (donc le nombre de pas est énormément plus que cela).
NB-1 : 2 ↑ 23 6 est un nombre "inconcevablement grand"; par exemple, même 2 ↑ 4 6 = 2 ↑↑↑↑ 6 dépasse déjà le premier terme (3 ↑↑↑↑ 3) dans la séquence utilisée pour calculer le nombre de Graham .
NB-2 : Je pense qu'il est probable que 256 caractères suffisent pour qu'un programme BF initialise et calcule une fonction avec une sortie beaucoup plus grande que le nombre de Graham - si je trouve du temps, j'essaierai peut-être d'en écrire un.
NB-3 : Si quelqu'un s'intéresse à l'origine des programmes ci-dessus, voici quelques ressources de programmation pour "Brainf * ck F" , avec divers programmes écrits en Python. ("Brainf * ck F", ou simplement "F", est ce que j'ai appelé une variante Turing-complète de l' esolangage Smallf * ck .) Je viens de télécharger ces fichiers, qui sont hors ligne depuis plusieurs années, et pour l'instant le la page Web liée n'est qu'un "classeur" - voir le fichier Busy_Beavers.txt pour une discussion détaillée concernant les programmes ci-dessus.
la source
Voici un joli 39 caractères:
Il fait essentiellement un «traîneau» de 3 espaces qu'il se déplace vers la droite et diminue d'une unité. Terminé en 31 919 535 558 instructions, la boucle la plus interne s'exécutant 256 ^ 3 fois. J'ai encore beaucoup de place pour étendre cela assez loin à un taux de 14 caractères à un autre ordre de grandeur pour la durée d'exécution.
Fonctionne sur n'importe quel interpréteur avec une mémoire illimitée ou avec une mémoire d'habillage.
Je laisse un exercice au lecteur pour déterminer quand la version améliorée par 2 boucles se terminera:
Il a maintenant fonctionné du jour au lendemain et se compose de plus de 3 000 000 000 de pas. N'a pas encore traversé une seule itération de la boucle externe. A à peine franchi 15% de la seconde boucle.
la source
Ce programme fonctionne dans un nombre infini de cellules. Deux valeurs sont initialisées au début avec des valeurs ascii 255. La première valeur à la première rotation de la boucle principale est divisée en 255 cellules et elles sont initialisées avec 255 chacune, à la deuxième rotation de la boucle principale, chaque valeur en 255 cellules se divise à nouveau jusqu'à 255 * 255 cellules, de la même manière pour 255 rotation de la boucle principale, le total des cellules initialisées sera 255 ^ 255. La deuxième valeur détermine combien de fois la boucle principale doit être répétée.
la source
Ce programme est presque le même que mon programme précédent, la différence est que la valeur déterminant la boucle externe reste fixe dans une cellule particulière, de sorte que le nombre de cellules initialisées et le nombre total d'étapes à la fin du programme peuvent être augmentés
cellules initialisées à la fin du programme 255 ^ 255
cellules initialisées à la fin du programme 255 ^ 255 ^ 3
Je l'ai encore modifié pour exécuter encore plus de nombre d'étapes.
il initialise 255 ^ 255 cellules lors de la première rotation de 255 ^ (255 ^ 255 * 255) cellules lors de la deuxième rotation de la boucle principale 255 ^ {255 ^ (255 ^ 255 * 255) * 255} cellules lors de la troisième rotation de la boucle principale dans cette boucle se répète 255 fois
la source