Einführung des Code Day n Golang: Suche nach XMAS und X-MAS

Einführung

An Tag 4 haben wir ein Rasterproblem vor uns. Wir erhalten einige Zahlen in Form eines Rasters, d. h. einige Zeilen und Spalten mit einigen Großbuchstaben. Was wir tun müssen, ist, das Wort XMAS in einer beliebigen Richtung (oben, links, unten, rechts, diagonal) zu finden, und im zweiten Teil müssen wir das Wort MAS finden, das ein X bildet.

Also, mal sehen, wie wir das angehen und in Golang lösen können.

Sie können meine Lösungen hier auf GitHub ansehen.

Aufbau des Rasters

Der grundlegendste Teil des Problems besteht darin, den Text tatsächlich in eine Raster- oder Matrixform umzuwandeln. Wir können die Zeilen in einzelne Zeilen aufteilen und jedes Zeichen als Element in einer Liste anhängen. Auf diese Weise können wir eine Liste mit Zeichenfolgen erstellen, die eine Matrix- oder gitterartige (zweidimensionale) Struktur darstellt.

Also, unten ist die Eingabe für das Rätsel.

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

Wir müssen es in so etwas umwandeln

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

Das ist also eine Liste von Strings, wir können in Golang sagen, dass es sich um einen [][]string handelt. Wir können das tun, indem wir eine Funktion wie diese erstellen:

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
}

Die obige Funktion nimmt eine Liste von Zeichenfolgen auf und gibt eine Liste von Zeichenfolgen zurück, bei denen es sich um einzelne Buchstaben im Raster handelt.

Wir können die Dateibytes lesen und die Bytes in Zeilenumbruchzeichen aufteilen, und dann wird dies als Eingabe für diese Funktion verwendet.

Sobald die Eingabe also in ein Raster geparst ist, können wir anfangen, über die eigentliche Logik nachzudenken, mit der das Wort XMAS darin gefunden werden soll.

Teil 1

Also müssen wir im ersten Teil das Wort XMAS in der Matrix finden, das erscheinen könnte:

• vorwärts (als XMAS)

• rückwärts (als SAMX)

• nach oben
  

            S
            A
            M
            X

• nach unten

            X
            M
            A
            S    

• Diagonal nach oben (rechts oder oben links)

            S
              A
                M
                  X

            OR
                  S
                A
              M 
            X

• Diagonalen nach unten (rechts oder links)

                     X
                   M
                 A
               S

            OR

            X
              M
                A
                  S

Es gibt also 8 Richtungen, in denen XMAS im Raster erscheinen könnte, es könnte n Anzahl dieser XMAS geben. Wir müssen die Anzahl davon im Raster ermitteln.

Um dies zu erreichen, können wir entweder das erste Zeichen im Wort XMAS finden und dann nacheinander in alle Richtungen suchen und prüfen, ob wir M finden. Wenn wir M in einer der Richtungen gefunden haben, gehen wir weiter in diese Richtung und prüfen Sie, ob in dieser Richtung A und S vorhanden sind.

Der Ansatz sieht so aus:

• Zähler auf 0 initialisieren

• Jede Zeile durchlaufen

  • Jedes Zeichen in der Zeile durchlaufen

    • Überprüfen Sie, ob das Zeichen gleich X ist

    • Wenn das Zeichen X ist→

      • Iterieren Sie alle Richtungen (oben, unten, rechts, links, oben-links, oben-rechts, unten-links, unten-rechts)

        • Für diese Richtung, wenn wir feststellen, dass es sich bei dem Charakter um M handelt
        • Bewegen Sie sich weiter in die gleiche Richtung, um A und S auf ähnliche Weise zu finden. Wenn wir dann alle Zeichen XMAS gefunden haben, erhöhen Sie den Zähler
        • Andernfalls wählen Sie eine andere Richtung in der Schleife

Das sieht komplex und umfangreich aus, ist aber einfach. Konzentrieren Sie sich auf eine Sache nach der anderen und Sie können das Problem leicht lösen.

Für die Umsetzung müssen wir also zunächst ein paar Dinge definieren:

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

Also haben wir die Liste der ganzen Zahlen in den Richtungen definiert, die die x- und y-Koordinaten sind, die wir addieren oder subtrahieren müssen, um an die gewünschte Position zu gelangen. Es ist im Grunde wie ein Einheitsvektor, es hat einen Abstand von 1 und eine durch oder angegebene Richtung – was bedeutet, dass man sich für x-Koordinaten nach links oder rechts und für y-Koordinaten nach oben und unten bewegt.

Lassen Sie mich das genauer erklären. Nehmen wir an, ich befinde mich bei (1,2) im Raster, das die Dimension 4x4 hat.

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

Bei 2,1 haben wir also G , also prüfen wir einige Anweisungen dafür

aufwärts → 0,-1 → 2 0, 1-1 → 2,0, wir sind zu C übergegangen

rechts → 1,0 → 2 1, 1 0 → 3,1 , wir sind zu H übergegangen

unten, links → -1,1 → 2-1, 1 1 → 1, 2, wir sind zu J übergegangen

Sie verstehen also, dass wir uns anhand dieser Koordinaten in einige Richtungen bewegen.

Wir können diese verwenden, um den nächsten Richtungssprung zu ermitteln, den wir machen möchten, um herauszufinden, ob dieses Element das nächste Zeichen in dem Wort hat, das wir suchen.

Wir werden zuerst eine Funktion schreiben, die dies tut, und die Funktion abstrahieren, die prüft, ob wir das Wort im Raster gefunden haben.

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
}

Die obige Funktion nimmt ein Raster auf und gibt eine Ganzzahl zurück, die die Punktzahl darstellt, d. h. die Anzahl der im Raster/in der Matrix gefundenen Wörter XMAS.

Zuerst müssen wir jede Zeile im Raster durchlaufen. Für jede Zeile iterieren wir über das Zeichen, sodass wir x- und y-Koordinaten als Index des Rasters haben. Wir müssen dann prüfen, ob das aktuelle Zeichen X oder wordList[0] ist. Wenn das der Fall ist, durchlaufen wir alle Richtungen und prüfen, ob wir XMAS, d. h. MAS, in dieser Richtung finden können. Wenn ja, erhöhen wir den Zähler. Was ist die FindXMAS-Funktion? Abstrahieren wir das und übergeben x, y, die Koordinaten des aktuellen Wortes, 1, die Wortposition von XMAS, und in diesem Fall haben wir bereits X gefunden, das wir brauchen MAS in dieser Richtung zu finden. Wir übergeben das Gitter und die Richtung, sodass diese Funktion wahr oder falsch zurückgibt, wenn diese Richtung MAS enthält.

Um es zu wiederholen:

• Wir iterieren über das Raster und erhalten Zeile und x als Liste der Zeichenfolgen und Index der aktuellen Zeile.

• Für jede Zeile, d. h. eine Liste von Zeichenfolgen, durchlaufen wir die Liste der Zeichenfolgen, um char und y als Zeichen (Zeichenfolge) und den Index dieses Zeichens in der Liste der Zeichenfolge zu erhalten.

• Wenn wir feststellen, dass das aktuelle Zeichen gleich X ist, was der 0. Index der Wortliste ist, dann

  • Wir durchlaufen alle Richtungen und rufen die Funktion FindXMAS auf, um zu prüfen, ob das verbleibende Wort MAS in dieser Richtung ist
  • Wenn wir alle Wörter finden, erhöhen wir den Zähler.

• Also geben wir den Zähler zurück, während wir die Anzahl der Wörter XMAS im Raster/in der Matrix zählen.

Jetzt können wir die FindXMAS-Funktion implementieren, die x- und y-Koordinaten, die Wortposition, die Richtung und das Raster aufnimmt und zurückgibt, wenn das Wort gefunden wird.

• Zuerst nehmen wir die aktuellen x-Koordinaten und fügen die x-Komponente der Richtung hinzu (0. Index oder erstes Element)

• aktuelle Y-Koordinaten zur Y-Komponente der Richtung hinzufügen (1. Index oder zweites Element)

• Wenn die Wortposition, d. h. der Wortindex oder das Wort selbst in der aktuellen Funktion, mit der Wortliste übereinstimmt, bedeutet dies, dass das gesuchte Wort vollständig gefunden wurde

• Wir müssen durch Hinzufügen der Richtung zu den x- und y-Koordinaten überprüfen, ob wir die Breite und Höhe des Gitters nicht überschreiten. Wenn wir das tun, geben wir ein falsches Ergebnis zurück

• Das letzte If dient der Überprüfung, ob das aktuelle Zeichen mit dem gesuchten Wort übereinstimmt. Es könnte M, A oder S sein. Wenn ja, rufen wir rekursiv die FindXMAS-Funktion auf, indem wir die aktualisierten x- und y-Koordinaten und das nächste Wort in der Wortliste übergeben. Wir behalten die Richtung bei und übergeben das gesamte Raster.
  

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

Also haben wir die FindXMAS-Funktion implementiert. Diese gibt nur dann zurück, wenn wir das MAS-Wort gefunden haben, indem wir in eine bestimmte Richtung gegangen sind, indem wir die Koordinaten aktualisiert und überprüft haben, ob das Wort an dieser Position im Raster das nächste Wort in MAS ist Liste.

So sieht also der gesamte erste Teil aus:

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

Wir nehmen die Zeilen als Liste von Zeichenfolgen auf und übergeben diese an ConstructGrid und erhalten das Raster. Schließlich rufen wir TraverseGrid auf, indem wir das Raster übergeben und die Punktzahl als Anzahl der Wörter XMAS im Raster erhalten.

Das war's ab Teil 1.

Teil 2

Für Teil zwei müssen wir MAS in der Kreuzform finden, wie unten:

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
}

Um dieses Problem zu lösen, können wir einen ähnlichen Ansatz verfolgen, aber viel einfacher: Wir müssen nur A finden, da in der Mitte immer das Wort MAS steht, also prüfen wir einfach, ob wir A und oben links haben , oben rechts oder unten rechts, unten links hat M oder S .

Wir erhalten die Koordinaten der Positionen oben rechts, oben links, unten rechts und unten links, indem wir 1 davon addieren und davon subtrahieren. Wir führen eine grundlegende Prüfung durch, um sicherzustellen, dass wir nicht über die Grenzen des Gitters hinausschießen. Wenn wir über die Grenzen hinausschießen, werden wir das MAS nicht finden

Aber wenn wir uns innerhalb des Rasters befinden, erhalten wir nun das Zeichen an diesen 4 Positionen, wir prüfen, ob oben links und unten rechts M und S oder S oder M haben, ähnlich für oben rechts und unten links hat M und S bzw. S oder M. Dies ist die diagonale Suche nach M und S über und unter dem Zeichen A.

Wenn also beide Diagonalen übereinstimmen, geben wir true zurück.

            S
            A
            M
            X

Das ist also die einfache Implementierung zum Ermitteln des MAS der Diagonale.

Jetzt müssen wir das TraverseGrid ein wenig ändern, da wir einfach über das Raster iterieren und prüfen, ob das Zeichen in der Zeile ein A enthält, d. h. wordList[2]. Wenn wir nun A haben, müssen wir die FindMAS-Funktion mit den aktuellen Koordinaten und dem Gitter aufrufen. Wenn diese Funktion „true“ zurückgibt, erhöhen wir den Zähler.

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

Das ist also die endgültige Implementierung von Teil 2, wir erhalten die Anzahl der MAS in Querrichtung.

Sie können meine Lösungen hier auf GitHub ansehen.

Abschluss

Das war's ab Tag 4 von Advent of Code in Golang. Lassen Sie mich wissen, ob Sie Vorschläge haben und wie Sie daran vorgegangen sind. Gibt es bessere Lösungen?

Viel Spaß beim Programmieren :)

Das obige ist der detaillierte Inhalt vonEinführung des Code Day n Golang: Suche nach XMAS und X-MAS. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!