Adapted from
http://www.jsoftware.com/pipermail/general/2008-July/032128.html
rparen=: 4 : 0
s=. /:~ x,y
d=. (~: }:"1@(0&,.)) (i.@(>./) </ ]) +/\ _1^s e. y
p=. d#&,(#d)#,:s
b=. ($p)$1 0
((b#p) i. x){(-.b)#p
)
x=: 12 34 36 47 70
y=: 30 44 54 59 82
x rparen y
30 59 44 54 82
(x,x+1e7) rparen y,y+1e7
30 59 44 54 82 10000030 10000059 10000044 10000054 10000082
This is quadratic in #x whereas there is a linear
(but looping) solution.
----- Original Message -----
From: Raul Miller <[email protected]>
Date: Thursday, March 25, 2010 11:40
Subject: [Jprogramming] parenthesis balancing
To: Programming forum <[email protected]>
> Does anyone remember how to efficiently solve problems like this:
>
> (I think we have solved similar issues in the past, but I am not
> finding the relevant messages.)
>
> Given a list of positions for left and right parenthesis, arranged
> in ascending order:
>
> 12 34 36 47 70
> 30 44 54 59 82
>
> Return the positions for the right parenthesis arranged to correspond
> with their matching left parenthesis.
>
> 30 59 44 54 82
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
