# Verify Brainfuck program

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.

• What about languages that don't allow setting a process exit code? – Kendall Frey Jan 3 '14 at 17:24
• @KendallFrey: Simple, use something else. Or in GolfScript, embed Ruby code. Perhaps this blocks some esoteric programming languages, but well... – Konrad Borowski Jan 3 '14 at 17:26
• Is it okay to set the error code to something other than 1 (as long as it's not 0 of course) on failure? – marinus Jan 3 '14 at 18:31
• @marinus: I don't know why you would want that, but I think it's fine. – Konrad Borowski Jan 3 '14 at 18:33
• @GlitchMr: because then I can use GCD(a,b) instead of 0 != a || b. – marinus Jan 3 '14 at 18:50

## 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".

• is this balanced?: ][ (ie does it fail in your program?) – Justin Jan 3 '14 at 22:46
• @Quincunx: It fails, as it should. – Ilmari Karonen Jan 3 '14 at 22:52
• However, it did turn out to accept [[]; I've fixed it now, at the cost of 4 chars, and it passes all my tests now. – Ilmari Karonen Jan 4 '14 at 0:16
• If I understand you correctly, you had a 14-char solution which fails to distinguish between a string and an array only in the case that the array is empty. 1+ will turn an empty array into a non-empty array, an non-empty array into a non-empty array, and a string into a string. – Peter Taylor Jan 4 '14 at 9:43
• @PeterTaylor: Yes, it was .{[]?)},~](n<. I did try your 1+, but it seems that the array needs to contain something other than a number (presumably so that the interpreter will crash when it tries to recursively compare a character with an array/string). Using n+ doesn't work either, since it coerces the array to a string; [n]+ does work, but still puts me at 18 chars. – Ilmari Karonen Jan 4 '14 at 16:19

# 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

• I like how you used Brainfuck even though the question said that was impossible. – Riking Jan 4 '14 at 1:09
• Oh, wow. I'm honestly surprised. I assumed it was impossible, but it's not. – Konrad Borowski Jan 4 '14 at 10:34
• @xfix: Brainfuck is turing-complete so it can do anything (given the I/O constraints.) – marinus Jan 8 '14 at 1:38
• @marinus Turing completness only means it can do all computations. Brainfuck is Turing complete without I/O as you can run a program that calculates any calculation and see the result by inspecting it's memory after running. BF without I/O would make people less interested as it would be difficult to make utilities. e.g. i could never have made my lisp interpreter. – Sylwester Jan 8 '14 at 7:37

# Befunge 98 - 263120 19 chars

~:']-!\'[-!-+:0j#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

• 18 bytes – Jo King Apr 9 '18 at 8:57
• @JoKing that's pretty nice, using the distance between [ and ] to do the comparison with both. – Justin Apr 9 '18 at 15:42

## 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.
• Nice breakdown... – Chris Cashwell Jan 3 '14 at 20:51

# 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

• This is codegolf. I'm sure you can remove some whitespace here. Ruby is somewhat whitespace sensitive, but it ignores it in many cases. To begin with, you don't need whitespace near = operator. – Konrad Borowski Jan 3 '14 at 18:03
• better version (somewhat inspired by the sed+tr solution). I'm not sure I can get much better than this. At least it has as low as 4 whitespaces! – rewritten Jan 3 '14 at 18:08
• And yet, I can remove two of them. – Konrad Borowski Jan 3 '14 at 18:18
• I think the spaces around the 0 can go. – marinus Jan 3 '14 at 18:23
• awesome space trick, thanks! – rewritten Jan 3 '14 at 18:30

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

• Guess I'll have to golf my answer better to beat this 30 char solution. – Justin Jan 4 '14 at 7:37
• There. My solution is now much shorter than it was before. Nice solution. +1 – Justin Jan 4 '14 at 9:04

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

• Unless I miss anything, you have useless use of cat and $() (also "[]" can be written as []). I accepted this answer, but until I will see improvements in length, I'm not going to upvote this, as while short, it could be way shorter for bash. – Konrad Borowski Jan 3 '14 at 17:43 • Well, actually I don't know shell scripting that well. I'm unable to make most of those work. I replaced $() with backticks and did the "[]" -> [] you suggested. – shiona Jan 3 '14 at 17:51
• There is still useless use of cat. – Konrad Borowski Jan 3 '14 at 17:56
• I could've sword I tried and failed this, but I was wrong. – shiona Jan 3 '14 at 18:09

## Perl (56 chars)

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


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

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)

• oh wow, only saw this comment when it was pointed out today. Fixed my code, but yeah nice, guards do seem to be denser (+1). – jgon Apr 10 '18 at 1:26

# 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;}

• Using getchar() instead of read will shorten the code and allow you to use (implicit) int instead of char for your variable. Also remember that globals are automatically initialized to zero. – breadbox Jan 4 '14 at 0:39
• Thanks, I forgot about getchar(). Not sure how the global init helps, though - defining a global int i takes more characters than using the implicit argc one. – fluffy Jan 4 '14 at 3:17
• Globals can also be implicit. Outside of a function c; defines a global int. – breadbox Jan 4 '14 at 3:21
• Meanwhile, getchar(c) ends up not making it any shorter, at least using this approach, because it needs to be tested for >=0 in some way, and an implicit int for c passed into read() isn't guaranteed to work due to endianness. – fluffy Jan 4 '14 at 3:22
• What about ][ ? I'm sure it's not balanced. Don't you have to keep track whether it goes negative at least once? – vsz Jan 4 '14 at 9:16

# Lua, 56

os.exit(("["..io.read"*a".."]"):match"^%b[]$"and 0 or 1)  • "^%b[]$" what is this? Can you explain? Surely, this isn't regex? – Cruncher Jan 3 '14 at 17:57
• @Cruncher: It's not. It's Lua pattern, not regex (Lua patterns are similar to regexes, but they aren't). In this case it matches the beginning of string (^), balanced set of [ and ] with anything inbetween (%b[]), and end of string ($). – Konrad Borowski Jan 3 '14 at 18:02 ## 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. ## MATHEMATICA, 88 chars s = "[ [ my crazy code ] [ don't explode please! [] [ :)Ahh) ] [] []]]"; r=StringReplace; StringLength@FixedPoint[r[#,"[]"-> ""]&,r[s,Except@Characters["[]"]-> ""]]  • With functions name like RegularExpression and StringLength I can never win text code golf context with Mathematica! :) – Murta Jan 4 '14 at 1:37 • I know what you mean:) ToCharacterCode is much longer than ord as well... PS: What about setting an exit code? – Ajasja Jan 4 '14 at 10:14 • Length[StringCases[s,"["|"]"]//.{x___,"[","]",y___}:>{x,y}] – alephalpha Jan 6 '14 at 9:51 # 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  • Upvoted, and shortened by one character (I removed whitespace after exit 1 in case you ask). – Konrad Borowski Jan 3 '14 at 21:28 # 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 # 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. • halt-err can be shorter, such as halt* for example. – Erik the Outgolfer Apr 9 '18 at 19:22 ## 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))))


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.

• – user202729 Apr 9 '18 at 11:56
• @user202729 That's an excellent point, that was super careless. Pretty sure it's fixed now. – jgon Apr 10 '18 at 1:25

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

• Nice. You can use .[]|& to filter the characters, and then re-use the literal for 11 – recursive Apr 9 '18 at 17:38