※過去記事はこちら。AlteryxユーザーのためのAdvent of Codeの始め方、１日目、２日目、３日目、４日目、５日目、６日目、７日目、８日目、９日目、１０日目、１１日目、１２日目、１３日目、１４日目、１５日目、１６日目、１７日目、１８日目、１９日目、２０日目、２１日目、２２日目、２３日目
２４日目です。２１のPart2が解けたときの画像を採用しています。
タイトルは、「Blizzard Basin」。吹雪の盆地、ですかね。Basinとか馴染みがない単語で・・・。
今回の問題も、地図問題ですが、エルフが吹雪を避けてゴールに到達する問題です。
サンプルの入力データとしては、以下のようになっています。
#.#####
#.....#
#>....#
#.....#
#...v.#
#.....#
#####.#＃は壁。「>」「v」はブリザードの地点と移動方向を示しています。実際の小さいサンプルを再度お見せします（スタート地点SとゴールGも記載しておきます）。
#S######
#>>.<^<#
#.<..<<#
#>v.><>#
#<^v^^>#
######G#ブリザードは矢印の方向に動いています。壁に当たると逆側で新たなブリザードが生成されます。ブリザードのあるところには入れないので、避けてゴールまで行く必要があります。ルールは非常にシンプルです。
Part1では最短でゴールに辿り着くまでの時間（経過ターン）をカウントします。
Part2では、一度ゴールに行った後、エルフがおやつを忘れてたとのことで、一度スタート地点に戻ってから再度ゴールに向かう最短時間を出す問題です（エルフ死ねばいいのに、、、）
・ネ
・
・タ
・
・バ
・
・レ
解いてみる
この問題、常に動く方向が一つとは限りません。例えば左右もしくは立ち止まれる場合に、動いた先でブリザードに囲まれて詰む場合もあったりします。最善手、というのがその瞬間ではわからず、すべての動き方をシミュレートする必要があります。
最初、特定のアルゴリズムで（例えば右下になるべく行くようにする）進めたのですが、サンプルの最善手にならなかったので、困り果てましたが、特定のアルゴリズムではなく、すべての道筋を残すようにしておいたらさくっといけた、というちょっと運が良かったです・・・。
データ量を減らすために、動き回れるポイント（Basinと書かれたユニオンツール）とブリザードは別々に管理しています。反復入力側に、ブリザードとエルフの位置をインプットしています。基本的に中身が書き換わるレコードを反復入力に入れておき、それ以外の下記変わらない部分は別の入力にしておくと、反復するデータ量が少なくなり、高速化されます。
Part1用ワークフロー：
Part1マクロ：移動マクロ
真ん中にある「don’t decide one route」というところが、次に行ける可能性のあるポイントが出てくる場所です。ここで１レコードに絞り込むと詰みます。絞り込まずに動かせば、到達できないルートは自然消滅するようになっています。このマクロはPart1、2共用です。
Part2は、一度ゴールに到達した状態で、ゴール側からスタート側へ移動する必要があります。基本的な考え方は同じであるため、スタートとゴール、吹雪の状態をPart1で使ったマクロに入れてあげれば動作します。さらにまたゴールに移動するため、同じマクロを３回、入力データを変えて適用すれば終わりです。
まとめ
- ２４日目もまたもや地図の問題でした。難易度として、ルートを絞らなければさくっと解けたのですが、ここに気づかなかったら永久にブリザードの盆地をさまよっていたと思います。
- 難易度的にはちょっと納まったように思いますが、高難易度なのは変わらないです。
- 個人タイム：一度見て一旦諦めました。が、結構さくっと解いてる方がいたので、改めてチャレンジしてみた、という感じです。Part1が解けてからPart2は30分程度で解いています。
コメント