Advent of CodeをAlteryxでやってみる2023_12日目

Advent of code
2023.12.13

※過去記事はこちら。AlteryxユーザーのためのAdvent of Codeの始め方、１日目、２日目、３日目、４日目、５日目、６日目、７日目、８日目、９日目、10日目、11日目。

クリアできました！！（2023/12/16）

第拾弐話　「Hot Springs」

未解決事件です！！　→　クリアできました！

タイトルは「温泉」。難易度はぬるくなかった。

ストーリーとしては、温泉に到着した、ということになっています。しかし、溶岩が不足しているとのことで暖かくないようです。溶岩の調子を見に行く必要があるのですが、そこに行くためにはバネ（スプリング）を使う必要があります。※Springがダブルミーニングでややこしいですね

インプットとしては以下のとおりです。動いているバネが「.」（ドット）、壊れているバネが「#」で示された以下の地図があります。「?」はこわれているのか動いているのかがわからない状態を示しています。ただ、後ろに続く数字は、壊れているバネの個数が書いています。3と記載されていれば、3個連続して壊れていることを示しています。

???.### 1,1,3
.??..??...?##. 1,1,3
?#?#?#?#?#?#?#? 1,3,1,6
????.#...#... 4,1,1
????.######..#####. 1,6,5
?###???????? 3,2,1

例として、下の一行目の状態は10通りの状態を取りえます。

?###???????? 3,2,1
.###.##.#...
.###.##..#..
.###.##...#.
.###.##....#
.###..##.#..
.###..##..#.
.###..##...#
.###...##.#.
.###...##..#
.###....##.#

100行存在する入力データに対して、何パターンの状態を取りうるかを計算します。

Part2は、入力データに対して５倍となります。つまり、

.# 1

というものの本当の状態は、

.#?.#?.#?.#?.# 1,1,1,1,1

となります。

これで取りうるパターンを求めます。

・ネ

・

・タ

・

・バ

・

・レ

Part1,2を解いてみる

Part1はブルートフォースで解けました（8秒で解けます）。Part2は天文学的な数値になり、現時点では解けていません。

一旦未解決事件として筆を置きたいと思います。

Part1は普通に解けます。

まず、インプットデータとして、以下のようなものを作ります。NumはInput2の数値を足したものです。

方法としては、正規表現ツールで、最初の?を#に変えたものと.に変えたものを2つ作ります。その後、生成された各パターンをチェックしていきます。なるべく途中で不要なパターンは削除して反復しないことを推奨します。

今回はチェックするのに？が入っていると確定的ではなくなりますが、とりあえず.を全部削除した後に、Numと長さを比較することで#の数が多すぎるものや明らかに不足するものをフィルタで取り除いています。

また、以下の正規表現で合わないパターンは捨てられます。

REGEX_Match("."+[Input1], TrimLeft(Replace(","+[Input2]+"}", ",", "}[\.?]+.*?[#?]{"),"}")+".*")

それらを取り入れたマクロが以下のような感じになります。

最終的なワークフローは以下の通り、、、比較的シンプルですよね。

さて、Part2です。Part2は、？の数が増えた分パターンが非常に増えるため、普通に反復すると到底終わりません。そのためパターン数をカウントする機能を組み込んでレコード数を減らす必要があります。

そして、私はPart1マクロをそのまま使おうとしたのですが、全く進みません。これ、ちょっとからくりがありました。検証のためにAMP OFFにしたときに初めてわかったのですが、正規表現式が複雑になりすぎていて結果が出ていなかったようです（しかもめちゃ遅くなる）。

少し見てみましょう。下のテーブルのRegEx_Formulaという右から2つ目のフィールドが実際に使われている正規表現の式です。

一番上のレコードを取り出してみましょう。めちゃくちゃ長いです。

[\.?]+.*?[#?]{1}[\.?]+.*?[#?]{1}[\.?]+.*?[#?]{3}[\.?]+.*?[#?]{1}[\.?]+.*?[#?]{1}[\.?]+.*?[#?]{3}[\.?]+.*?[#?]{1}[\.?]+.*?[#?]{1}[\.?]+.*?[#?]{3}[\.?]+.*?[#?]{1}[\.?]+.*?[#?]{1}[\.?]+.*?[#?]{3}[\.?]+.*?[#?]{1}[\.?]+.*?[#?]{1}[\.?]+.*?[#?]{3}.*

レコード１と２は同じ式なのですが、入力データがレコード２の方が複雑な用で、正規表現ちゃんがGive upして結果がREGEX_MATCH_ResultのところがNullになっています。

この状態だと、以下のようなメッセージが出ます。

しかし、これ、、、マクロ内だと出ないんですよね・・・。これでドはまりしていました。

結論的には、正規表現のみで複雑なものをチェックするとNGということで、地道にチェックするようにマクロを作り変える必要がありました。

Part2マクロは以下の手順に従っています。

  1. ？を.と＃に変換する
  2. 決定的なパターンを自力で作る＆一番左の数字に対してすでに確定していればその部分は削除する
  3. Numを作り直す
  4. パターンチェックで合わないものは捨てる
  5. グルーピングしてカウントを合計してレコード数を減らす

マクロ全景は以下のとおりです。

ブロック１：？を．と＃に変換しています

その他、

  • 複数の.が並んでいたら、.一つにします
  • #をカウントして、Numを超えていたり明らかに不足していればマッチしないので削除します（比較のときは？を残したり、残さなかったりしてカウントしています）
  • 一番左の塊に対して簡易的なパターンチェックを行っています。例えば、「##?.」で数値が3の場合OKとし（?が#のケースがOKなので）、「##.」の場合は不足しているので削除します。

ブロック２：決定的なパターンを自力で判別して作っています。また、左側の塊で不要なところは捨てています。これにより大きくパターンを削減できています

例として、「###?.#」で「3,1」の場合、？は「.」にしかならないので、？をドットにして左側の「＃＃＃」は削除し、「3,1」も「1」にしてしまいます。確定した左側の部分を切り詰めることでパターン数を減らすようにしています。この「確定した左側の部分を切る詰める」のがポイントです。

ブロック３：Numを再作成しています。ばらして合計を取るだけです。

ブロック４：複雑な正規表現を使わずにNGパターンを捨てます

これ、？がない確定したパターンと？が入ってる未確定のパターンでチェックロジックをわけています。？がないパターンはInput1,2をバラして数を照合するだけです。？があるとそれができないので、左側から見て確定している部分まででチェックしています。

ブロック５：グルーピングしてカウントを合計することでレコード数を減らしています

ワークフロー全景は以下のような感じでシンプルです。

まとめ

  • ４日間悩んでようやく完了しました。
  • 今回は複雑すぎる正規表現がマクロ内でいつのまにか息をしていなかった問題で大きく時間を取られました。正規表現を使っていなければ意外ともう少し早くできたのかもしれません。とはいえ、うまく行かないときはロジックをイチから見直すようなアプローチも必要かもしれません（過去のAoCでもどうしてもデバッグがうまく行かないときは作り直したことがあります）。
  • Private Leaderボードで、Part1は12位総合で14位となりました。最速の人で、Part1は30分くらいで解いていますが、Part2は1時間12分とのことです。自分は苦戦しましたが、意外と普通に解いてる人もいるんですね。
  • テストデータだと0.6秒で完了しますが、本番データだと1分くらいかかります。途中反復レコード数が2万超えると結構苦しそうな感じですが、50超えてくるとあっというまに最後まで完走します。

コメント

タイトルとURLをコピーしました