Génération de NOP Brainf ***

26

Parfois, lors de l'écriture de code brainfuck, vous ressentez le besoin de le rendre plus long que nécessaire pour encourager le débogage. Vous pourriez le faire en y insérant juste un ><, mais quel plaisir est-ce? Vous aurez besoin de quelque chose de plus long et moins de NOPey pour confondre quiconque lit votre code.

Introduction rapide à Brainfuck

Brainfuck est un langage de programmation ésotérique créé en 1993 par Urban Müller, et remarquable pour son minimalisme extrême. (Wikipédia)

Brainfuck est un langage basé sur huit commandes: +-><,.[]. Le code est exécuté sur quelque chose comme une machine de Turing: une bande infinie sur laquelle les valeurs peuvent être modifiées. Dans ce défi, nous nous concentrerons sur les quatre premiers:

+    increment the value at the pointer
-    decrement the value at the pointer
>    move the pointer right
<    move the pointer left

NOP Brainfuck

Un brainfuck NOP est une séquence de personnages brainfuck qui, lorsqu'ils sont exécutés à partir de n'importe quel état, ne conduisent à aucun changement d'état. Ils se composent des quatre caractères mentionnés ci-dessus.

Le défi

Le défi consiste à écrire un programme ou une fonction qui, une fois exécuté, génère un NOP de brainfuck aléatoire de la longueur donnée.

Contribution

Vous recevrez en entrée un entier pair non négatif n. (Les NOP sont impossibles à comprendre n.)

Sortie

Vous produirez un NOP de brainfuck aléatoire de la longueur n.

Règles

  • La définition de NOP: lorsque la sortie du programme est insérée à tout moment dans un programme brainfuck, le comportement dudit programme ne doit en aucun cas changer. En d'autres termes, il ne doit pas changer l'état de l'interprète.
    • Notez que, par exemple, +>-<est incorrect, car il modifie les valeurs des deux cellules sans les modifier en arrière. Veuillez tester votre solution pour ces derniers avant de poster.
    • Notez également qu'il +>-<->+<s'agit d'un NOP qui ne peut être réduit à rien simplement en le supprimant >< <> +- -+. Ainsi, vous ne pouvez pas utiliser un algorithme qui les insère simplement les uns dans les autres.
  • Chaque NOP valide de la longueur ndoit avoir une chance non nulle d'apparaître dans la sortie. La distribution ne doit cependant pas être uniforme.
  • L'interprète brainfuck en question a une bande doublement infinie de cellules de précision arbitraire. Autrement dit, vous pouvez aller à l'infini dans les deux directions et incrémenter / décrémenter chaque cellule indéfiniment.
  • Le programme doit se terminer en 1 minute pour n= 100 sur ma machine, donc pas de génération de tous les NOP possibles et d'en choisir un.
  • Si une entrée non valide (non entière, négative, impaire, etc.) est fournie, vous pouvez faire tout ce que vous souhaitez, y compris un crash.

Notation

Il s'agit de , donc la réponse la plus courte en octets l'emporte.

Exemples

Voici toutes les sorties valides pour n= 4:

++--    +-+-    +--+    --++    -+-+    -++-
>><<    ><><    ><<>    <<>>    <><>    <>><
><+-    ><-+    <>+-    <>-+
>+-<    >-+<    <+->    <-+>
+><-    -><+    +<>-    -<>+
+-><    -+><    +-<>    -+<>

Voici quelques sorties possibles pour n= 20:

+>>->+<->-<<<->>++<<
>+>-<+<->+-<>->+<-<+
+--+-++--++-+--+-++-
>>>>>>>>>+-<<<<<<<<<
PurkkaKoodari
la source
18
voici un NOP de brainfuck qui n'utilise pas +-<>comme vous l'avez demandé:a
undergroundmonorail
1
Je ne pense pas qu'il existe des NOP non simples, vous pouvez donc probablement supprimer cette qualification. .a un effet secondaire, ,écrase une valeur qui ne peut pas être récupérée sans l'utilisation de []. Mais []finira par définir une valeur à zéro. Cela écrase également une valeur (nous en aurions donc besoin d'une autre []pour la récupérer), sauf si nous pouvons être sûrs que la cellule affectée était zéro au départ. Cependant, nous devions rechercher une telle cellule avec quelque chose comme [>], et il est impossible de retourner de manière fiable à la position d'où nous venons.
Martin Ender
4
@Eumel "L'interprète brainfuck en question a une bande doublement infinie de cellules de précision arbitraire."
Martin Ender
2
Veuillez noter que "Brainfuck" n'est plus autorisé dans les titres de question au niveau du système. Il semble que vous ayez pu contourner la restriction en utilisant des caractères non ASCII. À l'avenir, veuillez respecter cette restriction.
Alex A.
2
@undergroundmonorail Eh bien, c'est Turing complet ... donc techniquement on pourrait y écrire un PRNG comme n'importe quelle autre langue. (Bien que l'ensemencement soit difficile.)
PurkkaKoodari

Réponses:

13

CJam, 62 59 octets

Merci à nhahtdh pour avoir économisé 3 octets.

Parce qu'il n'y a aucune exigence pour une distribution particulière tant que chaque no-op apparaît avec une probabilité finie, nous pouvons simplifier cela beaucoup en générant simplement une chaîne contenant un nombre équilibré de -+et <>, respectivement, en testant s'il s'agit d'un NOP et en le triant s'il le fait n'est pas.

Bien sûr, pour des entrées plus longues, cela se traduira presque toujours par une sortie triée, mais vous pouvez tester le code avec une entrée comme 8pour voir qu'il peut en principe produire n'importe quel NOP de la longueur donnée.

ri_0a*\2/{;"-+<>":L2/mR}%smr:SL["Xa.Xm"3/2e*L]z:sers~0-S$S?

Essayez-le en ligne.

Martin Ender
la source
1
Oui ... la limite arbitraire aurait dû être n = 1000 en moins de 10 secondes. Les ordinateurs sont juste un moyen de jeûner aujourd'hui ^^ Parce que la réponse algorithmique le résout en moins d'une seconde, même pour n = 1000
Falco
Pour un n encore plus grand, je pense qu'il est possible de simplement trier la sortie si la chaîne équilibrée n'est pas NOP. La distribution est terriblement biaisée, mais c'est permis par la question.
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ c'est une bonne idée.
Martin Ender
@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Merci, cela permet également d'économiser ici trois octets.
Martin Ender
16

CJam, 118 116 octets

Cela est devenu un peu incontrôlable ... en particulier la seconde moitié semble être très jouable.

ri2/_)mr:R-"<>"R*mr_'=fm0\{1$+}%+__&e`]:\{mr1aa..+}*\@](\z:~\{~\("+-"*mr1$3$e=[{_,)mr_2$<@@>}*+]@@f{`1$`={(}@?\}W<}/

Testez-le ici.

Cela gère à N = 100peu près instantanément. Je n'ai pas le temps d'écrire la décomposition complète du code maintenant, voici donc l'algorithme:

  • Générez une chaîne aléatoire équilibrée de <et >avec une longueur aléatoire (paire) entre 0et Ninclus.
  • Riffle les positions de tête de bande dans cette matrice. Par exemple, "<>><"devient [0 '< -1 '> 0 '> 1 '< 0].
  • Obtenez une liste de toutes les positions atteintes au cours du processus.
  • Pour chacune de ces positions, initialisez une chaîne vide. Déterminez également le nombre de paires de caractères restant pour atteindre une chaîne de longueur N.
  • Pour chaque paire restante, ajoutez +-à la chaîne d'une position aléatoire.
  • Mélangez toutes ces chaînes.
  • Pour chaque position, déterminez la fréquence à laquelle cette position se produit dans le tableau rayé et divisez la chaîne correspondante en autant de morceaux (de longueur aléatoire).
  • Dans le tableau rayé, remplacez les occurrences de la position par ses morceaux aléatoires.

Terminé. Ceci est basé sur l'observation que:

  • Tout NOP doit avoir une quantité égale de <et >pour remettre la tête de bande à sa position d'origine.
  • Le code sera un NOP tant que chaque cellule de bande est incrémentée aussi souvent que décrémentée.

En distribuant des quantités aléatoires mais équilibrées de +s et -s entre tous les endroits où la tête de bande se trouve sur une cellule donnée, nous nous assurons de trouver tous les NOP possibles.

Martin Ender
la source
4

Mathematica, 350 octets

Quiet@(For[a="+",If[{##4}=={},#3!=0||Union@#!={0},Switch[#4,"+",#0[ReplacePart[#,#2->#[[#2]]+1],#2,#3,##5],"-",#0[ReplacePart[#,#2->#[[#2]]-1],#2,#3,##5],">",#0[#~Append~0,#2+1,#3+1,##5],"<",If[#2<2,#0[#~Prepend~0,1,#3-1,##5],#0[#,#2-1,#3-1,##5]]]]&@@{{0},1,0}~Join~Characters@a,a=""<>RandomSample@Flatten@RandomChoice[{{"+","-"},{">","<"}},#/2]];a)&

Bien trop long? Oui. Est-ce que je m'en soucie même? Pas avant que quelqu'un d'autre ne poste une réponse valide.

LegionMammal978
la source
4
Pourriez-vous ajouter une explication, afin que les gens puissent se convaincre que c'est valable? :)
Martin Ender
Comment exactement fait ce travail? Si j'appelle la fonction avec un numéro, elle ne fait que revenir +.
Martin Ender
@ MartinBüttner Fixed ... Actuellement, il ne génère que des programmes aléatoires avec un nombre égal de +- -et <- >paires jusqu'à ce que l'un soit un NOP. La moitié est prise par un simple interprète BF.
LegionMammal978
cela génère-t-il réellement un no-op valide de longueur 100 en moins d'une minute?
Martin Ender
@ MartinBüttner Oui. En moyenne, je dirais que cela prend environ 5 secondes. Au début, j'ai essayé des programmes complètement aléatoires, mais cela ne s'est jamais terminé pour la longueur 100.
LegionMammal978
2

Python 3 , 177 octets

from random import*
n=int(input())
r=[0]*n*3
p=0
a=[43,45]
s=choices(a+[60,62],k=n)
for c in s:p+=~c%2*(c-61);r[p]+=c%2*(44-c)
if any(r+[p]):s=a*(n//2)
print(*map(chr,s),sep='')

Essayez-le en ligne!

J'ai utilisé le code de la réponse de Bubbler pour la simulation BF.

Tyilo
la source
2

Python 3 , 163 octets

from random import*
n=int(input())
p=0;d=[0]*n;a=choices(b'+-<>',k=n)
for c in a:d[p]+=c%2*(44-c);p+=~c%2*(c-61)
if p|any(d):a=n//2*b'+-'
print(*map(chr,a),sep='')

Essayez-le en ligne!

Programme complet qui imprime les résultats sur STDOUT. La ligne qui exécute le code BF peut être jouable au golf.

Adopté l'approche de Tyilo; si le code BF généré n'est pas un NOP, jetez-le complètement et revenez à '+-'répété.

Bubbler
la source
Délai d'attente
@ l4m2 Je n'ai pas remarqué cette exigence. Fixé.
Bubbler
1

JavaScript (Node.js) , 160 octets

n=>[...s=c(i=n,t=c(n/2,r=[],f=_=>'+-'),f=_=>'+-<>'[Math.random()*4|0])].map(_=>_<'<'?(r[i]=_+1-~r[i]-1):(i+=_<'>'||-1))|r.some(eval)|i-n?t:s;c=n=>n?c(n-1)+f():r

Essayez-le en ligne!

l4m2
la source
1

Wolfram Language (Mathematica) , 224 octets

(s=RandomSample[##&@@@Table["<"">",(r=RandomInteger)[#/2]]];While[(g=Length@s)<#,s=Insert[s=Insert[s,"+",i=r@g+1],"-",RandomChoice@@Select[GatherBy[0~Range~++g,Count[#,"<"]-Count[#,">"]&@Take[s,#]&],!FreeQ[#,i]&]+1]];""<>s)&

Essayez-le en ligne!

Voici la version non-golfée (ou plutôt pré-golfée):

Function[{n},
 k = RandomInteger[n/2];
 s = RandomSample[## & @@@ Table["<" ">", k]];
 While[Length[s] < n,
   s = Insert[s, "+", i = RandomInteger[Length[s]] + 1];
   p = GatherBy[Range[0, Length[s]], 
     Count[#, "<"] - Count[#, ">"]& @ Take[s, #]&];
   j = RandomChoice @@ Select[p, ! FreeQ[#, i] &]];
   s = Insert[s, "-", j + 1];
   ];
 ""<>s]

Nous choisissons d'abord un nombre aléatoire de <«et >» à utiliser, et générons une liste aléatoire avec un nombre égal de chacun.

Pour remplir le reste des caractères, nous choisissons une position dans laquelle ajouter un +, puis trouvons une position où le pointeur pointe vers le même emplacement et y ajoutons un -.

Répétez l'opération jusqu'à ce que la liste ait une longueur net chaînez le résultat.

Misha Lavrov
la source