String Topografi

23

Berikut beberapa contoh input, jadi saya bisa menjelaskan apa masalahnya:

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

Pikirkan baris teks ini sebagai peta topografi beberapa gunung. Setiap rangkaian tanda kurung menggambarkan satu unit ketinggian.

Jika kita "melihat" ini dari samping, sehingga kita melihat gunung secara vertikal, kita akan melihat:

          4 5                cherries    woohoo  
  1 2  3       moo       lik          e
                      i

Diberikan salah satu peta topografi ini, output peta, tetapi pada skala vertikal, seperti output di atas. Pisahkan item yang berbeda di peta dengan jumlah karakter ke item berikutnya. Misalnya, ada 4 ruang dalam output antara moodan i. Demikian juga, ada 4 karakter dalam input antara moodan i.

Kode yang melakukan ini dalam jumlah karakter paling sedikit akan menang.

beary605
sumber
Apakah aman untuk mengasumsikan bahwa ketinggian akan selalu positif? Misalnya, input ((1 2))))))))))3harus tidak valid jika ketinggian negatif dilarang.
Cristian Lupascu
@ w0lf: ya, tanda kurung akan selalu cocok.
beary605

Jawaban:

10

J, 87 79 72 70 67 57 56 karakter

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

Mengambil input dari keyboard. Contoh:

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

Penjelasan:

Penjelasan ini didasarkan pada versi pertama dari program saya:

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

x=.1!:1[1 ambil input dari keyboard dan masukkan x untuk nanti

(('('&([:+/=)-')'&([:+/=))\,.i.@#)membuat daftar semua indeces ke dalam string ( i.@#) dan jahitan (,. ) bersamaan dengan hasil dari (('('&([:+/=)-')'&([:+/=))\kata kerja.

(('('&([:+/=)-')'&([:+/=))\kata kerja ini diterapkan untuk semua prefiks dari string (seterusnya masukan helloitu akan berlaku untuk h, he, hel, hell, dan hello. Ini adalah garpu , yang menghitung jumlah tanda kurung terbuka ('('&([:+/=)dan kemudian mengurangi jumlah kurung dekat ')'&([:+/=). Ini memberi saya daftar dari indeces ke dalam string dan level karakter pada indeks itu harus di dalam output.Pada input sederhana ini memberi saya hal berikut:

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

((' '$~{.@]),[{~{:@])"1ini adalah kata kerja yang mengambil daftar yang baru saja saya buat dan juga keluaran dari ('( ) 'charsub x)(yang hanya melakukan penggantian string untuk mengganti semua tanda kurung dengan spasi di x). Dibutuhkan ekor dari setiap item daftar {:@]dan menggunakannya sebagai indeks ke dalam string untuk mendapatkan karakter [{~{:@]. Lalu itu awalan itu, dengan jumlah spasi seperti yang ditunjukkan oleh kepala setiap item dalam daftar (' '$~{.@]). Pada contoh sebelumnya ini memberi saya:

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

 o
 n
 e

  t
  w
  o

   t
   h
   r
   e
   e

Saya kemudian memindahkan array |:dan membalikkannya |.untuk mendapatkan output yang diinginkan.

Gareth
sumber
6

GolfScript 69

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

Demo online di sini .

Penjelasan:

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
sumber
@ Gareth Ya, kami berdua melakukan :)
Cristian Lupascu
Ingin menambahkan penjelasan cara kerjanya?
Timwi
@Timwi Saya telah mengedit jawaban saya untuk menyertakan penjelasan
Cristian Lupascu
5

APL (59)

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

Saya berasumsi bahwa 'markas' harus dapat digunakan juga. (yaitu(a(b))c(d) valid). Jika ini tidak diperlukan, dua karakter dapat disimpan.

Penjelasan:

  • T←⍞: menyimpan sederetan input di T
  • '()'∘=¨T: untuk setiap karakter dalam T, lihat apakah itu tanda kurung buka atau tutup. Ini memberikan daftar daftar boolean.
  • 1 ¯1∘ר: kalikan elemen kedua di masing-masing daftar ini dengan -1 (jadi tanda kurung pembuka adalah 1, yang penutup adalah -1 dan karakter lainnya adalah 0).
  • +/¨: ambil jumlah setiap daftar bagian dalam. Kami sekarang memiliki nilai fory untuk setiap karakter.
  • P←: simpan di P.
  • R←1++\P: ambil total P yang berjalan, berikan ketinggian untuk setiap karakter. Tambahkan satu ke setiap karakter sehingga karakter di luar tanda kurung ada di baris pertama.
  • (⍴T)∘⍴¨⍳⌈/R: untuk setiap kemungkinan nilai-y, buat daftar selama T, yang hanya terdiri dari nilai itu. (mis. 1111 ..., 2222 ...., dll.)
  • R∘=¨: untuk setiap elemen dalam daftar ini, lihat apakah itu sama dengan R. (Untuk setiap level, kami sekarang memiliki daftar nol dan yang sesuai dengan apakah karakter akan muncul pada level itu atau tidak).
  • ⍵×P=0: untuk masing-masing daftar ini, setel ke nol jika P tidak nol di tempat itu. Ini menghilangkan karakter dengan delta-y yang tidak nol, sehingga menghilangkan tanda kurung.
  • ⊃,/T\¨⍨: untuk setiap kedalaman, pilih dari T karakter yang akan muncul.
  • ⊖↑: buat matriks dan letakkan di sisi atas.
marinus
sumber
Implementasi APL mana yang Anda gunakan? Ini gratis?
FUZxxl
@FUZxxl Saya sudah menggunakan Dyalog APL, versi Windows dapat diunduh secara gratis.
marinus
5

Tcl, 50

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

Agak curang, tapi yah ..

Saya menggunakan urutan melarikan diri ascii untuk mendapatkan perbedaan garis, ^[[Aberarti memindahkan kursor 1 ke atas, ^[[Badalah memindahkan kursor 1 ke bawah.

Johannes Kuhn
sumber
5

APL, 41 karakter / byte *

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

Diuji pada Dyalog, dengan a ⎕IO←1dan ⎕ML←3lingkungan. Ini adalah fungsi yang mengambil input yang diperlukan dan mengembalikan output. Mengingat kata-kata pertanyaan itu, saya percaya itu dapat diterima. Jika tidak, berikut adalah versi yang membaca dari stdin dan menulis ke stdout, untuk 4 karakter lainnya:

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

Penjelasan :

{                                 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

Contoh:

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 dapat disimpan dalam berbagai rangkaian karakter byte tunggal sebelumnya yang memetakan simbol APL ke 128 byte atas. Oleh karena itu, untuk tujuan bermain golf, program yang hanya menggunakan karakter ASCII dan simbol APL dapat dinilai sebagai karakter = byte.

Tobia
sumber
Saya mencari karakter APL yang ditetapkan di sini dan saya tidak dapat menemukan simbolnya. Sepertinya kombinasi dari ¨dan ~karakter?
Gareth
Hai @Gareth Tidak, itu bukan di IBM APL2. Anda dapat menemukannya di Dyalog (komersial, tetapi ada versi nagware yang terkubur di situs web mereka, dan itu cukup bagus untuk bermain golf; IMHO APL terbaik yang tersedia saat ini), Nars2000 (APL sumber terbuka terbaik), GNU APL , dan APL ngn , di antara lainnya.
Tobia
@ Gareth Secara grafis itu adalah kombinasi dari ~dan ¨, meskipun itu karakter yang berbeda dari keduanya. Ini operator yang disebut Commute . Dalam bentuk diad itu membalik argumen dari fungsi dyadic itu diterapkan: (5-2)=(2-⍨5). Sebagai operator monadik ternyata fungsi diad ke monadik, menduplikasi argumen yang tepat: (2*2)=(*⍨2). Ini sebagian besar digunakan untuk menulis aliran fungsi yang tidak terputus dari kanan ke kiri, tanpa harus meletakkan tanda kurung di sekitar ekspresi besar dan melompat-lompat mata Anda di sekitar mereka. Dalam bermain golf itu berguna karena 3*⍨1-2satu karakter kurang dari (1-2)*3:-)
Tobia
2
Jadi itu setara dengan ~di J lalu.
Gareth
3

J, 56 karakter

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

56-karakter solusi J lain ... saya menghitung kedalaman dengan menerjemahkan (ke dalam ⁻1, )menjadi 1 dan semua karakter lain ke 0, dan kemudian mengambil jumlah yang menjalankan ini: [: +/\ 1 _1 0 {~ '()'&i.. Sisanya sebagian besar mirip dengan solusi @ Gareth.

FireFly
sumber
2

Python, 161 karakter

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
sumber
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
sumber
2

Ruby 1.9 (129)

Baca dari 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
sumber
3
Bagus! Anda menemukan bug di Ruby highlighter :)
Cristian Lupascu
Saya telah menguji dan menyoroti SQL berfungsi lebih baik untuk program Anda.
Cristian Lupascu
@ w0lf ha, Anda benar. Saya mengubah// ke ''yang menjaga karakter menghitung yang sama dan menghindari bug di stabilo.
Paul Prestidge
2

C, 132 karakter

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

Deskripsi gagal menentukan berapa banyak input yang harus diterima oleh kiriman agar dapat diterima, jadi saya menetapkan batas yang paling konsisten dengan kebutuhan golf saya (sambil tetap bekerja dengan satu contoh input yang diberikan). Izinkan saya mengambil kesempatan ini untuk mengingatkan orang-orang bahwa sering kali merupakan ide yang baik untuk menentukan maksimum minimum dalam deskripsi tantangan Anda.

Ada dua loop utama dalam kode. Loop pertama menghasilkan semua karakter non-kurung ke baris output yang sesuai, dan loop kedua mencetak setiap baris.

kotak roti
sumber
1

C, 149 karakter

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

jalankan dengan arg yang dikutip, egaout "((1 2) (3 (4 5) moo))) (i (lik (ceri) e (woohoo))))"

bayi-kelinci
sumber
0

Oktaf, 128

Sangat mirip dengan jawaban terakhir saya ...

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

Uji

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

Keluaran:

          4 5 ceri woohoo   
  1 2 3 moo lik e           
                      saya                           
sudo rm -rf slash
sumber
0

C #, 229 byte

Jika tidak ada batasan untuk memimpin ruang vertikal, Anda dapat menggunakan ini (indentasi untuk kejelasan). Ini akan menginisialisasi kursor satu baris untuk setiap yang (ditemukan sebelum mencetak, kemudian gerakkan kursor ke atas dan ke bawah saat tanda kurung dibaca.

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);
        }
    }
}
Makanan Tangan
sumber
0

PowerShell , 120 119 byte

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

Cobalah online!

Efek samping: Karakter &dan 'perubahan ketinggian sebagai (dan ), tetapi ditampilkan. Bandingkan hasil untuk:

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

Kurang bermain golf:

$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
sumber
-1

VB.net (Untuk S&G)

Bukan kode tercantik.

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
sumber