Kedatangan Hari Kod n Golang: Mencari XMAS dan X-MAS

pengenalan

Bergerak ke hari ke-4, kita menghadapi masalah grid di hadapan kita, kita diberikan beberapa nombor dalam bentuk grid, iaitu beberapa baris dan lajur dengan beberapa huruf besar. Apa yang perlu kita lakukan ialah mencari perkataan XMAS dalam mana-mana arah (atas, kiri, bawah, kanan, pepenjuru), dan di bahagian kedua kita perlu mencari perkataan MAS membentuk X.

Jadi, mari lihat bagaimana kita boleh mendekati perkara ini dan menyelesaikannya dalam golang.

Anda boleh menyemak penyelesaian saya di sini di GitHub.

Membina grid

Bahagian paling asas masalah terletak pada sebenarnya menukar teks ke dalam bentuk grid atau matriks. Kita boleh membahagikan baris, kepada baris individu dan menambahkan setiap aksara sebagai elemen dalam senarai, dan dengan cara itu kita boleh mempunyai senarai senarai rentetan yang merupakan struktur matriks atau grid (2 dimensi).

Jadi, di bawah adalah input untuk teka-teki.

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

Kita perlu menukarnya menjadi seperti ini

[
    [M M M S X X M A S M]
    [M S A M X M S M S A]
    [A M X S X M A A M M]
    [M S A M A S M S M X]
    [X M A S A M X A M M]
    [X X A M M X X A M A]
    [S M S M S A S X S S]
    [S A X A M A S A A A]
    [M A M M M X M M M M]
    [M X M X A X M A S X]
]

Jadi, ini ialah senarai rentetan, kita boleh katakan dalam golang ia ialah rentetan [][] . Kita boleh melakukannya dengan mencipta fungsi seperti ini:

func ConstructGrid(lines []string) [][]string {
    grid := [][]string{}
    for _, line := range lines {
        row := []string{}
        for _, char := range strings.Split(line, "") {
            row = append(row, char)
        }
        grid = append(grid, row)
    }
    return grid
}

Fungsi di atas mengambil senarai rentetan dan mengembalikan senarai rentetan yang merupakan huruf individu dalam grid.

Kita boleh membaca bait fail dan membahagikan bait pada aksara baris baharu dan kemudian ini akan digunakan sebagai input untuk fungsi ini.

Jadi, setelah input dihuraikan ke dalam grid, kita boleh mula memikirkan logik sebenar mencari perkataan XMAS di dalamnya.

Bahagian 1

Jadi, di bahagian pertama, kita perlu mencari perkataan XMAS dalam matriks yang mungkin muncul:

• ke hadapan (sebagai XMAS)

• ke belakang (sebagai SAMX)

• ke atas
  

            S
            A
            M
            X

• ke bawah

            X
            M
            A
            S    

• Pepenjuru ke atas (kanan atau atas kiri)

            S
              A
                M
                  X

            OR
                  S
                A
              M 
            X

• Pepenjuru ke bawah (kanan atau kiri)

                     X
                   M
                 A
               S

            OR

            X
              M
                A
                  S

Jadi, terdapat 8 arah di mana XMAS boleh muncul dalam grid, terdapat n bilangan XMAS ini. Kita perlu mencari kiraan ini dalam grid.

Untuk mendekati ini, kita boleh mencari watak pertama dalam perkataan XMAS dan kemudian mencari dalam semua arah satu demi satu dan semak jika kita menemui M dan jika kita telah menemui M dalam mana-mana arah, kita terus bergerak ke hadapan dalam arah itu dan semak sama ada terdapat A dan S ke arah itu.

Pendekatannya kelihatan seperti ini:

• Mulakan kaunter kepada 0

• Lelaran pada setiap baris

  • Lelaran pada setiap aksara dalam baris

    • Semak sama ada watak itu sama dengan X

    • Jika wataknya ialah X→

      • Lelaran ke atas semua arah (atas, bawah, kanan, kiri, atas-kiri, atas-kanan, bawah-kiri, bawah-kanan)

        • Untuk arah itu jika kita dapati watak itu adalah M
        • Teruskan bergerak ke hadapan dalam arah yang sama untuk mencari A dan S dengan cara yang sama, jika kami menjumpai semua aksara XMAS maka, tambahkan pembilang
        • Lain pilih arah lain dalam gelung

Ini kelihatan rumit dan besar tetapi mudah, fokus satu perkara pada satu masa dan anda boleh menyelesaikannya dengan mudah.

Jadi, untuk pelaksanaan ini, kita perlu menentukan beberapa perkara dahulu:

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

Jadi, kami telah menentukan senarai integer dalam arah yang merupakan koordinat x dan y yang perlu kami tambah atau tolak untuk sampai ke lokasi yang dikehendaki. Ia pada asasnya seperti vektor unit, ia mempunyai jarak 1 dan arah yang ditunjukkan oleh atau - menunjukkan untuk bergerak ke kiri atau kanan untuk koordinat x dan ke atas dan ke bawah untuk y c-ordinat.

Jadi, izinkan saya menerangkannya dengan lebih jelas, katakan saya berada di (1,2) dalam grid yang berdimensi 4x4.

[
    [M M M S X X M A S M]
    [M S A M X M S M S A]
    [A M X S X M A A M M]
    [M S A M A S M S M X]
    [X M A S A M X A M M]
    [X X A M M X X A M A]
    [S M S M S A S X S S]
    [S A X A M A S A A A]
    [M A M M M X M M M M]
    [M X M X A X M A S X]
]

Jadi, pada 2,1 kita ada G , jadi kita semak beberapa arah untuk ini

naik → 0,-1 → 2 0, 1-1 → 2,0, kami telah berpindah ke C

kanan → 1,0 → 2 1, 1 0 → 3,1 , kita telah berpindah ke H

bawah, kiri → -1,1 → 2-1, 1 1 → 1, 2, kita telah berpindah ke J

Jadi, anda mendapat idea, bahawa kami bergerak ke beberapa arah menggunakan koordinat ini.

Kita boleh menggunakan ini untuk mendapatkan lompatan arah seterusnya yang ingin kita lakukan untuk mencari sama ada elemen itu mempunyai aksara seterusnya dalam perkataan yang kita cari.

Kami akan menulis fungsi yang melakukan ini terlebih dahulu dan mengabstrakkan fungsi yang menyemak sama ada kami telah menemui perkataan dalam grid.

func ConstructGrid(lines []string) [][]string {
    grid := [][]string{}
    for _, line := range lines {
        row := []string{}
        for _, char := range strings.Split(line, "") {
            row = append(row, char)
        }
        grid = append(grid, row)
    }
    return grid
}

Fungsi di atas mengambil grid dan mengembalikan integer yang akan menjadi skor iaitu kiraan perkataan XMAS yang terdapat dalam grid/matriks.

Mula-mula, kita perlu lelaran melalui setiap baris dalam grid, untuk setiap baris, kita lelaran ke atas aksara, jadi kita akan mempunyai koordinat x dan y sebagai indeks grid. Kemudian kita perlu menyemak sama ada aksara semasa ialah X atau wordList[0] , jika itu berlaku, kita lelaran ke atas semua arah dan semak sama ada kita boleh menemui XMAS iaitu MAS ke arah itu, jika ya kita menambah kaunter. Apakah fungsi FindXMAS, mari kita abstrak itu, dan masukkan x, y, yang merupakan koordinat bagi perkataan semasa, 1 yang akan menjadi kedudukan perkataan XMAS dan dalam kes ini, kita telah menemui X yang kita perlukan untuk mencari MAS ke arah itu. Kami melepasi grid dan arah, jadi fungsi ini akan kembali benar atau salah jika arah itu mempunyai MAS di dalamnya.

Jadi untuk mengulang:

• Kami mengulangi grid dan mendapatkan baris dan x sebagai senarai rentetan dan indeks baris semasa.

• Untuk setiap baris iaitu senarai rentetan, kami mengulangi senarai rentetan untuk mendapatkan aksara dan y sebagai aksara (rentetan) dan indeks aksara itu dalam senarai rentetan.

• Jika kita dapati aksara semasa bersamaan dengan X yang merupakan indeks ke-0 wordList maka

  • Kami mengulangi semua arah dan memanggil fungsi FindXMAS untuk menyemak sama ada baki perkataan MAS ke arah itu
  • Jika kami menjumpai semua perkataan, kami menambah pembilang.

• Jadi, kami mengembalikan kaunter sambil mengira bilangan perkataan XMAS dalam grid/matriks.

Kini, kita boleh melaksanakan fungsi FindXMAS, yang mengambil koordinat x, y, wordPosition, arah dan grid, dan kembali jika perkataan itu ditemui.

• Pertama, kita ambil koordinat x semasa dan tambah komponen x arah (indeks ke-0 atau elemen pertama)

• tambah koordinat y semasa pada komponen y arah (indeks pertama atau elemen kedua)

• jika kedudukan perkataan iaitu indeks perkataan atau perkataan itu sendiri dalam fungsi semasa adalah sama dengan wordList, bermakna ia telah menemui perkataan yang diperlukan sepenuhnya

• Kami perlu menyemak dengan menambah arah pada koordinat x dan y, kami tidak melampaui lebar dan ketinggian grid, jadi jika kami lakukan, kami mengembalikan palsu

• Yak akhir adalah untuk menyemak sama ada aksara semasa adalah sama dengan perkataan yang kita cari, ia boleh jadi M, A atau S . Jika ya, kami mengembalikan fungsi FindXMAS secara rekursif dengan menghantar koordinat x dan y yang dikemas kini dan perkataan seterusnya dalam wordList, kami mengekalkan arah yang sama dan melepasi keseluruhan grid.
  

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

Jadi, kami telah melaksanakan fungsi FindXMAS, ini hanya akan kembali jika kami telah menjumpai perkataan MAS dengan pergi ke arah tertentu dengan mengemas kini koordinat dan menyemak sama ada perkataan pada kedudukan itu dalam gird adalah perkataan seterusnya dalam MAS senarai.

Jadi, beginilah rupa keseluruhan bahagian pertama:

[
    [M M M S X X M A S M]
    [M S A M X M S M S A]
    [A M X S X M A A M M]
    [M S A M A S M S M X]
    [X M A S A M X A M M]
    [X X A M M X X A M A]
    [S M S M S A S X S S]
    [S A X A M A S A A A]
    [M A M M M X M M M M]
    [M X M X A X M A S X]
]

Kami mengambil baris sebagai senarai rentetan dan menghantarnya kepada ConstructGrid dan mendapatkan grid, akhirnya, kami memanggil TraverseGrid , dengan melepasi grid dan mendapatkan skor sebagai kiraan perkataan XMAS dalam grid.

Itu sahaja dari bahagian 1.

Bahagian 2

Untuk bahagian dua, kita perlu mencari MAS dalam bentuk silang, seperti di bawah:

func ConstructGrid(lines []string) [][]string {
    grid := [][]string{}
    for _, line := range lines {
        row := []string{}
        for _, char := range strings.Split(line, "") {
            row = append(row, char)
        }
        grid = append(grid, row)
    }
    return grid
}

Jadi, untuk menyelesaikannya, kita boleh melakukan pendekatan yang sama tetapi lebih mudah, kita hanya perlu mencari A kerana akan sentiasa ada perkataan MAS di tengah-tengah, jadi kita semak sama ada kita mempunyai A dan kiri atas. , atas-kanan, atau bawah-kanan, bawah-kiri mempunyai M atau S .

Kami mendapat koordinat kedudukan kanan atas, kiri atas, kanan bawah dan kiri bawah dengan menambah dan menolak 1 daripadanya. Kami membuat semakan asas jika kami tidak melampaui sempadan grid. Jika kita melampaui batas, kita tidak akan menemui MAS

Tetapi jika kami berada dalam grid, kami kini mendapat watak di 4 kedudukan tersebut, kami menyemak sama ada kiri atas dan kanan bawah mempunyai M dan S atau S atau M, begitu juga untuk kanan atas dan kiri bawah mempunyai M dan S atau S atau M masing-masing. Ini ialah carian pepenjuru untuk M dan S di atas dan di bawah aksara A.

Jadi, jika kita mempunyai kedua-dua pepenjuru padan kita kembali benar.

            S
            A
            M
            X

Jadi, itulah pelaksanaan mudah untuk mencari pepenjuru MAS.

Sekarang, kita perlu menukar sedikit TraverseGrid, kerana kita hanya mengulangi grid dan semak sama ada kita mempunyai A dalam aksara dalam baris, iaitu wordList[2]. Sekarang, jika kita mempunyai A, kita perlu memanggil fungsi FindMAS dengan koordinat semasa dan grid, jika fungsi itu kembali benar, kita menambah pembilang,.

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

Jadi, itu adalah pelaksanaan terakhir bahagian 2, kita mendapat kiraan MAS dalam arah silang.

Anda boleh menyemak penyelesaian saya di sini di GitHub.

Kesimpulan

Jadi, itu sahaja dari hari ke-4 Kemunculan Kod di Golang, beritahu saya jika anda mempunyai sebarang cadangan dan cara anda mendekatinya. ada penyelesaian yang lebih baik?

Selamat Mengekod :)

Atas ialah kandungan terperinci Kedatangan Hari Kod n Golang: Mencari XMAS dan X-MAS. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!