Aufkommen von Code n Golang: Do or Don't Regex

Inspiriert durch Shradha Agarwals Beitrag zu Byte Size Go :hier: Ich habe beschlossen, über meine Herangehensweise an dieses Thema zu schreiben, es ist anders, und ich möchte es gerne teilen. Dieser Beitrag war gut geschrieben und die Lösung war kompakt und einfach. Ich empfehle, ihn auch zuerst zu lesen.

Das ist eine Blogvent-Reihe, ich würde auch gerne an Blogvent teilnehmen, bin mir aber nicht sicher, ob ich das abschließen werde.

Einführung

Nun, es ist Tag 3 der Einführung von Code 2024 und ich habe es in Live-Streams getan. Ich bin zwei Tage im Rückstand, arbeite sie aber einen nach dem anderen ab. Bisher habe ich viel in Go gelernt. Lasst uns in den dritten Tag eintauchen.

Teil 1

Teil eins zu jedem AOC-Problem scheint einfach zu sein, aber sobald Teil zwei enthüllt wird, beginnt die tatsächliche Umsetzung, Ihnen den Schweiß zu brechen (wenn Sie nicht optimistisch oder nachdenklich waren)

Teil 1 für diesen Tag bestand darin, eine Zeichenfolge zu analysieren, die mul(X,Y) einen Ausdruck enthielt, wobei X eine beliebige dreistellige Zahl sein könnte. Es könnte also mehrere solcher Ausdrücke innerhalb der Zeichenfolge geben und der Zweck bestand darin, X und Y im einzelnen Ausdruck zu multiplizieren und zu addieren.

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

In diesem Beispiel oben gibt es 4 solcher Ausdrücke, und wenn wir deren Multiplikationen addieren, erhalten wir das Ergebnis 161.

Ansatz

Es sieht aus wie ein Regex-Muster, das ein ausdrucksähnliches Muster in einer Zeichenfolge findet. Der Ansatz wäre also, solche Ausdrücke mit einem Regex-Muster zu finden, die Zahlen in ganze Zahlen zu analysieren und sie einfach zu multiplizieren.

Sie könnten fortfahren und den Parser schreiben, der jedes Zeichen in der Zeichenfolge durchläuft, die Token analysiert und dann den Ausdruck auswertet. Das ist ein gültiger Ansatz, aber ich entscheide mich dafür, weil ich nicht weiß, wie man einen Parser schreibt. Ehrlich gesagt möchte ich diese Lösung am Ende auch ausprobieren.

Aber für den ersten Teil scheint ein schneller regulärer Ausdruck eine gute Idee zu sein.

Konstruieren des regulären Ausdrucks

Als Erstes müssen Sie den regulären Ausdruck für den mul(X,Y)-Teil schreiben, der der einzige herausfordernde Abschnitt im ersten Teil ist. Der Rest ist nur einfache Mathematik.

Also müssen wir mul finden, dann a (dann eine beliebige Zahl, die 1 bis 3 Ziffern lang ist, dann und wieder eine Zahl, die 1 bis 3 Ziffern lang ist und schließlich mit a endet)

Das bedeutet:

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

Lass uns aufschlüsseln:

• mul zum Erfassen des wörtlichen Wortes mul

• ( Dies ist für die erste Klammer im Ausdruck mul() . Wir müssen die Klammer in einem regulären Ausdruck maskieren, wenn wir sie anpassen möchten, also verwenden wir davor.

• Dann haben wir eine Übereinstimmungsgruppe (d{1,3}), dies ist das X in mul(X,Y):

  • Eine Match-Gruppe ist wie eine Gruppe eines Matchs in einem regulären Ausdruck. Wenn Sie im Grunde bestimmte Teile im gesamten Match erfassen möchten, verwenden wir (), um sie einzeln zu gruppieren. Dies ist nicht notwendig, hilft aber dabei, das zu erhalten Richtige Dinge ohne Overhead
  • In diesem Fall verwenden wir eine Match-Gruppe zum Erfassen einer Zahl, die 1 bis 3 Ziffern haben kann.
  • Die andere Möglichkeit, dies zu schreiben, ist ([0-9]{1,3}) , was ebenfalls das Gleiche bewirken würde (HINWEIS: Es gibt einige Unterschiede in [0-9] und d, aber das ist Sehr subtil und hat keinen Einfluss auf dieses Rätsel. Wenn Sie immer noch neugierig sind, lese ich lieber diese StackOverflow-Frage)

• Wir verwenden dann , als Trennzeichen der X- und Y-Operanden im mul(X,Y)-Ausdruck

• Wir führen dann auf ähnliche Weise den Match für Y in mul(X,Y) mit der (d{1,3})-Match-Gruppe durch

• Schließlich beenden wir den regulären Ausdruck mit dem ), um den Ausdruck zu beenden

Codieren Sie es

Das ist ganz einfach: Wir erfassen die Zeile als Zeichenfolge und verwenden die Funktion regexp.MustCompile, die uns ein Regexp-Objekt liefert, dem wiederum einige Methoden zum Suchen, Abgleichen, Ersetzen und für andere Dinge zugeordnet sind Dies kann mit einem regulären Ausdruck auf einer Zeichenfolge erfolgen.

Sobald wir mulRegex haben, können wir die FindAllStringSubmatch-Methode verwenden, die der Regexp-Struktur im Regexp-Paket zugeordnet ist. Die Funktion nimmt einen String auf, für den der reguläre Ausdruck ausgeführt werden soll, und die maximale Anzahl von Übereinstimmungen, die zurückgegeben werden sollen. Wir wollen alle Ergebnisse, also übergeben wir sie in -1, um alle Übereinstimmungen zu erhalten.

Diese Methode gibt nun einen Ausschnitt aus einem String-Slice zurück, jeder Ausschnitt ist eine Übereinstimmung, und innerhalb jedes Ausschnitts gibt es einen Ausschnitt aus einer Zeichenfolge, mit der übereinstimmenden Zeichenfolge und den nachfolgenden Übereinstimmungsgruppen in der Zeichenfolge, falls vorhanden.

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

Die obige Funktion gibt also etwa Folgendes zurück

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

Dies ist eine Liste mit Zeichenfolgen. Diese sehen aus wie Zahlen, sind aber in Golang Zeichenfolgentypen.

Jetzt können wir den eigentlichen logischen Teil zum Erhalten des Ergebnisses erstellen, der darin besteht, diese Ausdrücke zu analysieren, X und Y zu multiplizieren und die Ergebnisse für jeden der Ausdrücke zu addieren.

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

Das ist ziemlich einfach: Wir iterieren über jede der Übereinstimmungen, also einen mul(X,Y)-Ausdruck, analysieren X und Y jeweils in ganze Zahlen und multiplizieren sie. Das erhaltene Ergebnis wird dann zur Punktzahl addiert. Wir tun dies für jeden mul(X,Y)-Ausdruck, der in der Zeichenfolge (Zeile) gefunden wird, und geben das Endergebnis zurück.

Eingang

Das Beispiel gab uns nun eine einzelne Zeichenfolge, aber mir wurde klar, dass die Eingabe sechs Zeilen enthielt (einzelne Eingabe), also mussten wir jede Zeile analysieren und die Punktzahl addieren.

Denken Sie daran, denn es wird in Teil 2 von entscheidender Bedeutung sein. Ich habe einige Zeit gebraucht und meine Existenz in Frage gestellt, bis mir klar wurde, dass wir alle Zeilen kombinieren müssen, um das Ergebnis zu erhalten (nicht notwendig in Teil 1, aber auf jeden Fall in Teil 2).

Teil 2

Hier geht normalerweise etwas schief. Zumindest bei mir war das der Fall.

Ich habe mit einem sehr naiven Ansatz begonnen, mit einer Endlosschleife und der Suche nach dem Index für „Do or Don’ts“, dem Entfernen dieser Abschnitte und dem anschließenden Schleifen, bis wir keine Dos und Don’ts mehr haben. Das hat für den Testfall funktioniert, ist aber bei der eigentlichen Eingabe fehlgeschlagen.

Der Ansatz, den ich schließlich gefunden habe, und ich habe daran gearbeitet, den gleichen Ansatz leicht zu optimieren.

Ansatz

Was ich mir ausgedacht habe, ist, die erste Übereinstimmungsposition der Zeichenfolgen don’() und do() in der gesamten Zeichenfolge zu finden. Wir nehmen diese und entfernen die Teile nach don’t() oder vor do() . Auf diese Weise können wir die Zeichenfolge auf nur gültige/aktivierte mul()-Ausdrücke reduzieren.

Der Ansatz wird also klarer definiert:

• Suchen Sie den Speicherort (Index) der don’t()- und do()-Ausdrücke

• Wir müssen nachverfolgen, ob die vorherige Zeichenfolge aktiviert oder deaktiviert war, und behalten daher ein Flag bei, um die aktivierten Ausdrücke (Teil der Zeichenfolge) an das Endergebnis anzuhängen

• Wenn keine davon gefunden wird, geben Sie die Zeichenfolge (Zeile) so zurück, wie sie ist

• Wenn wir eines davon gefunden haben, dann:

  • Wenn wir don’t zuerst finden, erscheint (don’t() vor do())

    • Wenn das aktivierte Flag wahr ist → fügen Sie die Zeichenfolge vor dem don’t()-Ausdruck an
    • Dann schalten Sie die Option „Aktiviert“ auf „Falsch“ um und entfernen Sie den Teil „don’t()“. (Auf diese Weise haben wir die Prüfung aller Dinge vor dem Don't-Ausdruck abgeschlossen und entfernen diesen Teil aus der Zeilenzeichenfolge.)

  • Wenn wir do zuerst finden (do() erscheint vor don’t())

    • Wenn das aktivierte Flag wahr ist → fügen Sie die Zeichenfolge vor dem do()-Ausdruck an
    • Dann schalten Sie „Enabled“ auf „True“ um und entfernen Sie den do()-Teil (Auf diese Weise haben wir die Überprüfung aller Dinge vor dem do-Ausdruck abgeschlossen und entfernen den Teil aus der Zeilenzeichenfolge.)

• Wir tun dies, bis keine zu prüfende Zeilenfolge mehr vorhanden ist

Code

Ich habe den einfachen Strings.Index verwendet, um den ersten Übereinstimmungsindex für den Teilstring zu erhalten. In diesem Fall möchte ich den ersten Übereinstimmungsindex für don’t() und do() . Sobald wir die Indizes beider Übereinstimmungen haben, können wir so lange iterieren, bis in der Zeichenfolge keine Gebote oder Verbote mehr übrig sind.

Wenn wir entweder „do“ oder „don't“ haben, hängen wir an die Zeichenfolge den Teil vor „don't“ an, wenn aktiviert, oder den Teil vor „do“, wenn aktiviert, und schalten das aktivierte Flag entsprechend ein und aus. Am Ende der Schleife enthält die Ergebniszeichenfolge nur noch die aktivierten Teile der Zeile/Zeichenfolge.

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

Ich nehme diese Funktion und übergebe sie an die Multiplikationsfunktion, wo ich die passenden Muster für den mul-Ausdruck erhalte und die Berechnung durchführe.

Die Methode strings.Index nimmt eine Zeichenfolge und eine Teilzeichenfolge auf, um sie in dieser Zeichenfolge zu finden, und gibt den Index der ersten vorkommenden Instanz dieser Teilzeichenfolge zurück. Damit können wir feststellen, ob die Zeilenzeichenfolge die Ausdrücke do() oder don't() enthält. Wenn dies nicht der Fall ist, geben wir einfach die Zeile zurück und wenn es Instanzen davon gibt, führen wir eine Schleife durch und kürzen die Zeichenfolge vor und nach dem Ausdrücke abhängig davon, ob das Flag aktiviert oder deaktiviert ist.

Nehmen wir ein Beispiel und gehen wir die Logik durch:

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

Wir verarbeiten das Ergebnis mit derselben Multiplikationsfunktion, die wir im ersten Teil verwendet haben, nachdem wir es durch die FindMulExpression-Funktion geleitet haben, die alle mul-Ausdrücke in der Ergebniszeilenzeichenfolge zurückgibt.

Kopf hoch mit der Eingabe

Die eigentliche Eingabe des Puzzles besteht meiner Meinung nach aus mehreren Zeilen, daher müssen wir diesen Status der Zeile in allen verbleibenden Zeilen beibehalten. ODER wir könnten schlauer sein und eine einzige große Zeichenfolge erstellen und diese verarbeiten. Beide sind gültig und würden die gleichen Ergebnisse liefern. Ich hatte einfach keine Lust, den Überblick über alle Zustände und Zeilen zu verlieren, also habe ich einfach alle Zeilen verkettet und diese einzelne Zeichenfolge verarbeitet.

Abschluss

Das war im Grunde ein einfaches Problem, aber wenn Sie sich mit Regex nicht auskennen, könnten Sie in die Versuchung geraten, Ihren eigenen Parser zu schreiben oder kabelgebundene String-Manipulationen durchzuführen (genau wie ich).

Das war's vom dritten Tag. Ich werde am Wochenende und möglicherweise auch in der nächsten Woche weitere Livestream-Lösungen durchführen. Den Code für meine AoC-Lösungen finden Sie hier auf GitHub.

Bis dahin,

Viel Spaß beim Programmieren :)

Das obige ist der detaillierte Inhalt vonAufkommen von Code n Golang: Do or Don't Regex. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!