Verifique el programa Brainfuck

17

Otro problema de análisis de Brainfuck, pero esta vez ... diferente.

Estás trabajando en Infinite Monkeys Incorporated, la compañía que desarrolla los programas Brainfuck, para resolver varios problemas interesantes (por accidente, nada menos, después de todo, la compañía hace programas aleatorios). Sin embargo, parece que las máquinas rápidas de Turing que solo ejecutan Brainfuck tienen un pequeño y costoso problema con los errores de sintaxis: crea uno y la computadora explota. Probablemente sea un defecto de diseño, pero nadie se había molestado en descubrir por qué sucede.

Como las máquinas de Turing (especialmente las rápidas) son caras (después de todo, tienen RAM infinita que cuesta), sería mejor asegurarse de que el programa no tenga errores de sintaxis antes de ejecutar el código. Su empresa ejecutará mucho código, por lo que la verificación manual no funcionará. Escriba un programa que lea el STDIN para el código Brainfuck y salga con el estado de salida establecido en cualquier cosa que no sea 0 (error) si el programa tiene algún error de sintaxis (por ejemplo, ]es un error de sintaxis, porque no hay coincidencia [). Salga con el estado de salida establecido en 0 si el programa está completamente bien.

Asegúrese de que su programa advierta correctamente los errores relacionados []. No querrías que explotara otra computadora, ¿verdad? Ah, y asegúrese de que sea lo más breve posible: su jefe paga los programas cortos (porque cree que son rápidos o algo así). Ah, y no tiene que codificar en Brainfuck (de hecho, no puede, porque Brainfuck no admite códigos de salida): su código se ejecutará en una computadora normal.

Entonces, como puede ver, su trabajo es verificar si el programa Brainfuck es "válido" (tiene []símbolos emparejados ). Tenga en cuenta que los programas Brainfuck pueden tener otros caracteres que []no sean , así que no rechace el programa solo porque tiene otros comandos. El código más pequeño gana, pero de todos modos probablemente te interesarían más los votos a favor.

Konrad Borowski
fuente
1
¿Qué pasa con los idiomas que no permiten configurar un código de salida de proceso?
Kendall Frey
1
@KendallFrey: Simple, usa algo más. O en GolfScript, incrustar código Ruby. Quizás esto bloquea algunos lenguajes de programación esotéricos, pero bueno ...
Konrad Borowski
1
¿Está bien establecer el código de error en algo diferente a 1 (siempre que no sea 0, por supuesto) en caso de falla?
marinus
@marinus: No sé por qué querrías eso, pero creo que está bien.
Konrad Borowski el
@ GlitchMr: porque entonces puedo usar en GCD(a,b)lugar de 0 != a || b.
marinus

Respuestas:

6

GolfScript, 18 caracteres

.{[]`?)},~](`91?./

Este código se ejecuta con éxito con el código de salida 0 (e imprime algo de basura en stdout) si los corchetes en la entrada están equilibrados. Si no lo están, falla con un código de salida distinto de cero e imprime un mensaje de error en stderr, por ejemplo:

(eval):2:in `/': divided by 0 (ZeroDivisionError)

o

(eval):1:in `initialize': undefined method `ginspect' for nil:NilClass (NoMethodError)

Como el desafío no dijo nada sobre la salida a stdout / stderr, creo que esto califica. En cualquier caso, siempre puedes redirigirlos a /dev/null.

Explicación:

El código {[]`?)},elimina todo menos los corchetes de la entrada, y ~evalúa el resultado como código GolfScript. La parte difícil es que los corchetes desequilibrados son perfectamente legales en GolfScript (y, de hecho, ¡mi código incluye uno!), Por lo que necesitamos otra forma de bloquear el código.

El truco que estoy usando es dejar una copia de la entrada en la parte inferior de la pila, recopilar toda la pila en una matriz (usando el desequilibrado ]) y desactivar el primer elemento. En este punto, pueden suceder tres cosas:

  • Si la entrada terminó en un no cerrado [, tratar de cambiar un elemento de una matriz vacía bloqueará el intérprete (que, en este caso, ¡es exactamente lo que queremos!)
  • Si los corchetes en la entrada estaban equilibrados, el elemento desplazado será la cadena de entrada original.
  • De lo contrario (si la entrada tenía un no abierto ]o un no cerrado [) será una matriz.

Mi entrada original de 14 caracteres comparó el valor desplazado con una cadena, que se bloquearía si fuera una matriz anidada. Desafortunadamente, resulta que comparar una matriz plana (o, en particular, vacía) con una cadena también es legal en GolfScript, por lo que tuve que cambiar de táctica.

Mi presentación actual, en cambio, utiliza un método de fuerza bruta para distinguir las matrices de las cadenas: las des-evalúa e intenta encontrar la primera aparición de [(código ASCII 91), que será cero si y solo si no se evade variable fue una matriz. Si es así, dividir el cero consigo mismo desencadena el bloqueo deseado.

PD. Otras dos soluciones de 18 caracteres son:

.{[]`?)},{.}%~](n<

y

.{[]`?)},~]([n]+n<

Por desgracia, todavía no he encontrado una forma más corta de resolver el "problema de matriz vacía".

Ilmari Karonen
fuente
¿está equilibrado ?: ][(es decir, ¿falla en su programa?)
Justin
@Quincunx: falla, como debería.
Ilmari Karonen
Sin embargo, resultó aceptar [[]; Lo arreglé ahora, al costo de 4 caracteres, y ahora pasa todas mis pruebas.
Ilmari Karonen
Si te entiendo correctamente, tenías una solución de 14 caracteres que no distingue entre una cadena y una matriz solo en el caso de que la matriz esté vacía. 1+convertirá una matriz vacía en una matriz no vacía, una matriz no vacía en una matriz no vacía y una cadena en una cadena.
Peter Taylor
@PeterTaylor: Sí, lo fue .{[]`?)},~](n<. Intenté su 1+, pero parece que la matriz necesita contener algo más que un número (presumiblemente para que el intérprete se bloquee cuando intenta comparar recursivamente un personaje con una matriz / cadena). El uso n+no funciona bien, ya que coacciona a la matriz en una cadena; [n]+ hace el trabajo, pero todavía me pone a los 18 caracteres.
Ilmari Karonen
17

Brainfuck 76 bytes

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

Esto desaparece si sus corchetes están desequilibrados, lo que hace que el intérprete / compilador bf falle en tiempo de ejecución y algunos de ellos tienen códigos de salida para reflejar eso.

requiere eof = 0, valores de ajuste y número finito de celdas

En Ubuntu puedes usar el intérprete bf( sudo apt-get install bf)

% echo '[[[]' | bf -n bf_matching.bf
Error: Out of range! Youwanted to '<' below the first cell.
To solve, add some '>'s at the beginning, for example.
an error occured
% echo $? 
5
% bf -n bf_matching.bf < bf_matching.bf
% echo $?
0
Sylwester
fuente
55
Me gusta cómo usaste Brainfuck a pesar de que la pregunta decía que era imposible.
Riking
Oh wow. Estoy sinceramente sorprendido. Asumí que era imposible, pero no lo es.
Konrad Borowski el
1
@xfix: Brainfuck está completo para que pueda hacer cualquier cosa (dadas las restricciones de E / S).
Marinus
2
La completitud de @marinus Turing solo significa que puede hacer todos los cálculos. BrainfuckTuring se completa sin E / S, ya que puede ejecutar un programa que calcula cualquier cálculo y ver el resultado inspeccionando su memoria después de ejecutarlo. BF sin E / S haría que las personas estuvieran menos interesadas, ya que sería difícil hacer utilidades. Por ejemplo, nunca podría haber hecho mi intérprete lisp .
Sylwester
14

Befunge 98 - 26 31 20 19 caracteres

~:']-!\'[-!-+:0`j#q

Se deshizo de algunos condicionales masivos. Ahora el programa funciona de la siguiente manera:

~:   read an input char and duplicate it

']-! push a 1 if the char is the ] char, 0 otherwise

\    swap the comparison value for the duplicated input char

'[-! push a 1 if the char is the [ char, 0 otherwise

-    subtract the two comparison values. If the second one is 1, the first is 0, 
     so the result is -1. Else if the second one is 0, the first is 1 and the result is
     1. Else, the first and the second are both 0 and the result is 0

+    Add the number to the counter (which is 0 if there is none already)

:0`  test if the counter is positive (that'd mean an invalid program). Pushes a 1 if 
     positive, 0 otherwise.

j#q  if the counter is positive, then this jumps to the q. Otherwise, it skips the q 
     and continues to the ~ at the beginning of the line. If there are no more chars in
     the input, then the IP will be sent back to the q. 

qsale del programa y muestra el valor superior como un valor de error. El valor de error será -1 1 si hay demasiados ], 0 si están equilibrados y positivo negativo si hay demasiados [. Si el número es positivo negativo, entonces se necesitan muchos de los valores absolutos de ese número ]para equilibrar el programa.

Editar: Incremento y decremento conmutados. [usado para incrementar el contador y ]usado para disminuirlo. Al cambiarlo, ahorro 1 carácter, porque para la condición de salida, solo tengo que verificar si el contador es positivo, en lugar de negativo.


Versión antigua

~:'[-!j;\1+\#;']-!j;1-#;:0\`j#q

Este código funciona de la siguiente manera:

~    read one char of input
:    duplicate it
'[-! push 1 if the character is [, 0 otherwise
j    jump that number of characters
;    skip until next ;
\1+\ increment counter

similarily for ].

#q when end of input is reached, ~ reflects the IP back. q ends the program with the error value on the stack.

Editar: me di cuenta de que esto aceptaba entradas ][, ahora termina cada vez que el recuento se vuelve negativo, usando

:0\`j
Justin
fuente
1
18 bytes
Jo King
@JoKing eso es bastante bueno, usando la distancia entre [y ]para hacer la comparación con ambos.
Justin
6

J ( 38 35)

exit({:+.<./)+/\+/1 _1*'[]'=/1!:1[3

Explicación:

  • 1!:1[3: leer stdin
  • '[]'=/: crea una matriz donde la primera fila es una máscara de bits de la [s en la entrada, y la segunda fila es la ]s.
  • 1 _1*: multiplica la primera fila por 1 y la segunda fila por -1.
  • +/: suma las columnas de la matriz juntas, dando sangría delta por carácter
  • +/\: crea un total acumulado de estos, dando un nivel de sangría en cada personaje
  • ({:+.<./): devuelve el MCD del elemento final ( {:) y el elemento más pequeño ( <./). Si todos los frenos coinciden, ambos deberían ser 0así para que esto regrese 0. Si las llaves no coinciden, devolverá un valor distinto de cero.
  • exit: establezca el valor de salida en eso y salga.
marinus
fuente
Buen desglose ...
Chris Cashwell
6

rubí (64)

exit $<.read.tr('^[]','').tap{|x|0while x.gsub!('[]','')}.empty?

anteriormente (68) era:

exit ARGF.read.tr('^[]','').tap{|x| 0 while x.gsub!('[]','')}.empty?

Otra solución equivalente utiliza

exit $<.read.tr('^[]','').tap{|x|0while x.gsub!('[]','')}.size>0

no se puede usar sizesolo porque daría falsos negativos (!!!) cuando el número total de paréntesis desequilibrados es múltiplo de 256

reescrito
fuente
Esto es codegolf. Estoy seguro de que puedes eliminar algunos espacios en blanco aquí. Ruby es algo sensible al espacio en blanco, pero lo ignora en muchos casos. Para empezar, no necesita espacios en blanco cerca del =operador.
Konrad Borowski el
mejor versión (algo inspirada en la solución sed + tr). No estoy seguro de que pueda ser mucho mejor que esto. ¡Al menos tiene tan solo 4 espacios en blanco!
reescrito el
1
Y sin embargo, puedo eliminar dos de ellos.
Konrad Borowski el
2
Creo que los espacios alrededor del 0can pueden ir.
marinus
increíble truco espacial, gracias!
reescrito el
5

Perl, 30 caracteres.

Tu expresión regular recursiva de Perl al rescate:

perl -0ne 'exit!/^(([^][]|\[(?1)\])*)$/'

Para aquellos que no están familiarizados con los argumentos de la línea de comandos utilizados aquí: -0permite establecer el carácter de final de línea para la entrada del archivo; el uso -0sin argumento establece el carácter de final de línea en EOF. -nlee automáticamente la entrada (en este caso, el archivo completo) de $_antemano.

Si la expresión regular coincide, devuelve un valor verdadero, que se niega a 0 para el código de salida. De lo contrario, el valor de retorno falso produce un código de salida de 1.

caja de pan
fuente
Supongo que tendré que mejorar mi respuesta para superar esta solución de 30 char.
Justin
Allí. Mi solución ahora es mucho más corta que antes. Buena solución +1
Justin
4

bash (tr + sed) - 42

[ -z `tr -Cd []|sed ":a;s/\[\]//g;t a"` ]

Si no le importan los mensajes de error, puede eliminar el último espacio entre `y ]para obtener la longitud 41.

shiona
fuente
A menos que me pierda algo, tienes un uso inútil de caty $()(también "[]"se puede escribir como []). Acepté esta respuesta, pero hasta que vea mejoras en la longitud, no voy a votar esto, ya que si bien es corto, podría ser mucho más corto para bash.
Konrad Borowski el
Bueno, en realidad no conozco los scripts de shell tan bien. No puedo hacer que la mayoría de esos funcionen. Lo reemplacé $()con backticks e hice el "[]"-> []que sugirió.
shiona
Todavía hay un uso inútil del gato .
Konrad Borowski el
1
Pude haber probado la espada, intenté y fallé, pero estaba equivocado.
shiona
3

Perl (56 caracteres)

$/=0;$r=qr/[^][]*(\[(??{$r})\])*[^][]*/;<>=~m/^$r$/||die

La solución obvia de Perl: una expresión regular recursiva. Lamentablemente es una construcción bastante detallada.

Peter Taylor
fuente
3

Haskell (143)

import System.Exit
f=exitFailure
v c []|c==0=exitSuccess|True=f
v c (s:t)|c<0=f|s=='['=v(c+1)t|s==']'=v(c-1)t|True=v c t
main=getContents>>=v 0

jgon: Usar 2 guardias parece ser más denso que if-then-else. Además, no creo que el suyo verifique que los corchetes estén en el orden correcto ("] [" pasa)

usuario13350
fuente
oh wow, solo vi este comentario cuando se señaló hoy. Se arregló mi código, pero sí, bueno, los guardias parecen ser más densos (+1).
jgon
3

C, 73 64 caracteres

Gracias a las sugerencias de breadbox (aunque esto probablemente requiera little-endian para funcionar):

i;main(c){while(read(0,&c,1)*(i+1))i+=(c==91)-(c==93);return i;}

Cómo funciona:

  • implícito int global ise inicializa a 0
  • cse convierte en un int implícito que obtiene argc(inicializado a 1 pero no nos importa, siempre y cuando los bits más altos no estén configurados)
  • read(0,&c,1)lee un solo carácter en el byte bajo de c (en arquitecturas little-endian) y devuelve 0 en EOF; i+1 != 0a menos que la cita del paréntesis equilibrado vaya a -1; multiplicarlos juntos funciona como un booleano (seguro) Y que requiere un carácter menos que&&
  • c==91evalúa a 1 para '['y c==93evalúa a 1 para ']'. (Puede haber algún truco complicado que sería más pequeño, pero no puedo pensar en nada).
  • return isale con el código de estado 0 si está equilibrado, no es cero si no lo está. Devolver -1 técnicamente viola POSIX, pero a nadie realmente le importa eso.

Versión previa:

main(i){char c;i=0;while(read(0,&c,1)*(i+1))i+=(c==91)-(c==93);return i;}
mullido
fuente
Usar en getchar()lugar de leer acortará el código y le permitirá usar (implícito) en intlugar de charpara su variable. También recuerde que los globales se inicializan automáticamente a cero.
breadbox
Gracias, me olvidé de getchar (). Sin embargo, no estoy seguro de cómo ayuda el inicio global: la definición de un int global requiere más caracteres que el uso del argumento implícito.
esponjoso
1
Los globales también pueden ser implícitos. Fuera de una función c;define un int global.
breadbox
Mientras tanto, getchar (c) termina no haciéndolo más corto, al menos utilizando este enfoque, porque necesita ser probado para> = 0 de alguna manera, y no se garantiza que un int implícito para c pase a read () trabajo por endianness.
esponjoso
¿Qué hay de ][? Estoy seguro de que no está equilibrado. ¿No tienes que hacer un seguimiento si se vuelve negativo al menos una vez?
vsz
2

Lua, 56

os.exit(("["..io.read"*a".."]"):match"^%b[]$"and 0 or 1)
mniip
fuente
"^%b[]$"¿Que es esto? ¿Puedes explicar? Seguramente, esto no es regex?
Cruncher el
@Cruncher: no lo es. Es el patrón Lua, no la expresión regular (los patrones Lua son similares a las expresiones regulares, pero no lo son). En este caso, coincide con el comienzo de la cadena ( ^), el conjunto equilibrado de [y ]con cualquier cosa entre ( %b[]) y el final de la cadena ( $).
Konrad Borowski el
1

GTB , 55

0→O:0→X[`I@I="[":X+1→X@I="]":X-1→X@X<0:1→O@!!Ig;e]l;e~O

Señoritas []

Use 0para parar.

Timtech
fuente
1

MATEMÁTICA, 88 caracteres

s = "[ [ my crazy code ] [ don't explode please! [] [ :)Ahh) ]  [] []]]";

r=StringReplace;
StringLength@FixedPoint[r[#,"[]"-> ""]&,r[s,Except@Characters["[]"]-> ""]]
Murta
fuente
¡Con la función s name like RegularExpression` y StringLengthnunca puedo ganar contexto de golf de código de texto con Mathematica! :)
Murta
Sé lo que quieres decir :) ToCharacterCodees mucho más largo que ordtambién ... PD: ¿Qué pasa con la configuración de un código de salida?
Ajasja
Length[StringCases[s,"["|"]"]//.{x___,"[","]",y___}:>{x,y}]
alephalpha
1

Rubí, 59 58

Busca el corchete de apertura y cierre, contando [como 1 y ]como -1, y sale si el recuento cae por debajo de 0.

b=0
$<.read.scan(/\]|\[/){exit 1if(b+=92-$&.ord)<0}
exit b
daniero
fuente
1
Votado y acortado por un carácter (eliminé los espacios exit 1en blanco después en caso de que lo solicite).
Konrad Borowski el
1

Hasio , 104 bytes

func main(){l=0;r=0;b=input();foreach (c in b){if(c=="[")l++;if(c=="]")r++;}if(!(r==l))exit(1);exit(0);}

Completamente expandido (la nota no funciona en el intérprete en línea ya que la entrada () está deshabilitada) aquí

Jacob Misirian
fuente
1

Código de máquina de Turing, 286 276 bytes

Nuevamente, estoy usando la sintaxis de la tabla de reglas definida aquí.

0 * * l 1
1 _ ! r Q
5 _ _ r 5
5 * * * W
W [ ! l E
W ] ! l T
W _ _ l I
W * ! r *
E ! ! l *
E * * * R
R _ [ r O
R * * l *
T ! ! l *
T * * * Y
Y _ _ r U
Y * * l *
U [ _ r O
U ! ! * halt-err
I ! ! l *
I _ _ r halt
I * * l halt-err
O ! ! r Q
O _ _ l I
O * * r *
Q ! ! r *
Q * * * W

Termina en estado haltpara aceptar la entrada y halt-errrechazarla.

SuperJedi224
fuente
halt-errpuede ser más corto, como halt*por ejemplo.
Erik the Outgolfer
1

Pyth, 25 bytes

Ilzv::z"[^[\]]"k"]\[""],[

Pruébalo en línea!

Traducción de Python 3:
import re
z=input()
if len(z):
 print(eval(re.sub("]\[","],[",re.sub("[^[\]]","",z))))
hakr14
fuente
1

Haskell 167 , 159)

Lo hice principalmente por diversión, si alguien tiene alguna sugerencia sobre cómo hacerlo más corto, me alegraría escucharlo aunque :)

import System.Exit
p x y b|b=x|True=y
main=getContents>>=(return.all (>=0).scanl (\v->p (v-1) (v+1).(==']')) 0.filter (`elem`"[]"))>>=p exitSuccess exitFailure

Editar: solucionó un problema que me señalaron en los comentarios (se agregaron 11 bytes).

Edición 2: función auxiliar creada para probar predicados utilizando guardias inspirados en el usuario 1350, eliminando 8 bytes.

jgon
fuente
@ user202729 Ese es un punto excelente, que fue súper descuidado. Estoy bastante seguro de que está arreglado ahora.
jgon
1

Stax , 14 11 caracteres

╬Äτ↔EªÉs «Ü

Ejecutar y depurarlo

Crédito a @recursive para -3 bytes.

ASCII equivalente:

.[]Y|&{yz|egp!

Elimine todos los caracteres excepto [], luego elimine []hasta que la cadena ya no cambie. Regrese 1si la cadena final está vacía.

Weijun Zhou
fuente
1
Agradable. Puede usar .[]|&para filtrar los caracteres, y luego reutilizar el literal para 11
recursivo el