Avènement du Code Day n Golang : recherche de XMAS et X-MAS

Introduction

Passons au jour 4, nous avons un problème de grille devant nous, on nous donne des nombres sous forme de grille, c'est-à-dire des lignes et des colonnes avec des lettres majuscules. Ce que nous devons faire est de trouver le mot XMAS dans n'importe quelle direction (haut, gauche, bas, droite, diagonales), et dans la deuxième partie, nous devons trouver le mot MAS formant un X.

Alors, voyons comment nous pouvons aborder ce problème et le résoudre en Golang.

Vous pouvez consulter mes solutions ici sur GitHub.

Construire la grille

La partie la plus fondamentale du problème réside dans la conversion du texte en grille ou sous forme matricielle. Nous pouvons diviser les lignes en lignes individuelles et ajouter chaque caractère en tant qu'élément dans une liste, et de cette façon nous pouvons avoir une liste de listes de chaînes qui est une structure matricielle ou de type grille (2 dimensions).

Donc, ci-dessous se trouve l'entrée pour le puzzle.

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

Nous devons le convertir en quelque chose comme ça

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

Donc, ceci est une liste de chaînes, on peut dire en golang que c'est une [][]string . Nous pouvons le faire en créant une fonction comme celle-ci :

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
}

La fonction ci-dessus récupère une liste de chaînes et renvoie une liste de chaînes qui sont des lettres individuelles dans la grille.

Nous pouvons lire les octets du fichier et diviser les octets en caractères de nouvelle ligne, puis cela sera utilisé comme entrée pour cette fonction.

Ainsi, une fois l'entrée analysée dans une grille, nous pouvons commencer à réfléchir à la logique réelle de la recherche du mot XMAS.

Partie 1

Donc, dans la première partie, il faut trouver le mot XMAS dans la matrice qui pourrait apparaître :

• avant (comme XMAS)

• en arrière (comme SAMX)

• vers le haut
  

            S
            A
            M
            X

• vers le bas

            X
            M
            A
            S    

• Diagonale vers le haut (droite ou haut gauche)

            S
              A
                M
                  X

            OR
                  S
                A
              M 
            X

• Diagonales vers le bas (droite ou gauche)

                     X
                   M
                 A
               S

            OR

            X
              M
                A
                  S

Donc, il y a 8 directions dans lesquelles XMAS pourrait apparaître dans la grille, il pourrait y en avoir un nombre n. Nous devons en trouver le nombre dans la grille.

Pour aborder cela, nous pouvons soit trouver le premier caractère du mot XMAS puis chercher dans toutes les directions une par une et vérifier si nous trouvons M et si nous avons trouvé M dans l'une des directions, nous continuons d'avancer cette direction et vérifiez s'il y a A et S dans cette direction.

L'approche ressemble à ceci :

• Initialiser le compteur à 0

• Parcourir chaque ligne

  • Parcourir chaque caractère de la ligne

    • Vérifiez si le caractère est égal à X

    • Si le caractère est X→

      • Parcourir toutes les directions (haut, bas, droite, gauche, haut-gauche, haut-droite, bas-gauche, bas-droite)

        • Pour cette direction si nous trouvons que le personnage est M
        • Continuez à avancer dans la même direction pour retrouver A et S de la même façon, si on a trouvé tous les caractères XMAS alors, incrémentez le compteur
        • Sinon, choisissez une autre direction dans la boucle

Cela semble complexe et vaste, mais c'est simple, concentrez-vous sur une chose à la fois et vous pourrez résoudre ce problème facilement.

Donc, pour la mise en œuvre de cela, nous devons d'abord définir quelques choses :

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

Nous avons donc défini la liste des entiers dans les directions qui sont les coordonnées x et y que nous devons ajouter ou soustraire pour arriver à l'emplacement souhaité. C'est fondamentalement comme un vecteur unitaire, il a une distance de 1 et une direction indiquée par ou - indiquant de se déplacer vers la gauche ou la droite pour les coordonnées x et de haut en bas pour les coordonnées y c.

Alors laissez-moi vous expliquer cela plus clairement, disons que je suis en (1,2) dans la grille qui est de dimension 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]
]

Donc, à 2,1 nous avons G , donc nous vérifions quelques directions pour cela

up → 0,-1 → 2 0, 1-1 → 2,0, nous sommes passés en C

droite → 1,0 → 2 1, 1 0 → 3,1 , nous sommes passés à H

en bas, à gauche → -1,1 → 2-1, 1 1 → 1, 2, nous sommes passés à J

Donc, vous voyez l'idée que nous nous déplaçons dans certaines directions en utilisant ces coordonnées.

Nous pouvons les utiliser pour obtenir le prochain saut de direction que nous voulons faire pour trouver si cet élément a le caractère suivant dans le mot que nous recherchons.

Nous allons d'abord écrire une fonction qui fait cela et faire abstraction de la fonction qui vérifie si nous avons trouvé le mot dans la grille.

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
}

La fonction ci-dessus prend une grille et renvoie un entier qui sera le score c'est-à-dire le nombre de mots XMAS trouvés dans la grille/matrice.

Tout d'abord, nous devons parcourir chacune des lignes de la grille, pour chaque ligne, nous parcourons le caractère, nous aurons donc les coordonnées x et y comme index de la grille. Nous devons ensuite vérifier si le caractère actuel est X ou wordList[0] , si tel est le cas, nous parcourons toutes les directions et vérifions si nous pouvons trouver XMAS, c'est-à-dire MAS dans cette direction, si c'est le cas, nous incrémentons le compteur. Qu'est-ce que la fonction FindXMAS, faisons abstraction de cela et passons les x, y, qui sont les coordonnées du mot actuel, 1 qui sera la position du mot du XMAS et dans ce cas, nous avons déjà trouvé X dont nous avons besoin pour trouver MAS dans cette direction. Nous passons la grille et la direction, donc cette fonction retournera vrai ou faux si cette direction contient MAS.

Donc pour itérer :

• Nous parcourons la grille et obtenons la ligne et x comme liste de chaînes et l'index de la ligne actuelle.

• Pour chaque ligne, c'est-à-dire liste de chaînes, nous parcourons la liste de chaînes pour obtenir char et y comme caractère (chaîne) et l'index de ce caractère dans la liste de la chaîne.

• Si nous trouvons que le caractère actuel est égal à X qui est le 0ème index de la liste de mots alors

  • Nous parcourons toutes les directions et appelons la fonction FindXMAS pour vérifier si le mot restant MAS dans cette direction
  • Si on retrouve tous les mots, on incrémente le compteur.

• Donc, on renvoie le compteur au fur et à mesure qu'on compte le nombre de mots XMAS dans la grille/matrice.

Maintenant, nous pouvons implémenter la fonction FindXMAS, qui prend les coordonnées x, y, la position du mot, la direction et la grille, et revenir si le mot est trouvé.

• Tout d'abord, nous prenons les coordonnées x actuelles et ajoutons la composante x de la direction (0ème indice ou premier élément)

• ajouter les coordonnées y actuelles à la composante y de la direction (1er indice ou deuxième élément)

• Si la position du mot, c'est-à-dire l'index du mot ou le mot lui-même dans la fonction actuelle, est égale à la liste de mots, cela signifie qu'il a complètement trouvé le mot recherché

• Nous devons vérifier en ajoutant la direction aux coordonnées x et y, nous ne dépassons pas la largeur et la hauteur de la grille, donc si nous le faisons, nous renvoyons un faux

• Le if final sert à vérifier si le caractère actuel est égal au mot que nous recherchons, il peut s'agir de M, A ou S . Si tel est le cas, nous renvoyons l'appel récursif à la fonction FindXMAS en passant les coordonnées x et y mises à jour et le mot suivant dans la liste de mots, nous gardons la même direction et passons la grille entière.
  

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

Nous avons donc implémenté la fonction FindXMAS, elle reviendra simplement si nous avons trouvé le mot MAS en allant dans une direction particulière en mettant à jour les coordonnées et en vérifiant si le mot à cette position dans la grille est le mot suivant dans MAS liste.

Voici donc à quoi ressemble toute la première partie :

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

Nous prenons les lignes sous forme de liste de chaînes et les transmettons à ConstructGrid et obtenons la grille, enfin, nous appelons TraverseGrid , en passant la grille et en obtenant le score comme le nombre de mots XMAS dans la grille.

C'est tout de la partie 1.

Partie 2

Pour la deuxième partie, nous devons trouver MAS en forme de croix, comme ci-dessous :

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
}

Donc, pour résoudre ce problème, nous pouvons faire une approche similaire mais beaucoup plus simple, il nous suffit de trouver A car il y aura toujours le mot MAS au centre, donc nous vérifions simplement si nous avons A et le coin supérieur gauche , en haut à droite ou en bas à droite, en bas à gauche a M ou S .

Nous obtenons les coordonnées des positions en haut à droite, en haut à gauche, en bas à droite et en bas à gauche en y ajoutant et en soustrayant 1. Nous effectuons une vérification de base si nous ne dépassons pas la limite de la grille. Si on dépasse les limites, on ne trouvera pas le MAS

Mais si nous sommes dans la grille, nous obtenons maintenant le caractère à ces 4 positions, nous vérifions si le haut à gauche et le bas à droite ont M et S ou S ou M, de même pour le haut à droite et le bas à gauche a M et S ou S ou M respectivement. Il s'agit de la recherche diagonale de M et S au-dessus et en dessous du caractère A.

Donc, si les deux diagonales correspondent, nous renvoyons vrai.

            S
            A
            M
            X

C'est donc la mise en œuvre simple pour trouver le MAS de la diagonale.

Maintenant, nous devons changer un peu le TraverseGrid, car nous parcourons simplement la grille et vérifions si nous avons A dans le caractère de la ligne, c'est-à-dire wordList[2]. Maintenant, si nous avons A, nous devons appeler la fonction FindMAS avec les coordonnées actuelles et la grille, si cette fonction renvoie vrai, nous incrémentons le compteur.

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

Donc, c'est l'implémentation finale de la partie 2, nous obtenons le décompte de MAS dans le sens croisé.

Vous pouvez consulter mes solutions ici sur GitHub.

Conclusion

Donc, ça y est depuis le jour 4 de Advent of Code in Golang, faites-moi savoir si vous avez des suggestions et comment vous l'avez abordé. de meilleures solutions ?

Joyeux codage :)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!