Verify Brainfuck program

Question

Yet another Brainfuck parsing problem, but this time... different.

You are working in the Infinite Monkeys Incorporated, the company making Brainfuck programs, to solve various interesting problems (by accident, no less - after all, the company makes random programs). However, it appears that your fast Turing machines that only execute Brainfuck have a small and expensive problem with syntax errors - make one, and the computer explodes. It's probably a design flaw, but nobody had bothered to find why it happens.

As Turing machines (especially fast ones) are expensive (after all, they have infinity RAM which costs), it would be better to make sure that the program doesn't have any syntax errors before executing the code. Your company is going to run lots of code, so manual verification won't work. Write a program that reads the STDIN for Brainfuck code, and exits with exit status set to anything other than 0 (error) if program has any syntax error (for example, ] is a syntax error, because there is no matching [). Exit with exit status set to 0 if the program is completely fine.

Make sure that your program correctly notices mistakes involving []. You wouldn't want another computer to explode, would you? Oh, and make sure it's as short as possible - your boss pays for short programs (because he thinks they are fast, or something). Oh, and you don't have to code in Brainfuck (in fact, you cannot, because Brainfuck doesn't support exit codes) - your code will be ran on normal computer.

So, as you can see, your job is to check if Brainfuck program is "valid" (has paired [] symbols). Please note that Brainfuck programs can have other characters than [], so don't refuse the program just because it has other commands. Smallest code wins, but probably you would care more about upvotes anyway.

Answer 1

GolfScript, 18 chars

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

This code runs successfully with exit code 0 (and prints some garbage to stdout) if the square brackets in the input are balanced. If they are not, it fails with a non-zero exit code and prints an error message to stderr, e.g.:

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

or

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

Since the challenge said nothing about output to stdout / stderr, I figure this qualifies. In any case, you can always redirect those to /dev/null.

Explanation:

The code {[]`?)}, strips everything but square brackets from the input, and the ~ evaluates the result as GolfScript code. The tricky part is that unbalanced brackets are perfectly legal in GolfScript (and, indeed, my code includes one!), so we need some other way to make the code crash.

The trick I'm using is to leave a copy of the input at the bottom of the stack, collect the entire stack into an array (using the unbalanced ]) and shift the first element off. At this point, three things can happen:

• If the input ended in an unclosed [, trying to shift an element off an empty array will crash the interpreter (which, in this case, is exactly what we want!)
• If the brackets in the input were balanced, the shifted element will be the original input string.
• Otherwise (if the input had an unopened ] or an unclosed [) it will be an array.

My original 14-char entry then compared the shifted value with a string, which would crash if it was a nested array. Unfortunately, it turns out that comparing a flat (or, in particular, empty) array with a string is also legal in GolfScript, so I had to switch tack.

My current submission, instead, uses a very brute-force method to tell arrays from strings: it un-evals them and tries to find the first occurrence of [ (ASCII code 91), which will be zero if and only if the un-evaled variable was an array. If so, dividing the zero with itself triggers the desired crash.

Ps. Two other 18-char solutions are:

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

and

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

Alas, I haven't yet found a shorter way to solve the "empty array problem".

Answer 2

Brainfuck 76 bytes

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

This goes out of it's bonds if square brackets are unbalanced turning the bf interpreter/compiler to fail runtime and some of them have exit codes to reflect that.

requires eof=0, wrapping values and finit number of cells

In Ubuntu you can use the interpreter 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

Answer 3

Befunge 98 - 26 31 20 19 chars

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

Got rid of some massive conditionals. Now the program works as follows:

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

q quits the program and pops the top value as an error value. The error value will be -1 1 if there are too many ]'s, 0 if they are balanced, and positive negative if there are too many ['s. If the number is positive negative, then that many the absolute value of that number ]'s are needed to balance the program.

Edit: Switched increment and decrement. [ used to increment the counter and ] used to decrement it. By switching it, I save 1 char, because for the exit condition, I only have to check if the counter is positive, rather than negative.

---

Old version

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

This code works as follows:

~    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: realized that this accepted inputs like ][, now it ends whenever the count gets negative, using

:0\`j

Answer 4

ruby (64)

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

previously (68) it was:

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

Another equivalent solution uses

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

can't use size alone because it would give false negatives (!!!) when the total number of unbalanced brackets is multiple of 256

Answer 5

J (38 35)

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

Explanation:

• 1!:1[3: read stdin
• '[]'=/: create a matrix where the first row is a bitmask of the [s in the input, and the second row is the ]s.
• 1 _1*: multiply the first row by 1 and the second row by -1.
• +/: sum the columns of the matrix together, giving delta-indentation per character
• +/\: create a running total of these, giving indentation level at each character
• ({:+.<./): return the GCD of the final element ({:) and the smallest element (<./). If all the braces match, both of these should be 0 so this will return 0. If the braces do not match, it will return a nonzero value.
• exit: set the exit value to that and exit.

Answer 6

Perl, 30 characters

Your basic Perl recursive regex to the rescue:

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

For those unfamiliar with the command-line arguments used here: -0 allows one to set the line-ending character for the purposes of file input; using -0 with no argument sets the line-ending character to EOF. -n automatically reads the input (in this case, the entire file) into $_ beforehand.

If the regex matches, it returns a true value, which is negated to 0 for the exit code. Otherwise, the false return value yields an exit code of 1.

Answer 7

bash (tr + sed) - 42

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

If you don't mind error messages then you can remove the last space between ` and ] to get length 41.

Answer 8

Perl (56 chars)

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

The obvious Perl solution: a recursive regex. Unfortunately it's a rather verbose construct.

Answer 9

C, 73 64 chars

Thanks to suggestions from breadbox (although this probably requires little-endian to work):

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

How it works:

• implicit int global i gets initialized to 0
• c becomes an implicit int which gets argc (initialized to 1 but we don't care, just as long as the higher bits aren't set)
• read(0,&c,1) reads a single character into the low byte of c (on little-endian architectures) and returns 0 at EOF; i+1 != 0 unless the balanced bracket quote goes to -1; multiplying them together works as a (safe) boolean AND that takes one less char than &&
• c==91 evaluates to 1 for '[', and c==93 evaluates to 1 for ']'. (There might be some fiddly bit-fiddling trick that would be smaller but I can't think of anything.)
• return i exits with status code 0 if it's balanced, non-zero if it isn't. Returning -1 technically violates POSIX but nobody actually cares about that.

Previous version:

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

Answer 10

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: Using 2 guards seems to be more dense than if-then-else. Also, I don't think yours checks that the brackets are in the right order ("][" passes)

Answer 11

Lua, 56

os.exit(("["..io.read"*a".."]"):match"^%b[]$"and 0 or 1)

Answer 12

Stax, 14 11 characters

╬Äτ↔EªÉs «Ü

Run and debug it

Credit to @recursive for -3 bytes.

ASCII equivalent:

.[]Y|&{yz|egp!

Remove all characters except [], then remove [] until the string no longer changes. Return 1 if the final string is empty.

Answer 13

Pyth, 25 bytes

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

Try it online!

Python 3 translation:

import re
z=input()
if len(z):
 print(eval(re.sub("]\[","],[",re.sub("[^[\]]","",z))))

Answer 14

Ruby, 59 58

Scans for opening and closing bracket, counting [ as 1 and ] as -1, and exits if the count drops below 0.

b=0
$<.read.scan(/\]|\[/){exit 1if(b+=92-$&.ord)<0}
exit b

Answer 15

GTB, 55

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

Misses []

Use 0 to stop.

Answer 16

Haskell (167,159)

Did this mostly for fun, if anyone's got any suggestions for how to make it shorter, I'd be glad to hear them tho :)

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

Edit: Fixed an issue pointed out to me in the comments (added 11 bytes).

Edit 2: Created auxiliary function for testing predicates using guards inspired by user13350, removing 8 bytes.

Answer 17

MATHEMATICA, 88 chars

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

r=StringReplace;
StringLength@FixedPoint[r[#,"[]"-> ""]&,r[s,Except@Characters["[]"]-> ""]]

Answer 18

Hassium, 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);}

Full expanded (note doesn't work in online interpreter as input() is disabled) here

Answer 19

Turing Machine Code, 286 276 bytes

Again, I'm using the rule table syntax defined here.

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

Terminates in state halt to accept the input and halt-err to reject it.