Code n Golang の出現: 正規表現を行うか行わないか

Byte Size Go に関する Shradha Agarwal の投稿に触発されて、こちら: これに対する私のアプローチについて書くことにしました。それは異なっており、共有したいと思います。その投稿はよく書かれており、ソリューションはコンパクトでシンプルでした。最初にそれも読むことをお勧めします。

これは blogvent シリーズです。私も blogvent に参加したいと思っていますが、これを完了できるかどうかはわかりません。

導入

さて、コード 2024 の出現から 3 日目ですが、ライブ ストリームでそれを行ってきました。 2日遅れていますが、一つずつ取り組んでいます。これまで、私は囲碁について多くのことを学びました。 3 日目について詳しく見ていきましょう。

パート 1

AOC の問題のパート 1 は簡単そうに見えますが、パート 2 が明らかになるとすぐに、実際の実装では汗をかき始めます (楽観的または思慮深い人でなければ)

この日のパート 1 は、mul(X,Y) という式を含む文字列を解析することでした。ここで、X は任意の 3 桁の数字です。したがって、文字列内にそのような式が複数存在する可能性があり、その目的は、個々の式の X と Y を乗算して合計することでした。

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

上のこの例には、そのような式が 4 つあり、それらの乗算を追加すると、答えは 161 になります。

アプローチ

これは正規表現パターンのように見え、文字列内で式のようなパターンを見つけます。したがって、このアプローチは、正規表現パターンを使用してそのような式を見つけ、数値を整数に解析し、それらを単純に乗算することになります。

文字列内の各文字を反復処理してトークンを解析し、式を評価するパーサーを作成することもできます。それは有効なアプローチですが、正直なところ、パーサーの書き方がわからないので、これを選択しました。最後にその解決策も試したいと思っています。

ただし、最初の部分では、簡単な正規表現を使用するのが良いと思われます。

正規表現の構築

最初に、パート 1 で唯一の難しいセクションである mul(X,Y) 部分の正規表現を作成します。残りは単純な計算です。

したがって、mul、次に a (次に 1 ～ 3 桁の長さの任意の数値、次に 、そして再び 1 ～ 3 桁の長さで最後に a で終わる数値) を見つける必要があります

これは次のようになります:

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

詳しく見てみましょう:

• リテラル単語 mul をキャプチャするための mul

• (これは式 mul() の最初の括弧用です。一致させたい場合は正規表現で括弧をエスケープする必要があるため、その前に使用します。

• 次に、一致グループ (d{1,3}) があり、これは mul(X,Y) の X になります:

  • 一致グループは、正規表現における一致のグループのようなものです。基本的に、一致全体の特定の部分をキャプチャしたい場合は、() を使用してそれらを個別にグループ化します。これは必須ではありませんが、オーバーヘッドなしで正しいことを行う
  • この場合、1 ～ 3 桁の数値を取得するために一致グループを使用しています。
  • これを書くもう 1 つの方法は ([0-9]{1,3}) です。これも同じことを行います (注: [0-9] と d にはいくつかの違いがありますが、それは非常に微妙であり、このパズルには影響しません。それでも興味がある場合は、この StackOverflow の質問を読むことをお勧めします)

• 次に、mul(X,Y) 式の X オペランドと Y オペランドの区切り文字として , を使用します

• 次に、(d{1,3}) 一致グループを使用して、mul(X,Y) の Y の一致を同様に実行します

• 最後に、正規表現を ) で終了し、式を終了します

コード化する

これは非常に簡単です。行を文字列として取得し、regexp.MustCompile 関数を使用して Regexp オブジェクトを取得します。この関数には、検索、一致、置換などを行うためのいくつかのメソッドが関連付けられています。文字列の正規表現を使用して実行します。

mulRegex を取得したら、regexp パッケージ内の Regexp 構造体に関連付けられた FindAllStringSubmatch メソッドを使用できます。この関数は、正規表現を実行する文字列と、返される一致の最大数を受け取ります。すべての結果が必要なので、すべての一致を取得するには -1 を渡します。

このメソッドは文字列のスライスのスライスを返します。各スライスは一致し、各スライス内には文字列のスライスがあり、一致した文字列と、文字列内にその後の一致グループがある場合はそれが含まれます。

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

したがって、上記の関数は次のようなものを返します

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

これは文字列のリストのリストです。これらは数字のように見えますが、Golang では文字列型です。

これで、結果を取得する実際のロジック部分を作成できます。これは、これらの式を解析し、X と Y を乗算し、各式の結果を加算することです。

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

これは非常に簡単です。各一致、つまり 1 つの mul(X,Y) 式を反復し、X と Y をそれぞれ整数に解析して乗算し、得られた結果がスコアに追加されます。 string(line) 内で見つかった各 mul(X,Y) 式に対してこれを実行し、最終スコアを返します。

入力

この例では 1 つの文字列が示されていますが、入力 (個々の入力) に 6 行あることに気付きました。そのため、各行を解析してスコアを合計する必要がありました。

これはパート 2 で重要になるため、覚えておいてください。結果を得るにはすべての行を結合する必要があることに気づくまでに、少し時間がかかり、自分の存在に疑問を抱きました (パート 1 では必要ありませんが、パート 2 では必ず必要です)。

パート 2

通常、ここで問題が発生します。少なくとも私にとってはそうでした。

私は非常に単純なアプローチから始めました。永久ループで、「やるべきこと」または「やらないこと」のインデックスを見つけてそれらのセクションを取り除き、「やるべきこと」と「やらないこと」がなくなるまでループするというものでした。これはテストケースでは機能していましたが、実際の入力では失敗しました。

私が最終的に思いついたアプローチで、同じアプローチを少し調整して取り組んでいました。

アプローチ

私が思いついたのは、文字列全体の中で don’() 文字列と do() 文字列が最初に一致する位置を見つけて、それを取得し、 don’t() の後または do() の前の部分を削除することです。こうすることで、文字列を有効/有効な mul() 式のみにトリミングできます。

したがって、より明確に定義されたアプローチは次のようになります。

• don't() 式と do() 式の場所 (インデックス) を見つけます

• 前の文字列が有効か無効かを追跡する必要があるため、有効な式 (文字列の一部) を最終結果に追加するフラグを保持します

• どれも見つからない場合は、文字列(行)をそのまま返します

• それらのいずれかを見つけた場合:

  • 最初に don't が見つかった場合 (don't() は do() の前に現れます)

    • 有効フラグが true の場合 → don't() 式の前に文字列を追加します
    • 次に、enabled を false に切り替え、don't() 部分を削除します。 (これで don't 式の前のすべてのチェックが完了したので、その部分を行文字列から削除します)

  • do が最初に見つかった場合 (do() が don't() の前に出現します)

    • 有効フラグが true の場合 → do() 式の前に文字列を追加します
    • 次に、enabled を true に切り替え、do() 部分をトリミングします。 (これで do 式までのチェックが完了したので、行文字列からその部分を削除します)

• チェックすべき行文字列がなくなるまでこれを行います

コード

単純な Strings.Index を使用して、部分文字列の最初の一致インデックスを取得しました。この場合、 don’t() と do() の最初の一致インデックスが必要です。両方の一致のインデックスを取得したら、文字列内に「すべき」または「してはいけない」がなくなるまで反復できます。

do または don't がある場合、有効な場合は don't の前の部分を文字列に追加し、有効な場合は do の前の部分を文字列に追加し、それに応じて有効なフラグのオンとオフを切り替えます。ループの終わりまでに、結果の文字列には行/文字列の有効な部分のみが含まれます。

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

この関数を乗算関数に渡し、そこで mul 式に一致するパターンを取得して計算を行います。

strings.Index メソッドは、文字列とその文字列内で検索する部分文字列を受け取り、その部分文字列の最初に発生したインスタンスのインデックスを返します。これにより、行文字列に do() または don't() 式が含まれているかどうかを識別できます。含まれていない場合は、単純にその行を返し、それらのインスタンスがある場合は、その前後の文字列をループしてトリミングします。フラグが有効か無効かに応じた式。

例を挙げてロジックを見てみましょう:

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

結果行文字列内のすべての mul 式を返す FindMulExpression 関数に結果を渡した後、最初の部分で使用したのと同じ Multiply 関数を使用して結果を処理します。

入力に注意を払う

パズルの実際の入力は複数行であると思います。そのため、残りのすべての行でこの行の状態を保持する必要があります。あるいは、もっと賢く、単一の大きな文字列を作成してそれを処理することもできます。どちらも有効であり、同じ結果が得られます。すべての状態と行を追跡するオーバーヘッドを追加したくなかったので、すべての行を連結してその 1 つの文字列を処理しました。

結論

これは本質的には単純な問題ですが、正規表現を知らないと、(私がやったのと同じように) 独自のパーサーを作成したり、有線で文字列を操作したりするというウサギの穴に陥る可能性があります。

3 日目はここまでです。週末とおそらく来週もライブ ストリームの解決をさらに行う予定です。私の AoC ソリューションのコードは、GitHub で見つけてください。

それまでは

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

以上がCode n Golang の出現: 正規表現を行うか行わないかの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。