# Topographic Strings

Here is some example input, so I can explain what the problem is:

((1 2)(3 (4 5) moo)) (i (lik(cherries)e (woohoo)))


Think of this line of text as a topographic map of some mountains. Each set of parentheses illustrates one unit of altitude.

If we "view" this from the side, so that we see the mountains vertically, we will see:

          4 5                cherries    woohoo
1 2  3       moo       lik          e
i


Given one of these topographic maps, output the map, but on a vertical scale, like the output above. Seperate the different items in the map with the number of characters to the next item. For example, there are 4 spaces in the output between moo and i. Likewise, there are 4 characters in the input between moo and i.

The code which does this in the least amount of characters wins.

• Is it safe to assume that heights will always be positive? For example, the input ((1 2))))))))))3 should be invalid if negative heights are forbidden. Jul 12 '12 at 13:53
• @w0lf: yep, the parentheses will always match up. Jul 12 '12 at 13:56

## J, 877972706757 56 characters

'( ) 'charsub|.|:(+/\@('('&=-')'&=)(],~' '$~[)"0])1!:1[1  Takes input from the keyboard. Example:  '( ) 'charsub|.|:(+/\@('('&=-')'&=)(],~' '$~[)"0])1!:1[1
((1 2)(3 (4 5) moo)) (i (lik(cherries)e (woohoo)))
4 5                cherries    woohoo
1 2  3       moo       lik          e
i


Explanation:

This explanation is based on the first version of my program:

|.|:('( ) 'charsub x)((' '$~{.@]),[{~{:@])"1(('('&([:+/=)-')'&([:+/=))\,.i.@#)x=.1!:1[1  x=.1!:1[1 take input from keyboard and put it into x for later (('('&([:+/=)-')'&([:+/=))\,.i.@#) creates a list of all indeces into the string (i.@#) and stitches (,.) it together with the result of the (('('&([:+/=)-')'&([:+/=))\ verb. (('('&([:+/=)-')'&([:+/=))\ this verb is applied to all the prefixes of the string (so on input hello it would apply to h,he,hel,hell, and hello. It is a fork, which counts the number of open brackets ('('&([:+/=) and then subtracts the number of close brackets ')'&([:+/=). This gives me list of indeces into the string and the level the character at that index should be at in the output. On simple input this gives me the following:  (('('&([:+/=)-')'&([:+/=))\,.i.@#)x=.1!:1[1 (one(two(three))) 1 0 1 1 1 2 1 3 2 4 2 5 2 6 2 7 3 8 3 9 3 10 3 11 3 12 3 13 2 14 1 15 0 16  ((' '$~{.@]),[{~{:@])"1 this is a verb which takes the list I just generated and also the output of ('( ) 'charsub x) (which just does a string replacement to replace all brackets with spaces in x). It takes the tail of each item of the list {:@] and uses it as an index into the string to get the character [{~{:@]. Then it prefixes it , with the number of spaces as indicated by the head of each item in the list(' '$~{.@]). On the previous example this gives me:  ('( ) 'charsub x)((' '$~{.@]),[{~{:@])"1(('('&([:+/=)-')'&([:+/=))\,.i.@#)x=.1!:1[1
(one(two(three)))

o
n
e

t
w
o

t
h
r
e
e


I then transpose the array |: and reverse it |. to get the desired output.

## GolfScript 69

0:§;{.'()'?))3%(.§+:§' ':s*\@s\if\n}%n/.{,}%$)\;:μ;{.,μ\-s*\+}%zip n*  Online demo here. Explanation: 0:§; # declare the variable §, representing the # current vertical level and initialize it at 0 { # iterate for each char in the string: .'()'?))3% ( # add on the stack the amount by which # the current vertical level should be # adjusted: # * +1 if the character is '(' # * -1 if the character is ')' # * 0 otherwise .§+:§ # adjust the value of § ' ':s* # add as many spaces as § tells us # and save the space in variable s \@s\if\ # return current char, if it's printable, # or a space if it's '(' or ')' n # add a newline char }% n/ # split by newline char; now we have # an array of strings on the stack. # Each string is a vertical line of the # final output. .{,}%$)\;:μ;        # Iterate through the strings and find the
# maximum length

{
.,μ\-s*\+       # Add spaces at the end to make all the strings
# the same length
}%

zip                 # Transpose the strings

n*                  # Join the transposed strings by newline characters

• @Gareth Yes, we both do :) Jul 13 '12 at 6:52
• Care to add an explanation how it works? Feb 9 '14 at 21:58
• @Timwi I've edited my answer to include an explanation Feb 10 '14 at 7:59

## APL (59)

⊖↑{⊃,/T\¨⍨⍵×P=0}¨R∘=¨(⍴T)∘⍴¨⍳⌈/R←1++\P←+/¨1 ¯1∘×¨'()'∘=¨T←⍞


I have assumed that the 'base' needs to be usable as well. (i.e. (a(b))c(d) is valid). If this is not necessary two characters can be saved.

Explanation:

• T←⍞: store a line of input in T
• '()'∘=¨T: for each character in T, see if it is an opening or closing parenthesis. This gives a list of lists of booleans.
• 1 ¯1∘×¨: multiply the second element in each of these lists by -1 (so an opening parenthesis is 1, a closing one is -1 and any other character is 0).
• +/¨: take the sum of each inner list. We now have the ∆y value for each character.
• P←: store in P.
• R←1++\P: take a running total of P, giving the height for each character. Add one to each character so that characters outside of the parentheses are on the first line.
• (⍴T)∘⍴¨⍳⌈/R: for each possible y-value, make a list as long as T, consisting of only that value. (i.e. 1111..., 2222...., etc.)
• R∘=¨: for each element in this list, see if it is equal to R. (For each level, we now have a list of zeroes and ones corresponding to whether or not a character should appear on that level).
• ⍵×P=0: for each of these lists, set it to zero if P is not zero at that spot. This gets rid of the characters with a non-zero delta-y, so that gets rid of the parentheses.
• ⊃,/T\¨⍨: for each depth, select from T the characters that should appear.
• ⊖↑: create a matrix and put it right-side-up.
• Which APL implementation are you using? Is it free? Jul 23 '12 at 8:35

puts \33\[9A[string map {( \33\[A ) \33\[B} $argv]  Kind of cheating, but well.. I use ascii escape sequences to get the line difference, ^[[A means move the curser 1 line up, ^[[B is move curser 1 line down. # APL, 41 chars/bytes* {⊖⍉⊃(↑∘''¨-⌿+/¨p∘.=,\⍵),¨⍵/⍨1-2×⍵∊p←'()'}  Tested on Dyalog, with a ⎕IO←1 and ⎕ML←3 environment. It's a function that takes the required input and returns the output. Given the question's wording, I believe it's acceptable. In case it's not, here is a version that reads from stdin and writes to stdout, for 4 chars more: ⍞←⊖⍉⊃(↑∘''¨-⌿+/¨'()'∘.=,\a),¨a/⍨1-2×'()'∊⍨a←⍞  Explanation: { p←'()'} p is the string made of two parentheses ⍵∊ ______ check which characters from ⍵ are parens 1-2× ________ -1 for every par., 1 for every other char ⍵/⍨ ____________ replace () with spaces in the orig. string ( ),¨ _______________ append every char to the following items ,\⍵ _____________________ for every prefix of the original string p∘.= ________________________ check which chars are '(' and which ')' +/¨ ____________________________ sum: compute the number of '(' and ')' -⌿ _______________________________ subtract the no. of ')' from that of '(' ↑∘''¨ _________________________________ generate as many spaces as that number ⊖⍉⊃ ____________________________________ make it into a table, transpose and flip  Examples: topo '((1 2)(3 (4 5) moo)) (i (lik(cherries)e (woohoo)))' 4 5 cherries woohoo 1 2 3 moo lik e i  topo 'a ( b ( c(d)e ) f ) g' d c e b f a g  *: APL can be saved in a variety of legacy single-byte charsets that map APL symbols to the upper 128 bytes. Therefore, for the purpose of golfing, a program that only uses ASCII characters and APL symbols can be scored as chars = bytes. • I'm searching the APL character set here and I can't find the ⍨ symbol. It looks like a combination of the ¨ and ~ characters? Feb 9 '14 at 22:22 • Hi @Gareth No, it was not in IBM APL2. You can find it in Dyalog (commercial, but there's a nagware version buried in their website, and that's good enough for golfing; IMHO the best APL available today), Nars2000 (best open source APL), GNU APL, and ngn's APL, among others. Feb 9 '14 at 22:46 • @Gareth Graphically it's the combination of ~ and ¨, although it's a different character from both. It's an operator called Commute. In its dyadic form it flips the arguments of the dyadic function it's applied to: (5-2)=(2-⍨5). As a monadic operator it turns a dyadic function into monadic, duplicating the right argument: (2*2)=(*⍨2). It's mostly used to write an uninterrupted stream of functions from right to left, without having to put parentheses around large expressions and jump your eyes around them. In golfing it's useful because 3*⍨1-2 is one char less than (1-2)*3 :-) Feb 9 '14 at 22:46 • So it's the equivalent of ~ in J then. Feb 9 '14 at 23:37 ## J, 56 chars '( ) 'charsub|.|:((,~#&' ')"0[:+/\1 _1 0{~'()'&i.)1!:1]1  Another 56-character J solution... I count depth by translating ( into ⁻1, ) into 1 and all other characters into 0, and then taking the running sum of this: [: +/\ 1 _1 0 {~ '()'&i.. The rest is largely similar to @Gareth's solution. ## Python, 161 chars S=raw_input() R=range(len(S)) H=[S[:i].count('(')-S[:i].count(')')for i in R]+[0] for h in range(max(H),0,-1):print''.join((' '+S[i])[H[i]==H[i+1]==h]for i in R)  # Python, 130 a=[""]*9 l=8 i=0 for c in raw_input():o=l;l+=c==')';l-=c=='(';a[l]=a[l].ljust(i)+c*(o==l);i+=1 print"\n".join(filter(str.strip,a))  ## Ruby 1.9 (129) Reads from stdin. l=0$><<gets.split('').map{|c|x=[?(]*99;x[l+=c==?(?-1:c==?)?1:0]=c;x}.transpose.map(&:join).*(?\n).tr('()',' ').gsub(/^\s+\n/,'')

• Nice! you discovered a bug in the Ruby highlighter :) Jul 12 '12 at 7:11
• I've tested and SQL highlighting works better for your program. Jul 12 '12 at 7:12
• @w0lf ha, you're right. I changed the // to '' which keeps the character count the same and avoids the bug in the highlighter. Jul 12 '12 at 22:25

## C, 132 characters

char*p,b[999];n;
main(m){for(p=gets(memset(b,32,999));*p;++p)*p-41?*p-40?p[n*99]=*p:++n>m?m=n:0:--n;
for(;m;puts(b+m--*99))p[m*99]=0;}


The description failed to specify how much input the submission had to accept in order to be accepted, so I settled on limits that were most consistent with my golfing needs (while still working with the one given example input). Allow me to take this opportunity to remind folks that it's often a good idea to specify minimum maximums in your challenge descriptions.

There are two main loops in the code. The first loop farms out all the non-parenthesis characters to the appropriate line of output, and the second loop prints each line.

# C, 149 chars

#define S for(i=0;c=v[1][i++];)h+=a=c-'('?c-')'?0:-1:1,
c,i,h=0,m=0;main(int a,char**v){S m=h>m?h:m;for(;m;m--){S putchar(a||h-m?32:c);putchar(10);}}


run with quoted arg, e.g. a.out "((1 2)(3 (4 5) moo)) (i (lik(cherries)e (woohoo)))"

# Octave, 128

Very similar to my last answer...

p=1;x=[0];y=input(0);for j=1:numel(y);p-=(y(j)==")");x(p,j)=y(j);p+=(y(j)=="(");end;x(x==40)=x(x==41)=x(x==0)=32;char(flipud(x))


### Test

Input: "((1 2)(3 (4 5) moo)) (i (lik(cherries)e (woohoo)))"

Output:

          4 5                cherries    woohoo
1 2  3       moo       lik          e
i


## C#, 229 bytes

If there's no restriction on leading vertical space, you can use this (indented for clarity.) It'll initialise the cursor down one line for every ( found before printing, then move the cursor up and down as brackets are read.

using C=System.Console;
class P{
static void Main(string[]a){
int l=a[0].Length,i=l;
while(i>0)
if(a[0][--i]=='(')C.CursorTop++;
while(++i<l){
char c=a[0][i];
if(c=='('){
c=' ';
C.CursorTop--;
}
if(c==')'){
c=' ';
C.CursorTop++;
}
C.Write(c);
}
}
}


# PowerShell, 120 119 bytes

(($h=($c=$args|% t*y)|%{($l+=(1,-1)[$_-40])})|sort)[-1]..0|%{$x=0;$y=$_
-join($c|%{"$_ "[$h[$x++]-ne$y-or$_-in40,41]})}


Try it online!

Side effects: Chars & and ' changes height as ( and ), but displays. Compare results for:

&$f "((1 2)(3 (4 5) moo)) (i (lik(cherries)e (woohoo)))" &$f "&&1 2'&3 &4 5' moo'' &i &lik&cherries'e &woohoo'''"


Less golfed:

$chars=$args|% toCharArray

$heights=$chars|%{
$level+=(1,-1)[$_-40]       # 40 is ASCII for '(', 41 is ASCII for ')'
$level }$maxHeight=($heights|sort)[-1]$maxHeight..0|%{
$x=0;$y=$_$line=$chars|%{ "$_ "[$heights[$x++]-ne$y -or$_-in40,41]
}
-join($line) }  # Charcoal, 14 bytes ＦＳ≡ι(«↘»)«↗»«ι  Try it online! Link is to verbose version of code. # AWK, 145 bytes x=split($0,a,b){for(;""!=e=a[++b];d+=(e=="(")-(e==")"))for(c=0;c++<x;f=f<d?d:f)z[c]=z[c](c==d?e=="("||e==")"?" ":e:" ")}END{for(;f;)print z[f--]}


Try it online!

This code takes advantage of the spacing rules of the contest, which makes it possible to process single characters and build up a set of output lines one character at time.

For each character in the input string, one character is appended to all the output lines. All but one line get   (space) characters. Only the line associated with the current topological height get a non-space character.

Here's a breakdown...

x=split(\$0,a,b){ ... }


The input line is split into a character array stored in a with the number of characters found saved in x.

for(;""!=e=a[++b];d+=(e=="(")-(e==")"))


The code block is one statement, a for loop with one statement, which is also a for loop. The outer loop just iterates over all the characters. The top of loop test ""!=e=a[++b] stores the current character in e to save some characters later.

The annoying ""!= check is needed to keep AWK from bailing if a 0 is included in the input...

The "end of loop" statement d+=(e=="(")-(e==")" increments and decrements the d topological depth indicator.

for(c=0;c++<x;f=f<d?d:f)


The inner for loop appends a character to all the output strings the code is assembling. It uses x (the number of characters in the input string) as the upper bound for the number of strings to construct since we don't know now many parenthesis are in the input. That's at least 2x too large, but the code is shorter if we just assemble lines that are never used.

The "end of loop" statement f=f<d?d:f just sets f to the maximum topological depth the code sees, which is used to figure out how many lines to print out later.

z[c]=z[c](c==d?e=="("||e==")"?" ":e:" ")


The body of the inner loop just appends a character to the current output string z[c]. The input character is appended only if the current line matches the topological depth, and the character isn't a paren.

END{for(;f;)print z[f--]}


One all the characters have been processed, the code just prints all the assembled lines up and including the largest topological depth reached while parsing the input.

## VB.net (For S&G)

Not the prettiest of code.

Module Q
Sub Main(a As String())
Dim t = a(0)
Dim h = 0
For Each m In (From G In (t.Select(Function(c)
h += If(c = "(", 1, If(c = ")", -1, 0))
Return h
End Function).Select(Function(y, i) New With {.y = y, .i = i}))
Group By G.y Into Group
Order By   y Descending
Select Group.ToDictionary(Function(x) x.i)
).Select(Function(d) New String(
t.Select(Function(c,i)If(d.ContainsKey(i),If(c="("c Or c=")"c," "c,c)," "c)).ToArray))
Console.WriteLine(m)
Next
End Sub
End Module