Prelude Syntax-Checker

Question

Prelude is an esoteric programming language, which has very few, but unusual, restrictions on what constitutes a valid program. Any block of printable ASCII text ("block" meaning that lines of printable ASCII are separated by newlines - 0x0A) is valid provided that:

• Every (vertical) column of text contains at most one of ( and ).
• Ignoring their vertical position, the ( and ) are balanced, that is, each ( is paired with exactly one ) to the right of it, and vice versa.

Write a program or function which, given a string containing printable ASCII and newlines, determines if it constitutes a valid Prelude program. You may take input via STDIN (or closest alternative), command-line argument or function argument. The result may be returned or printed to STDOUT, using any two fixed truthy/falsy values of your choice.

You must not assume that the input is rectangular.

This is code golf, so the shortest submission (in bytes) wins.

Examples

The following are valid Prelude programs (in fact, they're even real Prelude programs):

?1-(v  #1)-             
1   0v ^(#    0)(1+0)#)!
    (#)  ^#1-(0 #       

1(#  1) v #  - 1+)
    vv (##^v^+
? v-(0 # ^   #)
?
  1+              1-!

And here are a number of inputs, all of which are invalid:

#(#(##)##)##(
)##(##(##)#)#

#(#)
)###

#(##
(##)

(##)
(#)#

(##)
(###

#(#)
(##)

#(#)
###)

#()#
()##

#(#)##
###
###(#)

Answer 1

CJam, 57 56 bytes

qN/z_{_"()"--W<},,\s:Q,{)Q/({_')/,\'(/,-}:T~\sT0e>+z+}/!

Too long, can be golfed a lot. Explanation to be added once I golf it.

Brief explanation

There are two checks in the code:

• First filter checks that each column as at most 1 bracket. The final output of the filter is the number of columns with more than 1 brackets.
• Second we convert the input into column major format and then split it on each index into two parts.
  • In each of these two parts, (Number of "(" - Number of ")") should be complimenting each other. So when you add them up, it should result to 0. Any part that fails this property makes the whole input have non matching brackets.
  • I also have to make sure that "(" are to the left of ")". This means that the value of Number of "(" - Number of ")" cannot be negative for the right side block.

Try it online here

Answer 2

Python 2, 128 119 105 bytes

def F(p):
 v=n=1
 for r in map(None,*p.split("\n")):A,B=map(r.count,"()");n+=B-A;v*=n<2>A+B
 return n*v>0

Did you know that you can map None in Python 2?

Explanation

We want to start by transposing the Prelude so that columns become rows. Usually we would do this with zip, but since zip truncates to the shortest row length and itertools.zip_longest is far too long for code-golf, it seems like there's no short way to do what we want...

Except for mapping None:

>>> print map(None,*[[1,2,3],[4],[5,6]])
[(1, 4, 5), (2, None, 6), (3, None, None)]

Unfortunately (or rather, fortunately for all non-golf purposes), this only works in Python 2.

As for n and v:

• n acts like a stack, counting 1 - <number of unmatched '(' remaining>. For every ( we see we subtract 1, and for every ) we see we add 1. Hence if n >= 2 at any point, then we've seen too many )s and the program is invalid. If n doesn't finish on 1, then we have at least one unmatched ( remaining.
• v checks validity, and starts at 1. If the program is ever invalid (n >= 2 or A+B >= 2), then v becomes 0 to mark invalidity.

Hence if the program is valid, then by the end we must have n = 1, v = 1. If the program is invalid, then by the end we must either have v = 0, or v = 1, n <= 0. Therefore validity can be succinctly expressed as n*v>0.

(Thanks to @feersum for a multitude of good suggestions which took off 14 bytes!)

Previous, more readable submission:

def F(p):
 p=map(None,*p.split("\n"));v=n=0
 for r in p:R=r.count;A=R("(");B=R(")");n+=A-B;v|=A+B>1or n<0
 return n<1>v

Answer 3

J, 64 bytes

Input is a string with a trailing newline. Output is 0 or 1.

(0=(1<|s)s+[:(|@{:+(0>])s)[:+/\]s=.+/@:)@(1 _1 0{~[:'()'&i.];.2)

Example usage

   ]in=.'#(#)##',LF,'###',LF,'###(#)',LF
#(#)##
###
###(#)

   ((0=(1<|s)s+[:(|@{:+(0>])s)[:+/\]s=.+/@:)@(1 _1 0{~[:'()'&i.];.2)) in
0

The method is the following

• cut input at newlines and put into a matrix ];.2
• map ( / ) / anything else into 1 / -1 / 0 1 _1 0{~[:'()'&i.]
• define an s=.+/@: adverb which added to a verb sums the verbs array output

• add values in columns ]s

  • check positive () balance in every prefix [:(0>])s)[:+/\]
  • check equal () balance in the whole list (i.e. in the last prefix) |@{:@]

• add abs(values) in columns and check every element for a max value of 1 (1<|s)s

• as all the previous checks yielded positive at failure we add them up and compare to 0 to get the validity of the input 0=]

Answer 4

J, 56 bytes

3 :'*/0<: ::0:(+/\*:b),-.|b=.+/+.^:_1]0|:''()''=/];.2 y'

That is an anonymous function accepting a string with a trailing newline and returning 0 or 1. Reading from right to left:

• ];.2 y, as in the other J submission, cuts the string y at all occurrences of its last character (which is why the input needs a trailing newline) and makes a rectangular matrix whose rows are the pieces, padded with spaces if necessary.

• '()'=/ compares every character in that matrix first with ( and then with ) returning a list of two 0-1 matrices.

• +.^:_1]0|: turns that list of two matrices into a single matrix of complex numbers. So far the program turns every ( in the input into a 1, every ) into i, and every other character into 0.

• b=.+/ assigns the sum of the rows of that complex matrix to b.

• -.|b makes a list of 1-|z| for every z in b. The condition that every column contain at most a single parenthesis translates to all these numbers 1-|z| being nonnegative.

• +/\*:b is the vector of running sums of the squares of the numbers in b. If every column does contain at most one parenthesis, the squares of the numbers in b are all 0, 1 or -1. The , concatenates this vector with the vector of 1-|z|'s.

• now all we need to do is test that the entries of our concatenated vector v are nonnegative reals numbers, this is almost */0<:v, except that that causes an error if some entries of v are not real, so we replace <: with <: ::0: which just returns 0 in case of error.