Avènement de Code n Golang : faire ou ne pas regex

Inspiré par l'article de Shradha Agarwal sur Byte Size Go :ici : J'ai décidé d'écrire sur mon approche à ce sujet, c'est différent, et j'aimerais la partager. Cet article était bien écrit et la solution était compacte et simple, je recommande également de le lire en premier.

Il s'agit d'une série de blogvent, j'aimerais aussi participer à blogvent mais je ne peux pas être sûr de la terminer.

Introduction

Eh bien, c'est le troisième jour de l'avènement du code 2024, et je l'ai fait en streaming en direct. Je suis en retard de deux jours mais je les travaille un par un. Jusqu’à présent, j’ai appris beaucoup de choses au Go. Passons au jour 3.

Partie 1

La première partie de tout problème AOC semble simple, mais dès que la deuxième partie est révélée, la véritable mise en œuvre commence à vous faire transpirer (si vous n'étiez pas optimiste ou réfléchi)

La première partie de cette journée consistait à analyser une chaîne contenant mul(X,Y) une expression, où X pouvait être n'importe quel nombre à 3 chiffres. Ainsi, il pouvait y avoir plusieurs expressions de ce type dans la chaîne et le but était de multiplier X et Y dans l'expression individuelle et de les additionner.

xmul(2,4)&mul[3,7]!^don't()_mul(5,5)+mul(32,64](mul(11,8)undo()?mul(8,5))

Dans cet exemple ci-dessus, il y a 4 expressions de ce type, et si nous additionnons leurs multiplications, nous obtenons la réponse 161.

Approche

Cela ressemble à un modèle Regex, trouvant un modèle semblable à une expression dans une chaîne. Ainsi, l'approche serait de trouver de telles expressions avec un modèle regex, d'analyser les nombres en nombres entiers et de les multiplier simplement.

Vous pouvez continuer et écrire l'analyseur pour parcourir chaque caractère de la chaîne et analyser les jetons, puis évaluer l'expression. C'est une approche valable, mais j'ai choisi de le faire parce que je ne sais pas honnêtement comment écrire un analyseur, je veux aussi essayer cette solution à la fin.

Mais pour la première partie, une expression régulière rapide semble une bonne idée.

Construire l'expression régulière

La première chose est d'écrire l'expression régulière pour la partie mul(X,Y) qui est la seule section difficile de la première partie. Le reste n'est que de simples mathématiques.

Donc, nous devons trouver mul, puis a (puis n'importe quel nombre de 1 à 3 chiffres, puis , et encore un nombre de 1 à 3 chiffres, et enfin se termine par un )

Cela se traduit par :

mul\((\d{1,3}),(\d{1,3})\) 

Décomposons :

• mul pour capturer le mot littéral mul

• (c'est pour la première parenthèse de l'expression mul() , nous devons échapper au crochet dans une expression régulière si nous voulons la faire correspondre, nous l'utilisons donc avant.

• Ensuite, nous avons un groupe de correspondance (d{1,3}) , ce sera le X dans mul(X,Y) :

  • Un groupe de matchs est comme un groupe de match dans une regex, en gros, si vous souhaitez capturer des parties spécifiques dans l'ensemble du match, alors nous utilisons () pour les regrouper individuellement, ce n'est pas nécessaire mais aide à obtenir le bonnes choses sans frais généraux
  • Dans ce cas, nous utilisons un groupe de correspondance pour capturer un nombre pouvant comporter de 1 à 3 chiffres.
  • L'autre façon d'écrire ceci est ([0-9]{1,3}) , qui ferait également la même chose, (REMARQUE : il y a quelques différences entre [0-9] et d, mais c'est très subtil et n'affectera pas ce puzzle, si vous êtes toujours curieux, je préfère lire cette question StackOverflow)

• On utilise ensuite , pour le séparateur des opérandes X et Y dans l'expression mul(X,Y)

• Nous faisons ensuite de la même manière le match pour Y dans mul(X,Y) avec le groupe de correspondance (d{1,3})

• Enfin, on termine l'expression régulière par le ) pour terminer l'expression

Codez-le

C'est assez simple, nous récupérons la ligne sous forme de chaîne et utilisons la fonction regexp.MustCompile qui nous donne un objet Regexp, qui à son tour est associé à quelques méthodes pour rechercher, faire correspondre, remplacer et d'autres choses qui peuvent être fait avec une expression régulière sur une chaîne.

Une fois que nous avons le mulRegex , nous pouvons utiliser la méthode FindAllStringSubmatch associée à la structure Regexp dans le package regexp. La fonction prend une chaîne sur laquelle exécuter l'expression régulière et le nombre maximum de correspondances à renvoyer. On veut tous les résultats, donc on les passe en -1 pour avoir tous les matchs.

Maintenant, cette méthode renvoie une tranche d'une tranche de chaînes, chaque tranche est une correspondance, et dans chaque tranche, il y a une tranche de chaîne, avec la chaîne correspondante et les groupes de correspondance suivants dans la chaîne le cas échéant.

xmul(2,4)&mul[3,7]!^don't()_mul(5,5)+mul(32,64](mul(11,8)undo()?mul(8,5))

Donc, la fonction ci-dessus renverra quelque chose comme ceci

mul\((\d{1,3}),(\d{1,3})\) 

Ceci est une liste de chaînes, celles-ci ressemblent à des nombres mais ce sont des types de chaînes en Golang.

Maintenant que nous avons cela, nous pouvons créer la partie logique réelle pour obtenir le résultat, qui consiste à analyser ces expressions, à multiplier X et Y et à additionner les résultats pour chacune des expressions.

func FindMulExpression(line string) [][]string {
  mulRegex := regexp.MustCompile(`mul\((\d{1,3}),(\d{1,3})\)`)
  return mulRegex.FindAllStringSubmatch(line, len(line))
}

C'est assez simple, nous parcourons chacune des correspondances, c'est-à-dire une expression mul(X,Y) et analysons chacun X et Y en entiers et les multiplions, le résultat obtenu est ensuite ajouté au score. Nous faisons cela pour chaque expression mul(X,Y) trouvée dans la chaîne(ligne) et renvoyons le score final.

Saisir

Maintenant, l'exemple nous a donné une seule chaîne, mais j'ai réalisé qu'il y avait six lignes dans l'entrée (saisie individuelle), nous devions donc analyser chaque ligne et additionner le score.

N'oubliez pas cela car ce sera critique dans la partie 2, il m'a fallu du temps et des remises en question pour comprendre qu'il faut combiner toutes les lignes pour obtenir le résultat (pas nécessaire dans la partie 1 mais bien sûr dans la partie 2).

Partie 2

C’est généralement là que les choses tournent mal. Du moins pour moi, c'est le cas.

J'ai commencé avec une approche très naïve, avec une boucle éternelle et la recherche de l'index de ce qui est à faire ou à ne pas faire et en supprimant ces sections, puis en boucle jusqu'à ce qu'il ne nous reste plus rien à faire ou à ne pas faire. Cela fonctionnait pour le scénario de test mais a échoué sur l'entrée réelle.

L'approche que j'ai finalement trouvée et qui fonctionnait en modifiant légèrement la même approche.

Approche

Ce que j'ai proposé, c'est de trouver le premier emplacement de correspondance des chaînes don'() et do() dans la chaîne entière, nous prenons cela et supprimons les parties après don't() ou avant do() . De cette façon, nous pouvons réduire la chaîne aux seules expressions mul() valides/activées.

Ainsi, l'approche plus clairement définie sera :

• Trouver l'emplacement (index) des expressions don't() et do()

• Nous devons savoir si la chaîne précédente a été activée ou désactivée, nous conserverons donc un indicateur pour ajouter les expressions activées (une partie de la chaîne) au résultat final

• Si aucun d'entre eux n'est trouvé, renvoyez la chaîne (ligne) telle quelle

• Si nous trouvons l'un ou l'autre alors :

  • Si nous trouvons don't first (don't() apparaît avant do())

    • Si l'indicateur activé est vrai → ajoutez la chaîne avant l'expression don't()
    • Ensuite, activez la valeur false et coupez la partie don't() (De cette façon, nous avons terminé de tout vérifier avant l'expression don't, nous supprimons donc cette partie de la chaîne de ligne)

  • Si nous trouvons do d'abord (do() apparaît avant don't())

    • Si l'indicateur activé est vrai → ajoutez la chaîne avant l'expression do()
    • Ensuite, activez la valeur true et coupez la partie do() (De cette façon, nous avons terminé de tout vérifier avant l'expression do, nous supprimons donc la partie de la chaîne de ligne)

• Nous faisons cela jusqu'à ce qu'il n'y ait plus de chaîne de ligne à vérifier

Code

J'ai utilisé un simple Strings.Index pour obtenir le premier index de correspondance pour la sous-chaîne. Dans ce cas, je veux le premier index correspondant pour don't() et do() . Une fois que nous avons les indices des deux correspondances, nous pouvons parcourir jusqu'à ce qu'il ne nous reste plus aucune chose à faire ou à ne pas faire dans la chaîne.

Si nous avons soit faire, soit ne pas faire, nous ajoutons à la chaîne la partie avant ne pas si activé ou la partie avant faire si activé et activons et désactivons l'indicateur activé en conséquence. À la fin de la boucle, la chaîne résultante n'aura que les parties activées de la ligne/chaîne.

xmul(2,4)&mul[3,7]!^don't()_mul(5,5)+mul(32,64](mul(11,8)undo()?mul(8,5))

Je prends cette fonction et la passe à la fonction de multiplication où j'obtiens les modèles correspondants pour l'expression mul et fais le calcul.

La méthode strings.Index prend une chaîne et une sous-chaîne à rechercher dans cette chaîne et renvoie l'index de la première instance apparaissant de cette sous-chaîne. Avec cela, nous pouvons identifier si la chaîne de ligne contient les expressions do() ou don't(), si ce n'est pas le cas, nous renvoyons simplement la ligne et s'il y en a des instances, nous bouclons et coupons la chaîne avant et après le expressions selon que le drapeau est activé ou désactivé.

Prenons un exemple et parcourons la logique :

xmul(2,4)&mul[3,7]!^don't()_mul(5,5)+mul(32,64](mul(11,8)undo()?mul(8,5))

Nous traitons le résultat avec la même fonction Multiply que nous avons utilisée dans la première partie après l'avoir passé via la fonction FindMulExpression qui renverra toutes les expressions mul dans la chaîne de ligne de résultat.

Attention à l'entrée

L'entrée réelle du puzzle est, je pense, plusieurs lignes, nous devons donc conserver cet état de la ligne dans toutes les lignes restantes. OU, nous pourrions être plus intelligents et créer une seule grande chaîne et la traiter. Les deux sont valides et donneraient les mêmes résultats. Je n'aimais tout simplement pas ajouter une surcharge liée au suivi de tous les états et de toutes les lignes, alors j'ai simplement concaténé toutes les lignes et traité cette seule chaîne.

Conclusion

Il s'agissait essentiellement d'un problème simple, mais si vous n'êtes pas au courant des expressions régulières, vous pourriez vous retrouver dans un terrier de lapin en écrivant votre propre analyseur ou en manipulant des chaînes câblées (tout comme je l'ai fait).

C'est tout pour le troisième jour, je vais faire davantage de résolutions de diffusion en direct au cours du week-end et peut-être aussi la semaine prochaine. Trouvez le code de mes solutions AoC ici sur GitHub.

En attendant,

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!