Generando Brainf *** NOPs

26

A veces, al escribir código brainfuck, siente la necesidad de hacerlo más largo de lo necesario para alentar la depuración. Podrías hacerlo simplemente colocando un ><allí, pero ¿qué tan divertido es eso? Necesitará algo más largo y menos NOPey para confundir a cualquiera que lea su código.

Introducción rápida a Brainfuck

Brainfuck es un lenguaje de programación esotérico creado en 1993 por Urban Müller, y destaca por su minimalismo extremo. (Wikipedia)

Brainfuck es un lenguaje basado en ocho comandos: +-><,.[]. El código se ejecuta en algo parecido a una máquina de Turing: una cinta infinita en la que se pueden cambiar los valores. En este desafío, nos centraremos en los primeros cuatro:

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

Brainfuck NOPs

Un brainfuck NOP es una secuencia de personajes de brainfuck que, cuando se ejecuta desde cualquier estado, no conduce a ningún cambio en el estado. Se componen de los cuatro caracteres mencionados anteriormente.

El reto

El desafío es escribir un programa o función que, cuando se ejecuta, genera un NOP aleatorio de la duración dada.

Entrada

Recibirá como entrada un entero par no negativo n. (Los NOP son imposibles para imparn ).

Salida

Producirás un NOP aleatorio de la longitud n .

Reglas

  • La definición de NOP: cuando la salida del programa se inserta en cualquier punto de un programa mental, el comportamiento de dicho programa no debe cambiar de ninguna manera. En otras palabras, no debe cambiar el estado del intérprete.
    • Tenga en cuenta que, por ejemplo +>-< es incorrecto, ya que cambia los valores de las dos celdas sin volver a cambiarlas. Pruebe su solución para estos antes de publicar.
    • También tenga en cuenta que +>-<->+<es un NOP que no se puede reducir a nada simplemente quitándolo >< <> +- -+. Por lo tanto, no puede usar un algoritmo que simplemente los inserte uno dentro del otro.
  • Cada NOP válido de la longitud ndebe tener una probabilidad distinta de cero de aparecer en la salida. Sin embargo, la distribución no tiene que ser uniforme.
  • El intérprete en cuestión tiene una cinta doblemente infinita de celdas de precisión arbitraria. Es decir, puede ir infinitamente a ambas direcciones e incrementar / disminuir cada celda indefinidamente.
  • El programa debe finalizar en 1 minuto por n= 100 en mi máquina, por lo que no generar todos los NOP posibles y elegir uno.
  • Si se le proporciona una entrada no válida (no entera, negativa, impar, etc.), puede hacer lo que quiera, incluido el bloqueo.

Tanteo

Este es el , por lo que gana la respuesta más corta en bytes.

Ejemplos

Aquí están todas las salidas válidas para n= 4:

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

Aquí hay algunas salidas posibles para n= 20:

+>>->+<->-<<<->>++<<
>+>-<+<->+-<>->+<-<+
+--+-++--++-+--+-++-
>>>>>>>>>+-<<<<<<<<<
PurkkaKoodari
fuente
18
aquí hay un NOP brainfuck que no utilice +-<>como usted pidió:a
undergroundmonorail
1
No creo que existan NOP no simples, por lo que probablemente pueda eliminar esa calificación. .tiene un efecto secundario, ,sobrescribe un valor que no se puede recuperar sin el uso de []. Pero []terminará estableciendo un valor a cero. Esto también sobrescribe un valor (por lo que necesitaríamos otro []para recuperarlo) a menos que podamos estar seguros de que la celda afectada era cero para empezar. Sin embargo, tendríamos que buscar una celda de ese tipo con algo así [>], y es imposible volver de manera confiable a la posición de donde venimos.
Martin Ender
44
@Eumel "El intérprete en cuestión tiene una cinta doblemente infinita de celdas de precisión arbitraria".
Martin Ender
2
Tenga en cuenta que "Brainfuck" ya no está permitido en los títulos de preguntas en el nivel del sistema. Parece que pudo eludir la restricción mediante el uso de caracteres no ASCII. En el futuro, cumpla con esta restricción.
Alex A.
2
@undergroundmonorail Bueno, es Turing completo ... por lo que técnicamente uno podría escribir un PRNG como cualquier otro idioma. (Aunque sembrar puede ser difícil).
PurkkaKoodari

Respuestas:

13

CJam, 62 59 bytes

Gracias a nhahtdh por guardar 3 bytes.

Debido a que no existe un requisito para ninguna distribución en particular, siempre que cada no-op aparezca con probabilidad finita, podemos simplificar esto mucho simplemente generando una cadena que contenga un número equilibrado -+y <>, respectivamente, probando si es un NOP y clasificándolo si es no lo es

Por supuesto, para entradas más largas, esto casi siempre dará como resultado una salida ordenada, pero puede probar el código con alguna entrada 8para ver que, en principio, puede producir cualquier NOP de la longitud dada.

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

Pruébalo en línea.

Martin Ender
fuente
1
Sí ... el límite arbitrario debería haber sido n = 1000 en 10 segundos. Las computadoras son simplemente una forma de ayunar hoy ^^ Porque la respuesta algorítmica lo resuelve en menos de un segundo incluso para n = 1000
Falco
Para una n aún mayor, creo que es posible ordenar la salida si la cadena balanceada no es NOP. La distribución es terriblemente sesgada, pero la pregunta lo permite.
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ esa es una buena idea.
Martin Ender
@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Gracias, eso también ahorra tres bytes aquí también.
Martin Ender
16

Cjam, 118 116 bytes

Esto se salió un poco de control ... especialmente la segunda mitad parece que debería ser muy golfable.

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

Pruébalo aquí.

Esto se maneja N = 100prácticamente al instante. No tengo tiempo para escribir el desglose completo del código ahora, así que aquí está el algoritmo:

  • Genere una cadena equilibrada aleatoria de <y >con una longitud aleatoria (par) entre 0e Ninclusive.
  • Riffle las posiciones del cabezal de la cinta en esta matriz. Por ejemplo, se "<>><"convierte [0 '< -1 '> 0 '> 1 '< 0].
  • Obtenga una lista de todas las posiciones alcanzadas en el proceso.
  • Para cada posición de este tipo, inicialice una cadena vacía. También determine cuántos pares de caracteres quedan para alcanzar una cadena de longitud N.
  • Para cada par restante agregue +-a la cadena de una posición aleatoria.
  • Baraja todas esas cuerdas.
  • Para cada posición, determine con qué frecuencia se produce esa posición en la matriz ondulada y divida la cadena correspondiente en esa cantidad de fragmentos (de longitud aleatoria).
  • En la matriz ondulada, reemplace las ocurrencias de la posición con sus fragmentos aleatorios.

Hecho. Esto se basa en la observación de que:

  • Cualquier NOP debe tener una cantidad igual de <y >para devolver el cabezal de la cinta a la posición original.
  • El código será un NOP siempre que cada celda de cinta se incremente con la frecuencia que se decremente.

Al distribuir cantidades aleatorias pero equilibradas de +sys -entre todos los lugares donde se encuentra el cabezal de la cinta en una celda determinada, nos aseguramos de encontrar todos los NOP posibles.

Martin Ender
fuente
4

Mathematica, 350 bytes

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

¿Demasiado tiempo? Sí. ¿Me importa? No hasta que alguien más publique una respuesta válida.

LegionMammal978
fuente
44
¿Te importaría agregar una explicación, para que las personas puedan convencerse de que esto es válido? :)
Martin Ender
¿Cómo funciona esto exactamente ? Si llamo a la función con un número, solo regresa +.
Martin Ender
@ MartinBüttner fijo ... En la actualidad, sólo se genera programas aleatorios con un número igual de +- -y <- >pares hasta que uno pasa a ser un NOP. La mitad es tomada por un simple intérprete BF.
LegionMammal978
¿eso realmente genera una no-operación válida de longitud 100 en menos de un minuto?
Martin Ender
@ MartinBüttner Sí. En promedio, diría que lleva unos 5 segundos. Al principio, probé programas completamente al azar, pero nunca terminaron por una longitud de 100.
LegionMammal978
2

Python 3 , 177 bytes

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='')

Pruébalo en línea!

Usé código de la respuesta de Bubbler para la simulación BF.

Tyilo
fuente
2

Python 3 , 163 bytes

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='')

Pruébalo en línea!

Programa completo que imprime resultados en STDOUT. La línea que ejecuta el código BF podría ser golfable.

Enfoque de Tyilo adoptado; Si el código BF generado no es un NOP, deséchelo por completo y vuelva a '+-'repetirlo.

Bubbler
fuente
Tiempo de espera para n = 100
l4m2
@ l4m2 No noté ese requisito. Fijo.
Bubbler
1

JavaScript (Node.js) , 160 bytes

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

Pruébalo en línea!

l4m2
fuente
1

Wolfram Language (Mathematica) , 224 bytes

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

Pruébalo en línea!

Aquí está la versión sin golf (o más bien, pre golf):

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]

Primero seleccionamos un número aleatorio de <'sy >' s para usar, y generamos una lista aleatoria con un número igual de cada uno.

Para completar el resto de los caracteres, elegimos una posición en la que agregar un +, luego encontramos una posición donde el puntero apunta a la misma ubicación y agregamos un -allí.

Repita hasta que la lista tenga longitud ny stringifique el resultado.

Misha Lavrov
fuente