※過去記事はこちら。AlteryxユーザーのためのAdvent of Codeの始め方、1日目、2日目、3日目、4日目、5日目、6日目、7日目、8日目、9日目、10日目、11日目、12日目、13日目、14日目、15日目、16日目、17日目、18日目、19日目、20日目、21日目、22日目、23日目
24日目です。21のPart2が解けたときの画像を採用しています。

タイトルは、「Blizzard Basin」。吹雪の盆地、ですかね。Basinとか馴染みがない単語で・・・。
今回の問題も、地図問題ですが、エルフが吹雪を避けてゴールに到達する問題です。
サンプルの入力データとしては、以下のようになっています。
#.#####
#.....#
#>....#
#.....#
#...v.#
#.....#
#####.#
#は壁。「>」「v」はブリザードの地点と移動方向を示しています。実際の小さいサンプルを再度お見せします(スタート地点SとゴールGも記載しておきます)。
#S######
#>>.<^<#
#.<..<<#
#>v.><>#
#<^v^^>#
######G#
ブリザードは矢印の方向に動いています。壁に当たると逆側で新たなブリザードが生成されます。ブリザードのあるところには入れないので、避けてゴールまで行く必要があります。ルールは非常にシンプルです。
Part1では最短でゴールに辿り着くまでの時間(経過ターン)をカウントします。
Part2では、一度ゴールに行った後、エルフがおやつを忘れてたとのことで、一度スタート地点に戻ってから再度ゴールに向かう最短時間を出す問題です(エルフ死ねばいいのに、、、)
・ネ
・
・タ
・
・バ
・
・レ
解いてみる
この問題、常に動く方向が一つとは限りません。例えば左右もしくは立ち止まれる場合に、動いた先でブリザードに囲まれて詰む場合もあったりします。最善手、というのがその瞬間ではわからず、すべての動き方をシミュレートする必要があります。
最初、特定のアルゴリズムで(例えば右下になるべく行くようにする)進めたのですが、サンプルの最善手にならなかったので、困り果てましたが、特定のアルゴリズムではなく、すべての道筋を残すようにしておいたらさくっといけた、というちょっと運が良かったです・・・。
データ量を減らすために、動き回れるポイント(Basinと書かれたユニオンツール)とブリザードは別々に管理しています。反復入力側に、ブリザードとエルフの位置をインプットしています。基本的に中身が書き換わるレコードを反復入力に入れておき、それ以外の下記変わらない部分は別の入力にしておくと、反復するデータ量が少なくなり、高速化されます。
Part1用ワークフロー:

Part1マクロ:移動マクロ

真ん中にある「don’t decide one route」というところが、次に行ける可能性のあるポイントが出てくる場所です。ここで1レコードに絞り込むと詰みます。絞り込まずに動かせば、到達できないルートは自然消滅するようになっています。このマクロはPart1、2共用です。
Part2は、一度ゴールに到達した状態で、ゴール側からスタート側へ移動する必要があります。基本的な考え方は同じであるため、スタートとゴール、吹雪の状態をPart1で使ったマクロに入れてあげれば動作します。さらにまたゴールに移動するため、同じマクロを3回、入力データを変えて適用すれば終わりです。

まとめ
- 24日目もまたもや地図の問題でした。難易度として、ルートを絞らなければさくっと解けたのですが、ここに気づかなかったら永久にブリザードの盆地をさまよっていたと思います。
- 難易度的にはちょっと納まったように思いますが、高難易度なのは変わらないです。
- 個人タイム:一度見て一旦諦めました。が、結構さくっと解いてる方がいたので、改めてチャレンジしてみた、という感じです。Part1が解けてからPart2は30分程度で解いています。
コメント