Code Day n Golang の出現: XMAS と X-MAS の検索

導入

4日目に進むと、グリッドの問題が目の前にあります。グリッドの形でいくつかの数字、つまり、いくつかの大文字を含むいくつかの行と列が与えられます。私たちがしなければならないのは、任意の方向 (上、左、下、右、斜め) で XMAS という単語を見つけることです。2 番目の部分では、X を形成する MAS という単語を見つける必要があります。

それでは、これにどのようにアプローチして golang で解決できるかを見てみましょう。

ここ GitHub で私のソリューションをチェックできます。

グリッドの構築

問題の最も基本的な部分は、テキストを実際にグリッドまたは行列形式に変換することにあります。行を個別の行に分割し、各文字をリストの要素として追加することで、行列またはグリッド状 (2 次元) 構造である文字列のリストのリストを作成できます。

以下はパズルの入力です。

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 という単語を見つける必要があります。

• 転送 (クリスマスとして)

• 後方 (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 という単語の最初の文字を見つけてから、全方向に 1 つずつ検索して M が見つかったかどうかを確認し、いずれかの方向で M が見つかったかどうかを確認して、先に進み続けます。その方向に A と S があるかどうかを確認します。

アプローチは次のようになります:

• カウンタを 0 に初期化します

• 各行を反復処理します

  • 行内の各文字を反復処理します

    • 文字が X と等しいかどうかを確認します

    • キャラクターがXの場合→

      • すべての方向 (上、下、右、左、左上、右上、左下、右下) を反復します

        • キャラクターがMだとわかったらその方向へ
        • 同じ方向に進み続けて、同様に A と S を見つけます。すべての文字 XMAS が見つかったら、カウンターをインクリメントします
        • それ以外の場合は、ループ内の別の方向を選択します

これは複雑で大規模に見えますが、単純です。一度に 1 つのことに焦点を当てれば、簡単に解決できます。

したがって、これを実装するには、最初にいくつかのことを定義する必要があります。

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 を返します。

繰り返します:

• グリッドを反復処理し、行と x を文字列のリストと現在の行のインデックスとして取得します。

• 各行、つまり文字列のリストに対して、文字列のリストを反復処理して、文字 (文字列) として char と y を取得し、文字列のリスト内のその文字のインデックスを取得します。

• 現在の文字が wordList の 0 番目のインデックスである X と等しいことが判明した場合、

  • すべての方向を反復処理し、関数 FindXMAS を呼び出して、残りの単語がその方向にあるかどうかを確認します
  • すべての単語が見つかったら、カウンターをインクリメントします。

• したがって、グリッド/行列内の XMAS の単語数をカウントするときにカウンターを返します。

これで、x、y 座標、wordPosition、方向、グリッドを受け取り、単語が見つかった場合に返す FindXMAS 関数を実装できます。

• まず、現在の x 座標を取得し、方向の x コンポーネント (0 番目のインデックスまたは最初の要素) を追加します

• 現在の y 座標を方向の y コンポーネント (最初のインデックスまたは 2 番目の要素) に追加します

• 現在の関数内の単語の位置、つまり単語インデックスまたは単語自体が 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

パート 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
}

したがって、これを解決するには、同様のアプローチを実行できますが、はるかに単純です。中央には常に MAS という単語が存在するため、A を見つける必要があるだけです。そのため、A と左上があるかどうかを確認するだけです。 、右上、または右下、左下には M または S があります。

それに 1 を加算および減算することで、右上、左上、右下、および左下の位置の座標を取得します。グリッドの境界を超えていないかどうかの基本的なチェックを行います。境界を越えると MAS

しかし、グリッド内にいる場合は、これら 4 つの位置で文字を取得し、右上と左下についても同様に、左上と右下に M と S または S または M があるかどうかを確認します。にはそれぞれMとS、またはSまたはMがあります。これは、文字 A の上下にある M と S を斜めに検索します。

したがって、両方の対角線が一致する場合は true を返します。

            S
            A
            M
            X

これが、対角線の MAS を見つけるための簡単な実装です。

ここで、グリッドを反復処理し、行内の文字 (つまり wordList[2]) に A があるかどうかを確認するため、TraverseGrid を少し変更する必要があります。ここで、A がある場合、現在の座標とグリッドを使用して FindMAS 関数を呼び出す必要があります。その関数が true を返した場合は、カウンターをインクリメントします。

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

これがパート 2 の最後の実装であり、横方向の MAS のカウントを取得します。

ここ GitHub で私のソリューションをチェックできます。

結論

Golang の Advent of Code の 4 日目は以上です。何か提案があれば、またどのようにアプローチしたかを教えてください。何か良い解決策はありますか?

コーディングを楽しんでください:)

以上がCode Day n Golang の出現: XMAS と X-MAS の検索の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。