Tujuan Anda: Diberikan serangkaian tanda kurung, output Jarak Damerau-Levenshtein minimum diperlukan untuk mengubah string input menjadi string di mana tanda kurung seimbang.
Memasukkan
String input hanya akan berisi tanda kurung dan tidak ada karakter lain. Artinya, itu adalah kombinasi dari salah satu karakter di (){}[]<>
. Anda dapat mengambil input baik sebagai string atau array karakter. Anda tidak boleh membuat asumsi lain tentang string input; mungkin panjangnya sewenang-wenang (hingga ukuran maksimum yang didukung oleh bahasa Anda), mungkin kosong, kurung mungkin sudah seimbang, dll.
Damerau-Levenshtein Jarak
Jarak Damerau-Levenshtein antara dua string adalah jumlah minimum penyisipan, penghapusan, pergantian karakter tunggal, dan transposisi (swapping) dari dua karakter yang berdekatan.
Keluaran
Output harus Jarak Damerau-Levenshtein minimum antara string input dan string di mana tanda kurung cocok. Output harus berupa angka , bukan string seimbang yang dihasilkan.
Sepasang tanda kurung dianggap "cocok" jika tanda kurung buka dan tutup berada dalam urutan yang benar dan tidak memiliki karakter di dalamnya, seperti
()
[]{}
Atau jika setiap sub-elemen di dalamnya juga cocok.
[()()()()]
{<[]>}
(()())
Sub-elemen juga dapat disarangkan beberapa lapisan.
[(){<><>[()]}<>()]
<[{((()))}]>
(Terima kasih kepada @DJMcMayhem untuk definisinya)
Uji Kasus
Input Possible Balanced Output
Empty Empty 0
[](){}<> [](){}<> 0
[(){}<> [(){}<>] 1
[(]) []() 1
[[[[[[[[ [][][][] 4
(](<>}[>(}>><(>(({}] ()(<>)[(<><>){}] 7
>]{])< []{()} 3
([)}}>[ (){}<> 4
{<((<<][{{}>[<) <>(<<[]>{}>[]) 5
{><({((})>}}}{(}} {<><({()})>}{}{()} 4
(](<)>}[>(}>>{]<<(]] (<()<><<>()>>[])<()> 9
}})( {}() 2
(Terima kasih kepada @WheatWizard untuk memecahkan setengah dari kasus uji)
Ini adalah kode-golf , byte terkecil menang!
Kiriman Anda harus dapat diuji, artinya harus menghasilkan hasil untuk setiap kasus uji dalam waktu tidak lebih dari satu jam.
[<>]
atau[]<>
atau<>
Jawaban:
Retina,
254252264248240232267 byteTerima kasih kepada @AnthonyPham, @officialaimm, dan @MistahFiggins karena telah menunjukkan bug
Cobalah secara Online!
Solusi gaya non-brute! Ini berfungsi untuk semua kasus uji, dan bahkan menemukan kesalahan dalam satu.
-2 byte terima kasih kepada @MartinEnder (
${4}
ke$+
)+12 byte ke akun untuk kasus swapping tambahan
-16 byte dengan memanfaatkan kelas karakter dengan lebih baik
-8 byte dengan menghapus batasan yang tidak perlu pada swapping. Ini juga memperbaiki bug :)
-10 byte dengan menggabungkan logika swapping ke dalam satu regex tunggal
+2 byte ke akun untuk swap berurutan
+ Banyak untuk berbagai perbaikan bug **
Penjelasan:
T`[]()`:;'"
digunakan untuk mengganti jenis braket khusus untuk kenyamanan. Pertama, kami secara rekursif mengganti semua tanda kurung yang cocok dengan-
,AB
atau69
bergantung pada apakah berdekatan atau tidak.Kemudian, "swapping" yang bermanfaat dilakukan dengan menghapus tanda kurung yang baru cocok dan menambahkan a
1
ke awal string. Kami juga mengganti-
dengan string kosong, karena hanya digunakan untuk swapping di atas.Selanjutnya, kami mencoba "penggantian" dengan menghapus pasangan tanda kurung yang tidak cocok yang tidak tumpang tindih tanda kurung yang sudah cocok dan menambahkan
1
ke string.Akhirnya,
\W|6B|1
hitung kurung tunggal yang tersisa ditambah jumlah1
s.** Saat ini saya sedang mengerjakan versi yang lebih pendek yang menggunakan fitur pemisahan garis Retina, meskipun saya mengalami masalah yang cukup besar sehingga mungkin butuh waktu cukup lama.
sumber
${4}
bisa disingkat$+
. Saya sangat ingin tahu mengapa ini dijamin bekerja.[{][}] [] [[][][][][][]] [][][][][][][][][][][][]
, Anda cukup menukar bagian}
dalam pasangan kurung pertama dan membuatnya seimbang. Spasi digunakan untuk membuat input sedikit lebih mudah dibaca. Anda menghasilkan 3 tetapi harus benar-benar satu.[{]}
mengembalikan 1 tetapi[{][]}
mengembalikan 2.Brain-Flak , 1350 byte
Cobalah online!
Dengan perbandingan kecepatan konstan dan pointer dereferencing, algoritma ini adalah O (n 3 ). Sayangnya, Brain-Flak tidak memiliki keduanya, jadi program ini berjalan dalam waktu O (n 5 ) sebagai gantinya. Kasing uji terpanjang membutuhkan waktu sekitar 15 menit.
Menyederhanakan hasil
Untuk melihat bahwa algoritma saya berfungsi, kami perlu menunjukkan beberapa hasil yang mengurangi ruang pencarian secara signifikan. Hasil ini bergantung pada fakta bahwa target adalah seluruh bahasa, bukan hanya satu string tertentu.
Tidak diperlukan penyisipan. Sebagai gantinya, Anda bisa menghapus braket yang akhirnya cocok dengan karakter yang dimasukkan.
Anda tidak perlu menghapus braket, lalu menukar kedua tetangganya. Untuk melihat ini, asumsikan wlog bahwa braket yang dihapus adalah
(
, jadi kami mentransformasikannyaa(c
keca
dalam dua langkah. Dengan mengubahc
dan memasukkan salinan, kita dapat mencapaica()
dalam dua langkah tanpa swap. (Penyisipan ini kemudian dapat dihapus oleh aturan di atas.)Braket yang sama tidak perlu ditukar dua kali. Ini adalah fakta standar tentang jarak Damerau-Levenshtein secara umum.
Hasil penyederhanaan lain yang tidak saya gunakan, karena menghitungnya akan membutuhkan biaya byte:
Algoritma
Ketika string apa pun direduksi menjadi string seimbang, salah satu dari yang berikut ini benar:
k
(mungkin setelah mengubah satu atau keduanya).k
.Dalam kasus kedua, braket pada posisi
k
mungkin telah bertukar dengan salah satu tetangganya. Dalam salah satu dari dua kasus terakhir, string antara braket pertama (mungkin yang baru) dan braket yang dimulai pada posisik
harus diedit ke string seimbang, seperti halnya string yang terdiri dari semuanya setelahnyak
.Ini berarti bahwa pendekatan pemrograman dinamis dapat digunakan. Karena braket bertukar tidak perlu ditukar lagi, kita hanya perlu mempertimbangkan substring yang berdekatan, serta selanjutnya dibentuk dengan menghapus karakter kedua dan / atau karakter kedua dari belakang substring tersebut. Karenanya, hanya ada O (n 2 ) yang harus kita perhatikan. Masing-masing dari mereka memiliki O (n) cara yang mungkin untuk mencocokkan (atau menghapus) braket pertama, sehingga algoritma akan menjadi O (n 3 ) di bawah kondisi di atas.
Struktur data
Tumpukan yang tepat termasuk tanda kurung dari string asli, dengan dua byte per braket. Entri pertama menentukan seluruh braket, dan dipilih sedemikian rupa sehingga tanda kurung yang cocok memiliki perbedaan tepat 1. Entri kedua hanya menentukan apakah braket pembuka atau braket penutup: ini menentukan berapa banyak perubahan yang diperlukan untuk mencocokkan dua tanda kurung satu sama lain. Tidak ada nol tersirat di bawah ini yang pernah dibuat eksplisit, sehingga kita dapat menggunakan
[]
untuk mendapatkan panjang total dari string ini.Setiap substring yang dipertimbangkan diwakili oleh dua angka dalam kisaran 0 hingga 2n: satu untuk posisi awal, dan satu untuk akhir. Interpretasinya adalah sebagai berikut:
2k
akan mulai dari posisik
(0-diindeks), dan karakter kedua tidak dihapus.2k+1
akan mulai dari posisik
, dan karakter kedua dihapus karena telah ditukar kiri.2k
akan berakhir tepat sebelum posisik
(yaitu, rentang inklusif kiri dan eksklusif kanan.)2k-1
akan berakhir tepat sebelum posisik
, dan karakter kedua dari belakang dihapus karena telah ditukar dengan benar.Beberapa rentang (
k
kek+1
,2k+1
ke2k+1
,2k+1
ke2k+3
, dan2k+1
untuk2k+5
) tidak masuk akal secara fisik. Beberapa dari mereka muncul sebagai nilai perantara, karena lebih mudah daripada menambahkan pemeriksaan tambahan untuk menghindarinya.Stack kiri menyimpan jumlah suntingan yang diperlukan untuk mengubah setiap substring menjadi string yang seimbang. Jarak edit untuk interval
(x,y)
disimpan pada kedalamanx + y(y-1)/2
.Selama loop dalam, entri ditambahkan di atas tumpukan kiri untuk menunjukkan gerakan mana yang mungkin. Entri ini panjangnya 5 byte. Menghitung dari atas, jumlahnya
d+1
,y1
,x1
,y2
,x2
, di mana langkah itu biayad
mengedit langkah dan membagi substring dalam(x1,y1)
dan(x2,y2)
.Kode
Deskripsi yang akan datang. Untuk saat ini, inilah salinan kode saya yang berfungsi. Beberapa komentar mungkin tidak konsisten dengan terminologi.
sumber
Haskell , 797 byte
Cobalah online!
sumber