Cordas topográficas

23

Aqui está um exemplo de entrada, para que eu possa explicar qual é o problema:

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

Pense nessa linha de texto como um mapa topográfico de algumas montanhas. Cada conjunto de parênteses ilustra uma unidade de altitude.

Se "visualizarmos" isso de lado, para vermos as montanhas verticalmente, veremos:

          4 5                cherries    woohoo  
  1 2  3       moo       lik          e
                      i

Dado um desses mapas topográficos, produza o mapa, mas em uma escala vertical, como a produção acima. Separe os diferentes itens no mapa com o número de caracteres para o próximo item. Por exemplo, existem 4 espaços na saída entre mooe i. Da mesma forma, existem 4 caracteres na entrada entre mooe i.

O código que faz isso na menor quantidade de caracteres vence.

beary605
fonte
É seguro assumir que as alturas sempre serão positivas? Por exemplo, a entrada ((1 2))))))))))3deve ser inválida se alturas negativas forem proibidas.
Cristian Lupascu
@ w0lf: sim, os parênteses sempre coincidem.
beary605

Respostas:

10

J, 87 79 72 70 67 57 56 caracteres

'( ) 'charsub|.|:(+/\@('('&=-')'&=)(],~' '$~[)"0])1!:1[1

Recebe entrada do teclado. Exemplo:

   '( ) '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

Explicação:

Esta explicação é baseada na primeira versão do meu programa:

|.|:('( ) 'charsub x)((' '$~{.@]),[{~{:@])"1(('('&([:+/=)-')'&([:+/=))\,.i.@#)x=.1!:1[1

x=.1!:1[1pegue a entrada do teclado e coloque-a xpara mais tarde

(('('&([:+/=)-')'&([:+/=))\,.i.@#)cria uma lista de todos os indeces na string ( i.@#) e costura ( ,.) junto com o resultado do (('('&([:+/=)-')'&([:+/=))\verbo.

(('('&([:+/=)-')'&([:+/=))\este verbo é aplicado a todos os prefixos do string (assim por diante entrada helloseria aplicável para h, he, hel, hell, e hello. É um garfo , que conta o número de suportes abertos ('('&([:+/=)e, em seguida, subtrai o número de suportes de perto ')'&([:+/=). Isso me dá lista de indeces na string e no nível em que o caractere nesse índice deve estar na saída.Em entradas simples, isso me dá o seguinte:

   (('('&([:+/=)-')'&([:+/=))\,.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

((' '$~{.@]),[{~{:@])"1este é um verbo que pega a lista que acabei de gerar e também a saída de ('( ) 'charsub x)(que apenas substitui uma string para substituir todos os colchetes por espaços x). Ele pega o final de cada item da lista {:@]e o usa como um índice na string para obter o caractere [{~{:@]. Em seguida, o prefixa ,com o número de espaços, conforme indicado pelo cabeçalho de cada item na lista (' '$~{.@]). No exemplo anterior, isso me dá:

   ('( ) 'charsub x)((' '$~{.@]),[{~{:@])"1(('('&([:+/=)-')'&([:+/=))\,.i.@#)x=.1!:1[1
(one(two(three)))

 o
 n
 e

  t
  w
  o

   t
   h
   r
   e
   e

Transponho a matriz |:e a inverto |.para obter a saída desejada.

Gareth
fonte
6

GolfScript 69

0:§;{.'()'?))3%(.§+:§' ':s*\@s\if\n}%n/.{,}%$)\;:μ;{.,μ\-s*\+}%zip n*

Demonstração online aqui .

Explicação:

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
Cristian Lupascu
fonte
@Gareth Sim, nós dois fazer :)
Cristian Lupascu
Gostaria de adicionar uma explicação de como funciona?
Timwi
@ Timwi Eu editei minha resposta para incluir uma explicação #
Cristian Lupascu
5

APL (59)

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

Eu assumi que a 'base' precisa ser utilizável também. (ou seja, (a(b))c(d)é válido). Se isso não for necessário, dois caracteres podem ser salvos.

Explicação:

  • T←⍞: armazena uma linha de entrada em T
  • '()'∘=¨T: para cada caractere em T, veja se é um parêntese de abertura ou fechamento. Isso fornece uma lista de listas de booleanos.
  • 1 ¯1∘ר: multiplique o segundo elemento em cada uma dessas listas por -1 (para que um parêntese de abertura seja 1, um parêntese de fechamento seja -1 e qualquer outro caractere seja 0).
  • +/¨: pegue a soma de cada lista interna. Agora temos o valor y para cada personagem.
  • P←: loja em P.
  • R←1++\P: pegue um total de P, dando a altura para cada personagem. Adicione um a cada caractere para que caracteres fora dos parênteses fiquem na primeira linha.
  • (⍴T)∘⍴¨⍳⌈/R: para cada valor y possível, faça uma lista contanto que T, consistindo apenas nesse valor. (ou seja, 1111 ..., 2222 ...., etc.)
  • R∘=¨: para cada elemento nesta lista, veja se é igual a R. (para cada nível, agora temos uma lista de zeros e zeros correspondentes a se um caractere deve ou não aparecer nesse nível).
  • ⍵×P=0: para cada uma dessas listas, defina como zero se P não for zero nesse local. Isso elimina os caracteres com um delta-y diferente de zero, de modo que elimina os parênteses.
  • ⊃,/T\¨⍨: para cada profundidade, selecione T os caracteres que devem aparecer.
  • ⊖↑: crie uma matriz e coloque-a com o lado direito para cima.
marinus
fonte
Qual implementação de APL você está usando? É de graça?
FUZxxl 23/07/12
@FUZxxl Estou usando o Dyalog APL, a versão do Windows pode ser baixada gratuitamente.
Marinus
5

Tcl, 50

puts \33\[9A[string map {( \33\[A ) \33\[B} $argv]

Tipo de trapaça, mas bem ..

Eu uso seqüências de escape ascii para obter a diferença de linha, ^[[Asignifica mover o cursor 1 linha para cima, ^[[Bé mover o cursor 1 linha para baixo.

Johannes Kuhn
fonte
5

APL, 41 caracteres / bytes *

{⊖⍉⊃(↑∘''¨-⌿+/¨p∘.=,\⍵),¨⍵/⍨1-2×⍵∊p←'()'}

Testado em Dyalog, com um ambiente ⎕IO←1e ⎕ML←3. É uma função que pega a entrada necessária e retorna a saída. Dada a redação da pergunta, acredito que seja aceitável. Caso contrário, aqui está uma versão que lê de stdin e grava em stdout, por 4 caracteres a mais:

⍞←⊖⍉⊃(↑∘''¨-⌿+/¨'()'∘.=,\a),¨a/⍨1-2×'()'∊⍨a←⍞

Explicação :

{                                 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

Exemplos:

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

*: O APL pode ser salvo em uma variedade de conjuntos de caracteres de byte herdados que mapeiam os símbolos do APL para os 128 bytes superiores. Portanto, para fins de golfe, um programa que usa apenas caracteres ASCII e símbolos APL pode ser pontuado como chars = bytes.

Tobia
fonte
Estou pesquisando o conjunto de caracteres APL aqui e não consigo encontrar o símbolo. Parece uma combinação dos caracteres ¨e ~?
Gareth
Oi @Gareth Não, não estava no IBM APL2. Você pode encontrá-lo em Dyalog (comercial, mas há uma versão nagware enterrada em seu site, e isso é bom o suficiente para jogar golfe; IMHO é a melhor APL disponível hoje), Nars2000 (melhor APL de código aberto), GNU APL e APN da ngn , entre outras.
Tobia
@Gareth Graficamente é a combinação de ~e ¨, embora seja um personagem diferente de ambos. É um operador chamado Comutar . Na sua forma dyadic ele inverte os argumentos da função diádica é aplicada a: (5-2)=(2-⍨5). Como um operador monádico verifica-se uma função dyadic em monádico, duplicando o argumento direita: (2*2)=(*⍨2). É usado principalmente para escrever um fluxo ininterrupto de funções da direita para a esquerda, sem ter que colocar parênteses em torno de grandes expressões e pular os olhos em torno delas. Em golfe é porque útil 3*⍨1-2é um carvão animal inferior a (1-2)*3:-)
Tobia
2
Então é o equivalente ~em J então.
Gareth
3

J, 56 caracteres

'( ) 'charsub|.|:((,~#&' ')"0[:+/\1 _1 0{~'()'&i.)1!:1]1

Outra solução J 56 personagens ... Eu conto profundidade, traduzindo (em ⁻1, )em 1 e todos os outros personagens em 0, e em seguida, tomando a soma de execução deste: [: +/\ 1 _1 0 {~ '()'&i.. O resto é amplamente semelhante à solução de @ Gareth.

FireFly
fonte
2

Python, 161 caracteres

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)
Keith Randall
fonte
2

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))
grc
fonte
2

Rubi 1.9 (129)

Lê de 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/,'')
Paul Prestidge
fonte
3
Agradável! você descobriu um bug no marcador rubi :)
Cristian Lupascu
Eu testei e o destaque do SQL funciona melhor para o seu programa.
Cristian Lupascu
@ w0lf ha, você está certo. Mudei //para o ''que mantém a contagem de caracteres igual e evita o erro no marcador.
Paul Prestidge 12/07/2012
2

C, 132 caracteres

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

A descrição falhou ao especificar quanta entrada a submissão tinha que aceitar para ser aceita, então estabeleci limites que eram mais consistentes com minhas necessidades de golfe (enquanto ainda trabalhava com uma entrada de exemplo). Permita-me aproveitar esta oportunidade para lembrar às pessoas que geralmente é uma boa idéia especificar máximos mínimos nas descrições dos seus desafios.

Existem dois loops principais no código. O primeiro loop gera todos os caracteres que não estão entre parênteses na linha de saída apropriada e o segundo loop imprime cada linha.

caixa de pão
fonte
1

C, 149 caracteres

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

executar com arg citado, egaout "((1 2) (3 (4 5) meses)) (i (lik (cerejas) e (woohoo)))"

coelho bebê
fonte
0

Oitava, 128

Muito parecido com a minha última resposta ...

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))

Teste

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

Saída:

          4 5 cerejas woohoo   
  1 2 3 meses atrás           
                      Eu                           
barra sudo rm -rf
fonte
0

C #, 229 bytes

Se não houver restrição no espaço vertical inicial, você poderá usar isso (recuado para maior clareza.) Inicializará o cursor uma linha abaixo para cada (encontrado antes da impressão e, em seguida, moverá o cursor para cima e para baixo à medida que os colchetes forem lidos.

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);
        }
    }
}
Mão-E-Comida
fonte
0

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]})}

Experimente online!

Efeitos colaterais: Chars & e 'altera a altura como (e ), mas é exibida. Compare resultados para:

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

Menos golfe:

$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)
}
confuso
fonte
-1

VB.net (para S&G)

Não é o código mais bonito.

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
Adam Speight
fonte