Golang 代碼日的到來：搜尋 XMAS 和 X-MAS

介紹

進入第四天，我們面前有一個網格問題，我們得到了一些網格形式的數字，即一些帶有一些大寫字母的行和列。我們需要做的是在任意方向（上、左、下、右、對角線）找到單字 XMAS，而在第二部分我們需要找到形成 X 的單字 MAS。

那麼，讓我們看看如何在 golang 中解決這個問題。

您可以在 GitHub 上查看我的解決方案。

建構網格

問題最根本的部分在於實際上將文字轉換為網格或矩陣形式。我們可以將行分割成單獨的行，並將每個字元作為列表中的元素附加，這樣我們就可以得到一個字串列表列表，它是一個矩陣或網格狀（二維）結構。

所以，下面是謎題的輸入。

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

我們需要將其轉換成這樣的

[
    [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]
]

所以，這是一個字串列表，我們可以在 golang 中說它是一個 [][]string 。我們可以透過建立這樣的函數來做到這一點：

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
}

上面的函數接受一個字串列表並傳回一個字串列表，這些字串是網格中的單個字母。

我們可以讀取檔案位元組並按換行符分割位元組，然後將其用作此函數的輸入。

因此，一旦輸入被解析為網格，我們就可以開始思考在其中尋找單字 XMAS 的實際邏輯。

第 1 部分

所以，在第一部分中，我們需要在矩陣中找到可能出現的單字 XMAS：

• 轉發（作為 XMAS）

• 向後（如 SAMX）

• 向上
  

            S
            A
            M
            X

• 向下

            X
            M
            A
            S    

• 對角線向上（右或左上）

            S
              A
                M
                  X

            OR
                  S
                A
              M 
            X

• 對角線向下（右或左）

                     X
                   M
                 A
               S

            OR

            X
              M
                A
                  S

所以，XMAS 可以出現在網格中的方向有 8 個，這些 XMAS 的數量可能有 n 個。我們需要找到網格中這些的數量。

為了解決這個問題，我們可以找到單字XMAS 中的第一個字符，然後逐一搜尋所有方向並檢查是否找到M，如果在任何方向上找到M，我們繼續前進那個方向，檢查那個方向是否有A和S。

方法如下：

• 將計數器初始化為 0

• 迭代每一行

  • 迭代行中的每個字元

    • 檢查字元是否等於X

    • 如果角色是X→

      • 迭代所有方向（上、下、右、左、左上、右上、左下、右下）

        • 對於那個方向，如果我們發現字元是M
        • 繼續往同一方向前進，類似地找到A和S，如果找到所有字元XMAS，則增加計數器
        • 否則選擇循環中的另一個方向

這個看起來複雜又龐大，其實很簡單，一次專註一件事，你就能輕鬆解決。

因此，為了實現這一點，我們需要先定義一些東西：

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

因此，我們定義了方向上的整數列表，這些整數是我們需要添加或減去才能到達所需位置的 x 和 y 座標。它基本上就像一個單位向量，它的距離為 1，方向由 或 表示 - 表示 x 座標向左或向右移動，y 座標上下移動。

所以，讓我更清楚地解釋一下，假設我位於 4x4 維度的網格中的 (1,2)。

[
    [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]
]

所以，在 2,1 處我們有 G ，所以我們檢查一些方向

向上 → 0,-1 → 2 0, 1-1 → 2,0，我們已經移動到 C

右 → 1,0 → 2 1, 1 0 → 3,1 ，我們已經移動到 H

下、左→ -1,1 → 2-1, 1 1 → 1, 2，我們已經移動到 J

所以，你明白了，我們正在使用這些座標向某些方向移動。

我們可以使用它們來獲得我們想要進行的下一個方向跳躍，以查找該元素是否具有我們正在搜尋的單字中的下一個字元。

我們將編寫一個函數來首先執行此操作，並抽象化該函數來檢查我們是否在網格中找到了該單字。

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
}

上面的函數接受一個網格並傳回一個整數，該整數將作為分數，即在網格/矩陣中找到的 XMAS 單字數。

首先，我們需要迭代網格中的每一行，對於每一行，我們迭代字符，因此我們將 x 和 y 座標作為網格的索引。然後我們需要檢查當前字元是否為 X 或 wordList[0] ，如果是這種情況，我們迭代所有方向並檢查是否可以找到 XMAS，即該方向上的 MAS，如果是，我們會遞增計數器。 FindXMAS 函數是什麼，讓我們將其抽像出來，並傳入x、y，它們是當前單字的座標，1 將是XMAS 的單字位置，在這種情況下，我們已經找到了我們需要的X找到那個方向的MAS。我們傳遞網格和方向，因此如果該方向中有 MAS，則函數將傳回 true 或 false。

因此迭代：

• 我們迭代網格並取得 row 和 x 作為目前行的字串清單和索引。

• 對於每一行，即字串列表，我們迭代字串列表以獲取 char 和 y 作為字元（字串）以及該字元在字串列表中的索引。

• 如果我們發現目前字元等於 X，即 wordList 的第 0 個索引

  • 我們迭代所有方向並呼叫函數 FindXMAS 來檢查剩餘單字是否在該方向 MAS
  • 如果我們找到所有單詞，我們就會增加計數器。

• 因此，我們在計算網格/矩陣中 XMAS 的單字數時傳回計數器。

現在，我們可以實作 FindXMAS 函數，它接受 x、y 座標、單字位置、方向和網格，如果找到單字則回傳。

• 首先，我們取得目前的 x 座標並加入方向的 x 分量（第 0 個索引或第一個元素）

• 將目前 y 座標加到方向的 y 分量（第一個索引或第二個元素）

• 如果當前函數中的單字位置，即單字索引或單字本身等於wordList，則表示已經完全找到了所需的單字

• 我們需要透過將方向加到 x 和 y 座標來檢查，我們沒有超出網格的寬度和高度，因此如果超出，我們將返回 false

• 最後的 if 用於檢查當前字元是否等於我們要查找的單詞，它可以是 M、A 或 S 。如果是這樣，我們透過傳遞更新的 x 和 y 座標以及 wordList 中的下一個單字來傳回遞歸呼叫 FindXMAS 函數，我們保持方向相同並傳遞整個網格。
  

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

因此，我們已經實現了 FindXMAS 函數，如果我們透過更新座標並檢查網格中該位置的單字是否是 MAS 中的下一個單詞，沿著特定方向找到 MAS 單詞，則該函數將傳回列表。

所以，這就是整個第一部分的樣子：

[
    [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]
]

我們將行作為字串列表，並將其傳遞給 ConstructGrid 並獲取網格，最後，我們調用 TraverseGrid ，透過傳遞網格並獲取分數作為網格中 XMAS 單字的計數。

這是第 1 部分的內容。

第2部分

對於第二部分，我們需要找出十字形狀的 MAS，如下所示：

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
}

所以，為了解決這個問題，我們可以採取類似的方法，但更簡單，我們只需要找到A，因為中心總是有MAS 這個詞，所以我們只需檢查是否有A 和左上角、右上角、右下角、左下角有M 或S 。

加1減1得到右上角、左上位置、右下位置和左下位置的座標。我們會進行基本檢查，看看是否超出了網格的邊界。如果我們超出界限，我們將找不到 MAS

但是如果我們在網格內，我們現在得到這4 個位置的字符，我們檢查左上角和右下角是否有M 和S 或S 或M，右上角和左下角類似分別具有M和S或S或M。這是字元 A 上方和下方的 M 和 S 的對角線搜尋。

因此，如果我們的對角線都匹配，我們將返回 true。

            S
            A
            M
            X

這就是尋找 MAS 對角線的簡單實作。

現在，我們需要稍微更改一下 TraverseGrid，因為我們只是迭代網格，並檢查行中的字元中是否有 A，即 wordList[2]。現在，如果我們有 A，我們需要使用當前座標和網格來呼叫 FindMAS 函數，如果函數傳回 true，我們將增加計數器。

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

所以，這就是第2部分的最終實現，我們得到了橫向MAS的計數。

您可以在 GitHub 上查看我的解決方案。

結論

所以，這就是 Golang 程式碼降臨的第四天，如果您有任何建議，以及您是如何實現的，請告訴我。有更好的解決方案嗎？

快樂編碼:)

以上是Golang 代碼日的到來：搜尋 XMAS 和 X-MAS的詳細內容。更多資訊請關注PHP中文網其他相關文章！