Verifique o programa Brainfuck

17

Mais um problema de análise de Brainfuck, mas desta vez ... diferente.

Você está trabalhando na Infinite Monkeys Incorporated, a empresa que faz os programas Brainfuck, para resolver vários problemas interessantes (por acidente, nada menos - afinal, a empresa faz programas aleatórios). No entanto, parece que suas máquinas rápidas de Turing que executam apenas o Brainfuck têm um problema pequeno e caro com erros de sintaxe - crie uma e o computador exploda. Provavelmente é uma falha de design, mas ninguém se deu ao trabalho de descobrir por que isso acontece.

Como as máquinas de Turing (especialmente as mais rápidas) são caras (afinal de contas, elas têm RAM infinita que custa), seria melhor garantir que o programa não tenha nenhum erro de sintaxe antes de executar o código. Sua empresa executará muitos códigos, portanto a verificação manual não funcionará. Escreva um programa que leia o código STDIN para Brainfuck e saia com o status de saída definido como algo diferente de 0 (erro) se o programa tiver algum erro de sintaxe (por exemplo, ]é um erro de sintaxe, porque não há correspondência [). Saia com o status de saída definido como 0 se o programa estiver completamente correto.

Verifique se o seu programa percebe corretamente os erros envolvidos []. Você não gostaria que outro computador explodisse, queria? Ah, e verifique se é o mais curto possível - seu chefe paga por programas curtos (porque ele acha que eles são rápidos, ou algo assim). Ah, e você não precisa codificar no Brainfuck (na verdade, não pode, porque o Brainfuck não suporta códigos de saída) - seu código será executado no computador normal.

Portanto, como você pode ver, seu trabalho é verificar se o programa Brainfuck é "válido" (possui []símbolos emparelhados ). Observe que os programas Brainfuck podem ter outros caracteres além de [], portanto, não recuse o programa apenas porque possui outros comandos. O menor código vence, mas provavelmente você se importaria mais com upvotes.

Konrad Borowski
fonte
11
E os idiomas que não permitem definir um código de saída do processo?
Kendall Frey
11
@KendallFrey: Simples, use outra coisa. Ou no GolfScript, incorpore o código Ruby. Talvez este blocos algumas linguagens de programação esotéricas, mas bem ...
Konrad Borowski
11
Não há problema em definir o código de erro para algo diferente de 1 (desde que não seja 0, é claro) em caso de falha?
marinus
@ Marinus: Não sei por que você quer isso, mas acho que está bem.
Konrad Borowski
@ GlitchMr: porque então eu posso usar em GCD(a,b)vez de 0 != a || b.
marinus

Respostas:

6

GolfScript, 18 caracteres

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

Esse código é executado com êxito com o código de saída 0 (e imprime algum lixo em stdout) se os colchetes na entrada estiverem balanceados. Caso contrário, ele falhará com um código de saída diferente de zero e imprimirá uma mensagem de erro no stderr, por exemplo:

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

ou

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

Como o desafio não disse nada sobre saída para stdout / stderr, acho que isso se qualifica. Em qualquer caso, você sempre pode redirecioná-los para /dev/null.

Explicação:

O código {[]`?)},retira tudo, exceto colchetes, da entrada e ~avalia o resultado como código GolfScript. A parte complicada é que colchetes desequilibrados são perfeitamente legais no GolfScript (e, de fato, meu código inclui um!), Portanto, precisamos de outra maneira de fazer com que o código falhe.

O truque que estou usando é deixar uma cópia da entrada na parte inferior da pilha, coletar a pilha inteira em uma matriz (usando o desbalanceado ]) e desativar o primeiro elemento. Neste ponto, três coisas podem acontecer:

  • Se a entrada terminar em um não fechado [, tentar deslocar um elemento de uma matriz vazia trava o intérprete (que, nesse caso, é exatamente o que queremos!)
  • Se os colchetes na entrada estiverem balanceados, o elemento deslocado será a sequência de entrada original.
  • Caso contrário (se a entrada tiver uma abertura ]ou uma abertura [), será uma matriz.

Minha entrada original de 14 caracteres comparou o valor alterado com uma string, que falharia se fosse uma matriz aninhada. Infelizmente, acontece que comparar uma matriz plana (ou, em particular, vazia) com uma string também é legal no GolfScript, então tive que mudar de direção.

Minha submissão atual, em vez disso, usa um método de força bruta para diferenciar matrizes de strings: desvaloriza-as e tenta encontrar a primeira ocorrência de [(código ASCII 91), que será zero se e somente se as não avaliadas A variável era uma matriz. Nesse caso, dividir o zero consigo dispara a falha desejada.

Ps. Duas outras soluções de 18 caracteres são:

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

e

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

Infelizmente, ainda não encontrei uma maneira mais curta de resolver o "problema do array vazio".

Ilmari Karonen
fonte
é este equilibrada ?: ][(ou seja, não é falhar em seu programa?)
Justin
@ Quincunx: falha, como deveria.
Ilmari Karonen
No entanto, acabou por aceitar [[]; Corrigi-o agora, ao custo de 4 caracteres, e passa todos os meus testes agora.
Ilmari Karonen
Se bem entendi, você tinha uma solução de 14 caracteres que falha ao distinguir entre uma string e uma matriz apenas no caso em que a matriz está vazia. 1+transformará uma matriz vazia em uma matriz não vazia, uma matriz não vazia em uma matriz não vazia e uma sequência em uma sequência.
Peter Taylor
@ PeterTaylor: Sim, foi .{[]`?)},~](n<. Eu tentei o seu 1+, mas parece que o array precisa conter algo diferente de um número (presumivelmente para que o intérprete falhe quando ele tenta comparar recursivamente um caractere com um array / string). O uso n+também não funciona, uma vez que força a matriz a uma string; [n]+ faz o trabalho, mas ainda me coloca em 18 caracteres.
Ilmari Karonen
17

Brainfuck 76 bytes

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

Isso desaparece se os colchetes estiverem desequilibrados, tornando o interpretador / compilador bf com falha no tempo de execução e alguns deles possuem códigos de saída para refletir isso.

requer eof = 0, valores de quebra automática e número finito de células

No Ubuntu você pode usar o 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
fonte
5
Gosto de como você usou o Brainfuck, mesmo que a pergunta dissesse que era impossível.
Riking
Uau. Estou sinceramente surpreso. Presumi que era impossível, mas não é.
precisa saber é o seguinte
11
@xfix: Brainfuck é Turing completo para que ele possa fazer qualquer coisa (dadas as limitações de E / S.)
marinus
2
A completude de Turing significa apenas que ele pode fazer todos os cálculos. Brainfucké Turing completo sem E / S, pois você pode executar um programa que calcula qualquer cálculo e vê o resultado inspecionando sua memória após a execução. O BF sem E / S tornaria as pessoas menos interessadas, pois seria difícil criar utilitários. Por exemplo, eu nunca poderia ter feito meu intérprete de Lisp .
21439 Sylwester
14

Befunge 98 - 26 31 20 19 caracteres

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

Livre-se de alguns condicionais massivos. Agora o programa funciona da seguinte maneira:

~:   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. 

qsai do programa e exibe o valor superior como um valor de erro. O valor do erro será -1 1 se houver muitos ], 0 se estiverem equilibrados e negativo positivo se houver muitos [. Se o número for negativo positivo , serão necessários muitos do valor absoluto desse número ]para equilibrar o programa.

Editar: incremento e decréscimo comutado. [usado para incrementar o contador e ]decrementá-lo. Ao alterná-lo, eu salvo 1 caractere, porque para a condição de saída, só tenho que verificar se o contador é positivo, e não negativo.


Versão antiga

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

Este código funciona da seguinte maneira:

~    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.

Edit: percebeu que isso aceita entradas como ][, agora termina sempre que a contagem fica negativa, usando

:0\`j
Justin
fonte
11
18 bytes
Jo King
@JoKing isso é muito bom, usando a distância entre [e ]para fazer a comparação com ambos.
23718 Justin
6

J ( 38 35)

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

Explicação:

  • 1!:1[3: leia stdin
  • '[]'=/: crie uma matriz em que a primeira linha seja uma máscara de bit do [ s na entrada e a segunda linha é os ]s.
  • 1 _1*: multiplique a primeira linha por 1 e a segunda linha por -1.
  • +/: soma as colunas da matriz, fornecendo recuo delta por caractere
  • +/\: crie um total atual, fornecendo nível de recuo em cada caractere
  • ({:+.<./): retorna o GCD do elemento final ( {:) e o menor elemento ( <./). Se todas as chaves coincidirem, ambas devem ser, 0portanto, isso retornará0 . Se os colchetes não corresponderem, ele retornará um valor diferente de zero.
  • exit: defina o valor de saída como esse e saia.
marinus
fonte
Agradável colapso ...
Chris Cashwell
6

rubi (64)

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

anteriormente (68) era:

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

Outra solução equivalente usa

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

não pode usar sizesozinho porque daria falsos negativos (!!!) quando o número total de colchetes desequilibrados for múltiplo de 256

reescrito
fonte
Isso é codegolf. Tenho certeza de que você pode remover alguns espaços em branco aqui. O Ruby é um pouco sensível ao espaço em branco, mas o ignora em muitos casos. Para começar, você não precisa de espaço em branco próximo ao =operador.
precisa saber é o seguinte
versão melhor (um pouco inspirada na solução sed + tr). Não tenho certeza se posso ficar muito melhor que isso. Pelo menos tem apenas 4 espaços em branco!
reescrito
11
E, no entanto, posso remover dois deles.
218 Konrad Borowski
2
Eu acho que os espaços ao redor da 0lata podem ir.
marinus
truque de espaço incrível, obrigado!
reescrito
5

Perl, 30 caracteres

Sua regex recursiva básica do Perl para o resgate:

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

Para aqueles que não estão familiarizados com os argumentos de linha de comando usados ​​aqui: -0permite definir o caractere de final de linha para fins de entrada de arquivo; usar -0sem argumento define o caractere de final de linha como EOF. -nlê automaticamente a entrada (neste caso, o arquivo inteiro) em$_ antes.

Se o regex corresponder, ele retornará um valor verdadeiro, que é negado a 0 para o código de saída. Caso contrário, o valor de retorno falso produzirá um código de saída 1.

caixa de pão
fonte
Acho que vou ter que responder melhor à minha resposta para vencer essa solução de 30 caracteres.
Justin
Lá. Minha solução agora é muito mais curta do que era antes. Ótima solução. +1
Justin
4

festança (tr + sed) - 42

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

Se você não se importa com as mensagens de erro, pode remover o último espaço entre `e ]obter o comprimento 41.

shiona
fonte
A menos que eu perca alguma coisa, você tem uso inútil de ( cate $()também "[]"pode ser escrito como []). Aceitei esta resposta, mas até ver melhorias no comprimento, não vou votar mais, pois, embora curta, pode ser muito menor para o bash.
precisa saber é o seguinte
Bem, na verdade eu não conheço scripts de shell tão bem. Não consigo fazer a maioria deles funcionar. Troquei $()com acentos graves e fez o "[]"-> []você sugeriu.
Shiona
Ainda há uso inútil de gato .
precisa saber é o seguinte
11
Eu poderia ter tentado e falhado com isso, mas estava errado.
shiona
3

Perl (56 caracteres)

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

A solução Perl óbvia: um regex recursivo. Infelizmente, é uma construção bastante detalhada.

Peter Taylor
fonte
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

to jgon: Usar 2 guardas parece ser mais denso do que se-então-outro. Além disso, não acho que o seu verifique se os colchetes estão na ordem correta ("] [" passa)

user13350
fonte
uau, só vi esse comentário quando foi apontado hoje. Corrigido meu código, mas, sim, legal, os guardas parecem ser mais densos (+1).
jgon
3

C, 73 64 caracteres

Graças às sugestões da breadbox (embora isso provavelmente exija pouco trabalho):

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

Como funciona:

  • global implícito implícito ié inicializado como 0
  • ctorna-se um int implícito que é obtido argc(inicializado como 1, mas não nos importamos, desde que os bits mais altos não estejam definidos)
  • read(0,&c,1)lê um único caractere no byte baixo de c (em arquiteturas little-endian) e retorna 0 no EOF; i+1 != 0a menos que a cotação entre colchetes seja -1; multiplicá-los juntos funciona como um booleano (seguro) E que leva um caractere a menos do que&&
  • c==91avalia como 1 para '['ec==93 avalia como 1 para ']'. (Pode haver algum truque minucioso que seria menor, mas não consigo pensar em nada.)
  • return isai com o código de status 0 se estiver equilibrado, diferente de zero se não estiver. Retornar -1 tecnicamente viola o POSIX, mas ninguém se importa com isso.

Versão anterior:

main(i){char c;i=0;while(read(0,&c,1)*(i+1))i+=(c==91)-(c==93);return i;}
fofo
fonte
Usar em getchar()vez de ler reduzirá o código e permitirá que você use (implícito) em intvez de charpara sua variável. Lembre-se também de que as globais são automaticamente inicializadas em zero.
breadbox
Obrigado, eu esqueci o getchar (). Porém, não tenho certeza de como o init global ajuda - definir um int global leva mais caracteres do que usar o argc implícito.
macia
11
Globais também podem estar implícitos. Fora de uma função c;define um int global.
breadbox
Enquanto isso, o getchar (c) acaba não o tornando mais curto, pelo menos usando essa abordagem, porque precisa ser testado para> = 0 de alguma forma, e um int implícito para c passado para read () não é garantido. trabalho devido a endianness.
macia
Que tal ][? Tenho certeza que não está equilibrado. Você não precisa acompanhar se é negativo pelo menos uma vez?
vsz
2

Lua, 56

os.exit(("["..io.read"*a".."]"):match"^%b[]$"and 0 or 1)
mniip
fonte
"^%b[]$"o que é isso? Você pode explicar? Certamente, isso não é regex?
Cruncher
@ Cruncher: Não é. É padrão Lua, não regex (os padrões Lua são semelhantes aos regexes, mas não são). Nesse caso, ele corresponde ao início da string ( ^), conjunto equilibrado de [e ]com qualquer coisa entre ( %b[]) e final da string ( $).
precisa saber é o seguinte
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

Sente falta []

Use 0para parar.

Timtech
fonte
1

MATEMÁTICA, 88 caracteres

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

r=StringReplace;
StringLength@FixedPoint[r[#,"[]"-> ""]&,r[s,Except@Characters["[]"]-> ""]]
Murta
fonte
Com a função s name like RegularExpression` e StringLengthnunca consigo ganhar o contexto de golfe com código de texto com o Mathematica! :)
Murta
Eu sei o que você quer dizer :) ToCharacterCodeé muito mais demorado do ordque isso ... PS: Que tal definir um código de saída?
precisa saber é o seguinte
Length[StringCases[s,"["|"]"]//.{x___,"[","]",y___}:>{x,y}]
Alephalpha
1

Rubi, 59. 58

Procura entre colchetes de abertura e fechamento, contando [como 1 e ]como -1, e sai se a contagem cair abaixo de 0.

b=0
$<.read.scan(/\]|\[/){exit 1if(b+=92-$&.ord)<0}
exit b
daniero
fonte
11
Votado e reduzido por um caractere (removi o espaço exit 1em branco depois , caso você pergunte).
precisa saber é o seguinte
1

Hássio , 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);}

Expandido completo (a nota não funciona no intérprete online, pois a entrada () está desativada) aqui

Jacob Misirian
fonte
1

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

Mais uma vez, estou usando a sintaxe da tabela de regras definida aqui.

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 no estado haltpara aceitar a entrada e halt-errrejeitá-la.

SuperJedi224
fonte
halt-errpode ser mais curto, como halt*por exemplo.
Erik the Outgolfer
1

Pitão, 25 bytes

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

Experimente online!

Tradução Python 3:
import re
z=input()
if len(z):
 print(eval(re.sub("]\[","],[",re.sub("[^[\]]","",z))))
hakr14
fonte
1

Haskell ( 167 , 159)

Fiz isso principalmente por diversão, se alguém tiver alguma sugestão de como reduzi-lo, ficaria feliz em ouvi-los :)

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: Corrigido um problema apontado para mim nos comentários (adicionado 11 bytes).

Edit 2: Função auxiliar criada para testar predicados usando proteções inspiradas no user13350, removendo 8 bytes.

jgon
fonte
@ user202729 Esse é um ponto excelente, que foi super descuidado. Tenho certeza que está consertado agora.
jgon
1

Stax , 14 11 caracteres

╬Äτ↔EªÉs «Ü

Execute e depure

Crédito para @recursive por -3 bytes.

Equivalente ASCII:

.[]Y|&{yz|egp!

Remova todos os caracteres [], exceto e remova []até que a sequência não seja mais alterada. Retorne 1se a sequência final estiver vazia.

Weijun Zhou
fonte
11
Agradável. Você pode usar .[]|&para filtrar os caracteres e, em seguida, re-utilizar o literal para 11
recursiva