Kemunculan Kod n Golang: Lakukan atau Jangan Regex

Diinspirasikan oleh siaran Shradha Agarwal di Byte Size Go :di sini: Saya memutuskan untuk menulis tentang pendekatan saya terhadap perkara ini, ia berbeza dan ingin berkongsinya. Siaran itu ditulis dengan baik dan penyelesaiannya padat dan ringkas, saya syorkan untuk membacanya dahulu juga.

Itu adalah siri blogvent, saya juga ingin mengambil bahagian dalam blogvent tetapi tidak pasti saya akan menyiapkannya.

pengenalan

Nah, hari ini adalah hari ke-3 kemunculan kod 2024, dan saya telah melakukannya pada strim langsung. Saya berada di belakang dua hari tetapi menyelesaikannya satu demi satu. Setakat ini, saya telah belajar banyak perkara dalam Go. Mari selami untuk hari ke-3.

Bahagian 1

Bahagian satu kepada mana-mana masalah AOC nampaknya mudah, tetapi sebaik sahaja bahagian kedua didedahkan, pelaksanaan sebenar mula memerah keringat (jika anda tidak optimistik atau tidak bertimbang rasa)

Untuk bahagian 1 untuk hari ini, adalah untuk menghuraikan rentetan yang mengandungi mul(X,Y) ungkapan, dengan X boleh menjadi sebarang nombor 3 digit. Jadi, mungkin terdapat berbilang ungkapan sedemikian dalam rentetan dan tujuannya adalah untuk mendarab X dan Y dalam ungkapan individu dan menambahkannya.

xmul(2,4)&mul[3,7]!^don't()_mul(5,5)+mul(32,64](mul(11,8)undo()?mul(8,5))

Dalam contoh di atas ini terdapat 4 ungkapan sedemikian, dan jika kita menambah pendarabannya, kita mendapat jawapan sebagai 161.

Pendekatan

Ia kelihatan seperti corak Regex, mencari corak seperti ekspresi dalam rentetan. Jadi, pendekatannya adalah untuk mencari ungkapan sedemikian dengan corak regex dan menghuraikan nombor kepada integer, dan mendarabkannya, dengan mudah.

Anda boleh meneruskan dan menulis penghurai untuk mengulangi setiap aksara dalam rentetan dan menghuraikan token, kemudian menilai ungkapan. Itu adalah pendekatan yang sah, tetapi saya memilih untuk melakukan ini kerana saya tidak tahu cara menulis penghurai secara jujur, saya mahu mencuba penyelesaian itu pada penghujungnya juga.

Tetapi untuk bahagian pertama, ungkapan biasa pantas nampaknya idea yang bagus.

Membina Ungkapan Biasa

Perkara pertama ialah menulis ungkapan biasa untuk bahagian mul(X,Y) yang merupakan satu-satunya bahagian yang mencabar dalam bahagian satu. Selebihnya hanyalah matematik mudah.

Jadi, kita perlu mencari mul, kemudian a ( kemudian sebarang nombor yang panjangnya 1 hingga 3 digit, kemudian , dan sekali lagi nombor yang panjangnya 1 hingga 3 digit, dan akhirnya berakhir dengan )

Itu diterjemahkan kepada:

mul\((\d{1,3}),(\d{1,3})\) 

Mari pecahkan:

• mul untuk menangkap perkataan literal mul

• ( ini adalah untuk kurungan pertama dalam ungkapan mul() , kita perlu melepaskan kurungan dalam ungkapan biasa jika kita mahu memadankannya, jadi kita gunakan sebelum itu.

• Kemudian kami mempunyai kumpulan perlawanan (d{1,3}) , ini akan menjadi X dalam mul(X,Y):

  • Kumpulan perlawanan adalah seperti kumpulan perlawanan dalam regex, pada asasnya, jika anda ingin menangkap bahagian tertentu dalam keseluruhan perlawanan, maka kami menggunakan () untuk mengumpulkannya secara individu, ini tidak perlu tetapi membantu dalam mendapatkan perkara yang betul tanpa overhead
  • Dalam kes ini, kami menggunakan kumpulan padanan untuk menangkap nombor yang boleh mempunyai 1 hingga 3 digit.
  • Cara lain untuk menulis ini ialah ([0-9]{1,3}) , yang juga akan melakukan perkara yang sama, (NOTA: terdapat beberapa perbezaan dalam [0-9] dan d, tetapi itu sangat halus dan tidak akan menjejaskan teka-teki ini, jika anda masih ingin tahu, saya lebih suka membaca soalan StackOverflow ini)

• Kami kemudiannya menggunakan , untuk pemisah operan X dan Y dalam ungkapan mul(X,Y)

• Kami kemudian melakukan perlawanan yang sama untuk Y dalam mul(X,Y) dengan kumpulan perlawanan (d{1,3})

• Akhir sekali, kami menamatkan ungkapan biasa dengan ) untuk menamatkan ungkapan

Kodkannya

Ini agak mudah, kami mengambil baris sebagai rentetan dan menggunakan fungsi regexp.MustCompile yang memberi kami objek Regexp, yang seterusnya mempunyai beberapa kaedah yang dikaitkan dengannya untuk mencari, memadankan, menggantikan dan perkara lain yang boleh dilakukan dengan ungkapan biasa pada rentetan.

Setelah kita mempunyai mulRegex , kita boleh menggunakan kaedah FindAllStringSubmatch yang dikaitkan dengan struct Regexp dalam pakej regexp. Fungsi ini mengambil rentetan untuk melaksanakan regex, dan bilangan maksimum padanan untuk dikembalikan. Kami mahukan semua keputusan, jadi kami melepasinya dalam -1 untuk mendapatkan semua perlawanan.

Sekarang, kaedah ini mengembalikan sekeping hirisan rentetan, setiap hirisan adalah padanan, dan dalam setiap hirisan, terdapat hirisan rentetan, dengan rentetan yang dipadankan dan kumpulan padanan seterusnya dalam rentetan jika ada.

xmul(2,4)&mul[3,7]!^don't()_mul(5,5)+mul(32,64](mul(11,8)undo()?mul(8,5))

Jadi, fungsi di atas akan mengembalikan sesuatu seperti ini

mul\((\d{1,3}),(\d{1,3})\) 

Ini ialah senarai rentetan, ini kelihatan seperti nombor tetapi itu adalah jenis rentetan dalam Golang.

Sekarang kita mempunyai ini, kita boleh mencipta bahagian logik sebenar untuk mendapatkan hasil, iaitu menghuraikan ungkapan ini, mendarab X dan Y dan menambah keputusan untuk setiap ungkapan.

func FindMulExpression(line string) [][]string {
  mulRegex := regexp.MustCompile(`mul\((\d{1,3}),(\d{1,3})\)`)
  return mulRegex.FindAllStringSubmatch(line, len(line))
}

Ini agak mudah, kami mengulangi setiap perlawanan, iaitu satu ungkapan mul(X,Y) dan menghuraikan X dan Y setiap satu kepada integer dan mendarabnya, hasil yang diperoleh kemudiannya ditambah pada markah. Kami melakukan ini untuk setiap ungkapan mul(X,Y) yang terdapat dalam rentetan(baris) dan mengembalikan skor akhir.

Input

Sekarang, contoh memberi kami satu rentetan, tetapi saya menyedari terdapat enam baris dalam input (input individu), jadi kami perlu menghuraikan setiap baris dan menambah markah.

Ingat ini kerana ia akan menjadi kritikal dalam bahagian 2, saya mengambil sedikit masa dan mempersoalkan kewujudan saya untuk menyedari bahawa kita perlu menggabungkan semua baris untuk mendapatkan keputusan (tidak perlu dalam bahagian 1 tetapi pasti dalam bahagian 2).

Bahagian 2

Di sinilah selalunya perkara yang tidak kena. Sekurang-kurangnya bagi saya, ia berlaku.

Saya mulakan dengan pendekatan yang sangat naif, dengan gelung selama-lamanya dan mencari indeks buat atau tidak dan menanggalkan bahagian tersebut, dan kemudian gelung sehingga kita tidak mempunyai apa-apa lagi. Itu berfungsi untuk kes ujian tetapi gagal pada input sebenar.

Pendekatan yang akhirnya saya buat dan sedang berusaha dengan mengubah sedikit pendekatan yang sama.

Pendekatan

Apa yang saya hasilkan ialah untuk mencari lokasi padanan pertama rentetan don’() dan do() dalam keseluruhan rentetan, kami mengambilnya dan mengalih keluar bahagian selepas don’t() atau sebelum do() . Dengan cara itu kita boleh memangkas rentetan kepada hanya ungkapan mul()yang sah/didayakan.

Jadi, pendekatan yang ditakrifkan dengan lebih jelas ialah:

• Cari lokasi (indeks) ungkapan jangan() dan lakukan()

• Kami perlu menjejaki sama ada rentetan sebelumnya didayakan atau dilumpuhkan supaya akan menyimpan bendera untuk menambahkan ungkapan yang didayakan (sebahagian daripada rentetan) pada hasil akhir

• Jika tiada satu pun daripada mereka ditemui, kembalikan rentetan(baris) seperti sedia ada

• Jika kami menemui salah satu daripada mereka maka:

  • Jika kita dapati jangan dahulu (jangan() muncul sebelum lakukan())

    • Jika bendera yang didayakan adalah benar → tambah rentetan sebelum ungkapan jangan()
    • Kemudian togol yang didayakan sebagai palsu dan potong bahagian jangan(). (Dengan cara ini kami telah selesai menyemak segala-galanya sebelum ungkapan jangan, jadi kami mengalih keluar bahagian itu daripada rentetan baris)

  • Jika kita dapati lakukan dahulu (do() muncul sebelum jangan())

    • Jika bendera yang didayakan adalah benar → tambah rentetan sebelum ungkapan do()
    • Kemudian togol yang didayakan sebagai benar dan potong bahagian do(). (Dengan cara ini kami telah selesai menyemak segala-galanya sebelum ungkapan do, jadi kami mengeluarkan bahagian daripada rentetan baris)

• Kami melakukan ini sehingga tiada rentetan baris lagi untuk diperiksa

Kod

Saya menggunakan Strings.Index mudah untuk mendapatkan indeks padanan pertama untuk subrentetan, Dalam kes ini, saya mahu indeks padanan pertama untuk don't() dan do() . Sebaik sahaja kami mempunyai indeks bagi kedua-dua perlawanan, kami boleh mengulangi sehingga kami tidak mempunyai sebarang tindakan atau tindakan dalam rentetan.

Jika kita ada lakukan atau tidak, kita tambahkan pada rentetan bahagian sebelum jangan jika didayakan atau bahagian sebelum lakukan jika didayakan dan togol hidupkan dan matikan bendera yang didayakan dengan sewajarnya. Pada penghujung gelung, rentetan hasil hanya akan mempunyai bahagian baris/rentetan yang didayakan.

xmul(2,4)&mul[3,7]!^don't()_mul(5,5)+mul(32,64](mul(11,8)undo()?mul(8,5))

Saya mengambil fungsi ini dan menghantarnya ke fungsi darab di mana saya mendapat corak padanan untuk ungkapan mul dan melakukan pengiraan.

Kaedah rentetan.Indeks mengambil rentetan dan subrentetan untuk mencari dalam rentetan itu dan mengembalikan indeks bagi kejadian pertama bagi subrentetan itu. Dengan itu kita boleh mengenal pasti sama ada rentetan baris mengandungi ungkapan do() atau jangan(), jika tidak, kita hanya kembalikan baris itu dan jika ada kejadiannya, kita gelung dan memangkas rentetan sebelum dan selepas ungkapan bergantung pada sama ada bendera didayakan atau dilumpuhkan.

Mari kita ambil contoh dan ikuti logiknya:

xmul(2,4)&mul[3,7]!^don't()_mul(5,5)+mul(32,64](mul(11,8)undo()?mul(8,5))

Kami memproses hasil dengan fungsi Darab yang sama yang kami gunakan pada bahagian pertama selepas menghantarnya melalui fungsi FindMulExpression yang akan mengembalikan semua ungkapan mul dalam rentetan baris hasil.

Mengetuai input

Input sebenar teka-teki adalah saya rasa berbilang baris, jadi kita perlu mengekalkan keadaan garis ini dalam semua baris yang tinggal. ATAU, kita boleh menjadi lebih bijak dan mencipta satu rentetan besar dan memprosesnya. Kedua-duanya adalah sah dan akan memberikan hasil yang sama. Saya hanya tidak suka menambah overhed untuk menjejaki semua negeri dan baris, jadi saya hanya menggabungkan semua baris dan memproses rentetan tunggal itu.

Kesimpulan

Ini adalah masalah mudah pada dasarnya tetapi jika anda tidak mengetahui regex anda boleh pergi ke lubang arnab untuk menulis parser anda sendiri atau manipulasi rentetan berwayar (sama seperti yang saya lakukan).

Itu sahaja di hari ke-3, saya akan melakukan lebih banyak penyelesaian strim langsung pada hujung minggu dan mungkin minggu depan juga. Cari kod untuk penyelesaian AoC saya di sini di GitHub.

Sehingga itu,

Selamat Mengekod :)

Atas ialah kandungan terperinci Kemunculan Kod n Golang: Lakukan atau Jangan Regex. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!