Ciągi topograficzne

23

Oto kilka przykładowych danych wejściowych, dzięki czemu mogę wyjaśnić, na czym polega problem:

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

Pomyśl o tym wierszu tekstu jako mapie topograficznej niektórych gór. Każdy zestaw nawiasów ilustruje jedną jednostkę wysokości.

Jeśli „zobaczymy” to z boku, aby zobaczyć góry pionowo, zobaczymy:

          4 5                cherries    woohoo  
  1 2  3       moo       lik          e
                      i

Biorąc pod uwagę jedną z tych map topograficznych, wypisz mapę, ale w skali pionowej, podobnie jak powyżej. Oddziel poszczególne elementy na mapie liczbą znaków do następnego elementu. Na przykład są 4 spacje na wyjściu między mooi i. Podobnie, na wejściu między mooi znajdują się 4 znaki i.

Wygrywa kod, który robi to w najmniejszej liczbie znaków.

beary605
źródło
Czy można bezpiecznie założyć, że wysokości zawsze będą dodatnie? Na przykład dane wejściowe ((1 2))))))))))3powinny być niepoprawne, jeśli zabronione są wysokości ujemne.
Cristian Lupascu,
@ w0lf: tak, nawiasy zawsze będą pasować.
beary605

Odpowiedzi:

10

J, 87 79 72 70 67 57 56 znaków

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

Pobiera dane z klawiatury. Przykład:

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

Wyjaśnienie:

To wyjaśnienie oparte jest na pierwszej wersji mojego programu:

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

x=.1!:1[1weź dane z klawiatury i włóż je na xpóźniej

(('('&([:+/=)-')'&([:+/=))\,.i.@#)tworzy listę wszystkich indeków w string ( i.@#) i scitches ( ,.) wraz z wynikiem (('('&([:+/=)-')'&([:+/=))\czasownika.

(('('&([:+/=)-')'&([:+/=))\Ten czasownik jest stosowana do wszystkich prefiksów napisu (tak na wejściu helloto dotyczy h, he, hel, hell, i hello. Jest to widelec , który zlicza liczbę otwartych nawiasie ('('&([:+/=), a następnie odejmuje liczby bliskich nawiasach ')'&([:+/=). To daje mi listy indeces do łańcucha i poziom, na którym znak w tym indeksie powinien znajdować się na wyjściu. Po prostym wprowadzeniu daje mi to:

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

((' '$~{.@]),[{~{:@])"1jest to czasownik, który pobiera listę, którą właśnie wygenerowałem, a także dane wyjściowe ('( ) 'charsub x)(które zastępuje ciąg znaków, aby zastąpić wszystkie nawiasy spacjami x). Bierze ogon każdego elementu listy {:@]i używa go jako indeksu w ciągu, aby uzyskać znak [{~{:@]. Następnie poprzedza ją ,liczbą spacji wskazaną przez nagłówek każdego elementu na liście (' '$~{.@]). W poprzednim przykładzie daje mi to:

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

 o
 n
 e

  t
  w
  o

   t
   h
   r
   e
   e

Następnie transponuję tablicę |:i odwracam ją, |.aby uzyskać pożądany wynik.

Gareth
źródło
6

GolfScript 69

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

Demo online tutaj .

Wyjaśnienie:

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
źródło
@Gareth Tak, oboje to robimy :)
Cristian Lupascu,
Chcesz dodać wyjaśnienie, jak to działa?
Timwi
@Timwi Zredagowałem swoją odpowiedź, aby uwzględnić wyjaśnienie
Cristian Lupascu,
5

APL (59)

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

Założyłem, że „baza” również musi być użyteczna. (tzn. (a(b))c(d)jest ważny). Jeśli nie jest to konieczne, można zapisać dwa znaki.

Wyjaśnienie:

  • T←⍞: zapisz wiersz wprowadzania w T
  • '()'∘=¨T: dla każdego znaku w T sprawdź, czy jest to nawias otwierający czy zamykający. To daje listę list boolean.
  • 1 ¯1∘ר: pomnóż drugi element na każdej z tych list przez -1 (więc nawias otwierający to 1, zamykający to -1, a każdy inny znak to 0).
  • +/¨: weź sumę każdej wewnętrznej listy. Mamy teraz wartość dla każdej postaci.
  • P←: przechowywać w P.
  • R←1++\P: weź bieżącą sumę P, podając wysokość każdej postaci. Dodaj po jednym do każdego znaku, aby znaki poza nawiasami znajdowały się w pierwszym wierszu.
  • (⍴T)∘⍴¨⍳⌈/R: dla każdej możliwej wartości y utwórz listę o długości T, składającą się tylko z tej wartości. (tj. 1111 ..., 2222 .... itd.)
  • R∘=¨: dla każdego elementu na tej liście sprawdź, czy jest on równy R. (Dla każdego poziomu mamy teraz listę zer i jedynek odpowiadających temu, czy postać powinna pojawiać się na tym poziomie).
  • ⍵×P=0: dla każdej z tych list ustaw ją na zero, jeśli P nie jest zero w tym miejscu. Pozbywa się to znaków o niezerowej delcie y, dzięki czemu pozbywamy się nawiasów.
  • ⊃,/T\¨⍨: dla każdej głębokości wybierz z T znaki, które powinny się pojawić.
  • ⊖↑: utwórz matrycę i umieść ją prawą stroną do góry.
marinus
źródło
Jakiej implementacji APL używasz? Czy to jest darmowe?
FUZxxl,
@FUZxxl Korzystam z APL Dyalog, wersję Windows można pobrać za darmo.
marinus
5

Tcl, 50

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

Niby oszukiwanie, ale cóż ...

Używam sekwencji ucieczki ascii, aby uzyskać różnicę linii, ^[[Aoznacza przesunięcie kursora o 1 linię w górę, ^[[Bprzesunięcie kursora o 1 linię w dół.

Johannes Kuhn
źródło
5

APL, 41 znaków / bajtów *

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

Testowane na Dyalog, z a ⎕IO←1i⎕ML←3 środowiskiem . Jest to funkcja, która pobiera wymagane dane wejściowe i zwraca dane wyjściowe. Biorąc pod uwagę treść pytania, uważam, że jest to do przyjęcia. Jeśli tak nie jest, oto wersja, która czyta ze standardowego wejścia i zapisuje na standardowe wyjście, dla 4 znaków więcej:

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

Objaśnienie :

{                                 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

Przykłady:

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 można zapisać w różnych starszych, jednobajtowych zestawach znaków, które odwzorowują symbole APL na górne 128 bajtów. Dlatego do celów gry w golfa program, który używa tylko znaków ASCII i symboli APL, może być oceniany jako znaki = bajty.

Tobia
źródło
Przeszukuję tutaj zestaw znaków APL i nie mogę znaleźć symbolu. To wygląda jak kombinacja znaków ¨i ~?
Gareth,
Cześć @Gareth Nie, nie było go w IBM APL2. Można go znaleźć w Dyalog (reklama, ale na ich stronie internetowej znajduje się wersja nagware, która jest wystarczająca do gry w golfa; IMHO najlepsza dostępna obecnie APL), Nars2000 (najlepsza APL open source), GNU APL i APL ngn , wśród inni
Tobia,
@Gareth Graficznie jest to kombinacja ~i ¨, chociaż jest to inna postać od obu. To operator o nazwie Commute . W swojej formie diadycznej to trzepie argumenty funkcji diadycznej to zastosowanie do: (5-2)=(2-⍨5). Jako operator monadycznej okazuje się dwójkowym funkcję w monadycznego, powielanie odpowiedniego argumentu (2*2)=(*⍨2). Najczęściej służy do pisania nieprzerwanego strumienia funkcji od prawej do lewej, bez konieczności umieszczania nawiasów wokół dużych wyrażeń i przeskakiwania wokół nich. W golfa jest to przydatne, ponieważ 3*⍨1-2jest o jeden char mniej niż (1-2)*3:-)
Tobia
2
Więc jest to odpowiednik ~w J wtedy.
Gareth,
3

J, 56 znaków

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

Kolejny 56-znakowy rozwiązanie J ... liczę głębokość tłumacząc (się ⁻1, )do 1 i wszystkie inne znaki na 0, a następnie biorąc działa sumę to: [: +/\ 1 _1 0 {~ '()'&i.. Reszta jest w dużej mierze podobna do rozwiązania @ Gareth.

Robaczek świętojański
źródło
2

Python, 161 znaków

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
źródło
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
źródło
2

Rubinowy 1.9 (129)

Czyta ze standardowego.

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
źródło
3
Miły! odkryłeś błąd w zakreślaczu Ruby :)
Cristian Lupascu,
Przetestowałem, a podświetlanie SQL działa lepiej dla twojego programu.
Cristian Lupascu,
@ w0lf ha, masz rację. Zmieniłem //do ''której zlicza postać taka sama i pozwala uniknąć błędów w wyróżnienia.
Paul Prestidge
2

C, 132 znaki

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

W opisie nie określono, ile danych wejściowych musi zaakceptować przesłanie, aby zostać zaakceptowanym, więc zdecydowałem się na limity, które były najbardziej zgodne z moimi potrzebami golfowymi (wciąż pracując z jednym podanym przykładem). Pozwólcie, że skorzystam z okazji, aby przypomnieć ludziom, że często dobrym pomysłem jest określenie minimów maksymalnych w opisach wyzwań.

W kodzie są dwie główne pętle. Pierwsza pętla farmuje wszystkie znaki niepozostawiające nawiasów w odpowiednim wierszu danych wyjściowych, a druga drukuje każdą linię.

chlebak
źródło
1

C, 149 znaków

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

uruchom z cytowanym arg, np. „((1 2) (3 (4 5) moo)) (i (lik (wiśnie) e (woohoo)))”

króliczek
źródło
0

Oktawa, 128

Bardzo podobny do mojej ostatniej odpowiedzi ...

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

Wkład: "((1 2)(3 (4 5) moo)) (i (lik(cherries)e (woohoo)))"

Wydajność:

          4 5 wiśni woohoo   
  1 2 3 moo lik e           
                      ja                           
sudo rm -rf slash
źródło
0

C #, 229 bajtów

Jeśli nie ma żadnych ograniczeń dotyczących wiodącej przestrzeni pionowej, możesz użyć tego (wcięcie dla przejrzystości.) Inicjuje kursor w dół o jedną linię dla każdego (znalezionego przed drukowaniem, a następnie przesuwa kursor w górę i w dół podczas odczytywania nawiasów.

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);
        }
    }
}
Hand-E-Food
źródło
0

PowerShell , 120 119 bajtów

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

Wypróbuj online!

Efekty uboczne: Znaki &i 'zmiany wysokości jak (i ), ale wyświetla. Porównaj wyniki dla:

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

Mniej golfa:

$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)
}
mazzy
źródło
-1

VB.net (dla S&G)

Nie najładniejszy kod.

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
źródło