Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
    
What about languages that don't allow setting a process exit code? –  Kendall Frey Jan 3 at 17:24
1  
@KendallFrey: Simple, use something else. Or in GolfScript, embed Ruby code. Perhaps this blocks some esoteric programming languages, but well... –  xfix Jan 3 at 17:26
1  
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 at 18:31
    
@marinus: I don't know why you would want that, but I think it's fine. –  xfix Jan 3 at 18:33
    
@GlitchMr: because then I can use GCD(a,b) instead of 0 != a || b. –  marinus Jan 3 at 18:50

15 Answers 15

up vote 3 down vote accepted

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

share|improve this answer
    
is this balanced?: ][ (ie does it fail in your program?) –  Quincunx Jan 3 at 22:46
    
@Quincunx: It fails, as it should. –  Ilmari Karonen Jan 3 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 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 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 at 16:19

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
share|improve this answer

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
share|improve this answer
4  
I like how you used Brainfuck even though the question said that was impossible. –  Riking Jan 4 at 1:09
    
Oh, wow. I'm honestly surprised. I assumed it was impossible, but it's not. –  xfix Jan 4 at 10:34
1  
@xfix: Brainfuck is turing-complete so it can do anything (given the I/O constraints.) –  marinus Jan 8 at 1:38
1  
@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 at 7:37

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.
share|improve this answer
    
Nice breakdown... –  Chris Cashwell Jan 3 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

share|improve this answer
    
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. –  xfix Jan 3 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 at 18:08
1  
And yet, I can remove two of them. –  xfix Jan 3 at 18:18
2  
I think the spaces around the 0 can go. –  marinus Jan 3 at 18:23
    
awesome space trick, thanks! –  rewritten Jan 3 at 18:30

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.

share|improve this answer
    
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. –  xfix Jan 3 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 at 17:51
    
There is still useless use of cat. –  xfix Jan 3 at 17:56
1  
I could've sword I tried and failed this, but I was wrong. –  shiona Jan 3 at 18:09

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.

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

Perl (56 chars)

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

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

share|improve this answer

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;}
share|improve this answer
    
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 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 at 3:17
1  
Globals can also be implicit. Outside of a function c; defines a global int. –  breadbox Jan 4 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 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 at 9:16

Lua, 56

os.exit(("["..io.read"*a".."]"):match"^%b[]$"and 0 or 1)
share|improve this answer
    
"^%b[]$" what is this? Can you explain? Surely, this isn't regex? –  Cruncher Jan 3 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 ($). –  xfix Jan 3 at 18:02

MATHEMATICA, 88 chars

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

r=StringReplace;
StringLength@FixedPoint[r[#,"[]"-> ""]&,r[s,Except@Characters["[]"]-> ""]]
share|improve this answer
    
With function`s name like RegularExpression and StringLength I can never win text code golf context with Mathematica! :) –  Murta Jan 4 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 at 10:14
    
Length[StringCases[s,"["|"]"]//.{x___,"[","]",y___}:>{x,y}] –  alephalpha Jan 6 at 9:51

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)

share|improve this answer

Ruby (59)

Simply iterate the input and count opening brackets against closing brackets along the way.

b=0
$<.chars{|c|exit 1if(b+={?[=>1,?]=>-1}[c]||0)<0}
exit b
share|improve this answer
1  
Upvoted, and shortened by one character (I removed whitespace after exit 1 in case you ask). –  xfix Jan 3 at 21:28

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.

share|improve this answer

Haskell (157) (including import and blank line, 137 without)

Did this mostly for fun, I doubt I could get it under a hundred... If anyone's got any suggestions for how to make it shorter, I'd be glad to hear them

import System.Exit

main=getContents>>=(return.sum.map (\x->if x=='[' then 1 else if x==']' then -1 else 0))>>= \x->if x==0 then exitSuccess else exitFailure
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.