Kurung Saling Bertautan

30

Tulis program atau fungsi yang menggunakan string delapan byte yang berisi salah satu dari masing-masing karakter yang ()[]{}<>disusun sedemikian rupa sehingga empat jenis braket yang cocok. Misalnya, ]<([){}>input tidak valid karena tanda kurung tidak cocok (meskipun semua yang lain).

Cetak atau kembalikan integer dari 0ke 6yang menunjukkan berapa banyak dari enam pasangan yang mungkin dari keempat jenis braket yang saling terkait. Pasangan jenis braket dianggap saling terkait jika tepat satu braket dari satu jenis terjadi di antara braket dari jenis lainnya. Jadi ([)]dan [(])yang saling bertautan tetapi ()[], [](), ([]), dan [()]tidak.

Kode terpendek dalam byte menang.

Contoh Input / Output

()[]{}<> : 0
([{<>}]) : 0
<>{[]}() : 0
{<>([])} : 0
<(>)[{}] : 1
<[({)}]> : 1
[{<}]>() : 2
{<>([}]) : 2
<{(>})[] : 3
[(]<){>} : 3
<([>{)}] : 4
(<{[>})] : 4
(<[{)>}] : 5
<{[(>})] : 5
[{<(]}>) : 6
(<{[)>}] : 6
Hobi Calvin
sumber

Jawaban:

17

CJam, 18

l7~f&_f{\/~;&}s,2/

Terima kasih isaacg untuk beberapa ide bermain golf :)
Cobalah online atau coba semua contoh

Penjelasan:

l         read a line of input
7~f&      clear the lowest 3 bits of each character
           the goal is to convert brackets of the same type to the same char
_         duplicate the resulting string, let's call it S
f{…}      for each character in S, and S (the char and S are pushed every time)
  \       swap the character with S
  /       split S around that character, resulting in 3 pieces:
           before, between, after
  ~       dump the pieces on the stack
  ;       pop the last piece
  &       intersect the first 2 pieces
          after the loop, we have an array of strings
          containing the chars interlocking to the left with each char of S
s         join all the string into one string
,         get the string length
2/        divide by 2, because S has duplicated characters
aditsu
sumber
1
Oh, jadi kaulah yang menciptakan CJam ?? Anda berutang pada saya untuk semua jawaban yang saya hilangkan yang dikalahkan oleh jawaban CJam! ;)
kirbyfan64sos
6
@ kirbyfan64sos baik, Anda sebaiknya mulai mempelajarinya juga jika Anda ingin menang :)
aditsu
9
7~f&? Saya sudah menyukai jawaban ini, dan saya bahkan belum membaca sisanya.
Dennis
11

Python 2, 163 byte

def f(b,e='([{<)]}>',q=range(4)):
 b=[b[b.index(e[j])+1:b.index(e[j+4])]for j in q]
 print sum(sum(abs(b[k].count(e[j])-b[k].count(e[j+4]))for j in q)for k in q)/2

Ini terlihat pada hal-hal di antara masing-masing pasangan kurung yang cocok dan menghitung jumlah kurung kiri atau kanan yang ada. Jumlah ini dibagi dua adalah output.

Saya yakin itu bisa lebih banyak golf dengan pegolf yang lebih baik dari saya.

Hobi Calvin
sumber
31
Yah, itu terjadi. Calvin memposting sebuah jawaban. Akhir zaman ada pada kita.
Alex A.
4

GNU sed -r, 147

Keluaran tidak sesuai dengan meta-jawaban ini .

y/([{</)]}>/
s/.*/\t& & & & /
:b
y/)]}>/]}>)/
s/\S*>(\S*)>\S* /\1\t/
t
s/\S* //
:
s/(\t\S*)(\S)(\S*)\2(\S*\t)/\1\3\4/
t
s/\S *$/&/
tb
s/\s//g
s/../1/g

Catatan: Ganti \tdengan tabkarakter aktual untuk mendapatkan skor yang benar. Namun, program ini akan bekerja baik dengan GNU sed.

Cobalah online .

Trauma Digital
sumber
3

Perl, 77 byte

76 kode + 1 sakelar

perl -pe 'y/)]}>/([{</;for$x(/./g){$h{$x="\\$x"}++&&s!$x(.*)$x!$z+=length$1,$1!e}$_=$z'

Mengambil input dari STDIN dan program harus dimulai baru untuk setiap input.

Penjelasan

  1. Ganti semua tanda kurung tutup dengan mitra terbuka mereka ( y/.../.../).
  2. Kemudian, untuk setiap karakter dalam string input ( for$x...), tambahkan penghitung untuk karakter ( $h{$x}++).
  3. Jika ini adalah kedua kalinya kita melihat karakter, dapatkan jarak antara dua kejadian ( length $1) dan hapus kedua kejadian karakter ini dari string. Misalnya, jika string itu ([{([{<<, ada dua karakter [dan di {antara keduanya (. Setelah (s diproses, string menjadi [{[{<<dan kami menambahkan 2 ke jumlah total ( $z) tanda kurung yang saling terkait.
  4. Hasilnya diambil dari $z( $_=$z)
svsd
sumber
3

Pyth, 20 byte

JmC/CdTzlsm@FPcsJd{J

Suite uji

JmC/CdTz: Pertama, ini mengonversi setiap pasangan simbol ke satu karakter dengan memetakan setiap karakter input ke kode karakternya ( Cd) dibagi 10 ( / T), yang sama untuk setiap pasangan tetapi berbeda di antara semua pasangan. Angka yang dihasilkan dikonversi kembali menjadi karakter untuk tujuan yang akan diungkapkan kemudian ( C). Daftar karakter yang dihasilkan disimpan ke J.

lsm@FPcsJd{J: Sekarang, kami memetakan karakter unik di J( {J). Kita mulai dengan memotong string yang dibentuk dengan menggabungkan Jmenggunakan karakter saat ini sebagai delimeter ( csJd). Sepasang kurung tumpang tindih dengan pasangan saat ini jika muncul di grup kedua dan grup pertama atau ketiga. Untuk menghindari penghitungan ganda, kami hanya akan menghitung case grup pertama dan kedua. Jadi, kami menghapus grup ketiga ( P) dan mengambil persimpangan grup yang tersisa ( @F). Akhirnya, kami menggabungkan karakter yang tumpang tindih ( s) dan mencetak panjang resut ( l).

isaacg
sumber
3

Python 3, 107

t=0
s=""
for x in input():s+=chr(ord(x)&~7)
for x in s:a=s.split(x);t+=len(set(a[0])&set(a[1]))
print(t//2)

Secara longgar didasarkan pada solusi CJam saya.

aditsu
sumber
3

Retina , 128 108 64 62 55 byte

(T`)]>}`([<{
(\D)(.*)\1(.*)
\n$2\n$3
(?=(\D).*\n.*\1)
1
\n
<empty>

Dimana <empty>mewakili garis trailing kosong. Untuk tujuan penghitungan, letakkan setiap baris dalam file terpisah, dan ganti \ndengan karakter linefeed yang sebenarnya. Untuk kenyamanan, Anda dapat menggunakan kode setara ini dengan -standa dari satu file:

(T`)]>}`([<{
(\D)(.*)\1(.*)
#$2#$3
(?=(\D)[^#]*#[^#]*\1)
1
#
<empty>

Outputnya unary .

Penjelasan

Yang pertama (memberitahu Retina untuk mengeksekusi seluruh kode dalam satu lingkaran sampai iterasi berhenti mengubah string. Dalam hal ini, itu akan selalu diulang empat kali, satu kali untuk setiap jenis braket.

T`)]>}`([<{

Ini hanya mengubah setiap braket penutup menjadi braket pembuka yang sesuai, sehingga kita dapat mencocokkan braket yang sesuai dengan referensi balik sederhana nanti. (Tahap ini menjadi no-op setelah iterasi pertama. Ini hanya termasuk dalam loop, karena Tsudah memerlukan backtick, jadi menambahkan (biaya hanya satu, bukan dua byte.)

(\D)(.*)\1(.*)
\n$2\n$3

Ini menggantikan pasangan kurung paling kiri dengan baris baru. Kita gunakan\D untuk membedakan tanda kurung dari tanda kurung yang 1kita tambahkan nanti dalam loop untuk penghitungan. The (.*)di akhir memastikan bahwa hanya satu pasangan yang diganti (karena pertandingan tidak dapat tumpang tindih).

(?=(\D).*\n.*\1)
1

Seluruh regex berada dalam lookahead, jadi ini cocok dengan posisi . Lebih khusus itu cocok dengan satu posisi untuk setiap pasangan tanda kurung yang telah dipisahkan oleh tanda kurung lain kami baru saja berubah menjadi baris baru. SEBUAH1 dimasukkan ke dalam masing-masing posisi ini. Kita bisa membiarkan saja 1di sana, karena mereka tidak mempengaruhi regex yang lain (karena dia \Dmemastikan bahwa kita tidak cocok dengan mereka secara tidak sengaja).

\n
<empty>

Akhirnya, kami menghapus baris baru (yaitu placeholder untuk jenis kurung saat ini) - ini berarti bahwa kami telah mengurangi masalah yang tersisa menjadi string dengan panjang 6 yang hanya berisi 3 jenis tanda kurung, tetapi jika tidak, kerjanya sama persis.

Pada akhirnya, hanya huruf 1s yang kami masukkan akan ditinggalkan, dan jumlahnya sesuai dengan jumlah tanda kurung yang saling terkait.

Martin Ender
sumber
2

JavaScript (ES7), 121 117 byte

x=>(a=b=0,[for(c of x)for(d of'1234')(e=c.charCodeAt()/26|0)==d?a^=1<<d:b^=(a>>d&1)<<d*4+e],f=y=>y&&y%2+f(y>>1))(b)/2

Wow. Itu tadi menyenangkan. Saya membuat sketsa ide jawaban ketika tantangan ini pertama kali keluar, tetapi panjangnya lebih dari 150 byte dan saya tidak ingin melakukan upaya untuk golf itu. Saya menemukan ide ini di notebook saya kemarin dan memutuskan saya tidak akan berhenti memikirkannya sampai saya benar-benar bermain golf. Saya akhirnya menulis dua algoritma yang sama sekali baru, yang pertama berakhir dengan beberapa byte lebih pendek setelah bermain golf sekitar 25 byte dengan banyak bit-hacking.

Bagaimana itu bekerja

Pertama kita atur variabel adan bke 0. aadalah array biner 4-bit di mana pasangan braket saat ini kita berada di dalam, danb merupakan array biner 16-bit di mana pasangan braket dihubungkan bersama.

Selanjutnya, kita mengulang setiap karakter cdi x, dan setiap karakter ddi '0123'. Pertama kita menentukan jenis bracket cadalah dengan e=c.charCodeAt()/26-1|0. Kode karakter desimal masing-masing jenis braket adalah sebagai berikut:

() => 40,41
<> => 60,62
[] => 91,93
{} => 123,125

Dengan membaginya dengan 26, mengurangi 1, dan lantai, kami memetakan ini masing-masing menjadi 0, 1, 2, dan 3.

Selanjutnya kita periksa apakah angka ini sama dengan nilai saat ini d. Jika ya, kita baik masuk atau keluar dth jenis bracket, jadi kami membalik dbit th di adengan a^=1<<d. Jika tidak, tetapi kita berada di dalam dtipe braket th, kita perlu membalik ebit dke-4 di bagian 4-bit b. Ini dilakukan seperti ini:

b^=(a>>d&1)<<d*4+e

(a>>d&1)Mengembalikan dbit ke dalam a. Jika kita berada di dalam dtipe braket th, ini mengembalikan 1; jika tidak, ia mengembalikan 0. Selanjutnya, kita menggeser ini ditinggalkan oleh d*4+ebit, dan XOR boleh hasilnya. Jika kita berada di dalam dtipe braket th, ini XOR d*4+ebit th b; jika tidak, ia tidak melakukan apa-apa.

Di akhir semua perulangan, bakan berisi sejumlah 1-bit sama dengan dua kali nilai pengembalian yang diinginkan. Tetapi kita masih perlu mencari tahu berapa banyak bit ini. Di situlah sub-fungsi fmasuk:

f=y=>y&&y%2+f(y>>1)

Jika y0, ini hanya mengembalikan 0. Jika tidak, dibutuhkan bit terakhir ydengan y%2, lalu menambahkan hasil menjalankan semua kecuali bit terakhir ymelalui fungsi lagi. Sebagai contoh:

f(y)         => y && y%2 + f(y>>1)
f(0b1001101) =>       1  + f(0b100110) = 4
f(0b100110)  =>       0  + f(0b10011)  = 3
f(0b10011)   =>       1  + f(0b1001)   = 3
f(0b1001)    =>       1  + f(0b100)    = 2
f(0b100)     =>       0  + f(0b10)     = 1
f(0b10)      =>       0  + f(0b1)      = 1
f(0b1)       =>       1  + f(0b0)      = 1
f(0b0)       => 0                      = 0

Kami menjalankan bmelalui fungsi ini dan membagi hasilnya dengan 2, dan ada jawaban kami.

Produksi ETH
sumber
1

Oracle SQL 11.2, 206 byte

WITH v AS(SELECT b,MIN(p)i,MAX(p)a FROM(SELECT SUBSTR(TRANSLATE(:1,'])>}','[(<{'),LEVEL,1)b,LEVEL p FROM DUAL CONNECT BY LEVEL<9)GROUP BY b)SELECT COUNT(*)FROM v x,v y WHERE x.i<y.i AND x.a<y.a AND y.i<x.a;

Tidak golf:

WITH v AS( -- Compute min and max pos for each bracket type
           SELECT b,MIN(p)i,MAX(p)a 
           FROM   ( -- replace ending brackets by opening brakets and split the string  
                    SELECT SUBSTR(TRANSLATE(:1,'])>}','[(<{'),LEVEL,1)b,LEVEL p 
                    FROM DUAL 
                    CONNECT BY LEVEL<9
                  )
           GROUP BY b
         )
SELECT COUNT(*)
FROM   v x,v y
WHERE  x.i<y.i AND x.a<y.a AND y.i<x.a -- Apply restrictions for interlocking brackets  
Jeto
sumber