Advent of Codeをデータ分析ツールAlteryxでやってみるシリーズ、2024年18日目です。
※過去記事はこちら。AlteryxユーザーのためのAdvent of Codeの始め方、１日目、２日目、３日目、4日目、５日目、6日目、7日目、8日目、9日目、10日目、11日目、12日目、13日目、14日目、15日目、16日目、17日目。
Day 18「RAM Run」
タイトルは、「RAM走る」と直訳できますが、なんだろ、訳が難しいですね。いっそのこと「ランラン」だと楽しそうですね。
ストーリー的にはなぜかコンピュータの中に入り込んでしまっているようです。そして、メモリ破損が起きているので逃げる必要があります。メモリ破損は、以下のようなインプットデータにより起きています。左側はx座標、右側はy座標を示しています。
5,4
4,2
4,5
3,0
2,1
6,3
2,4
1,5
0,6
3,3
2,6
5,1
1,2
5,5
2,5
6,5
1,4
0,4
6,4
1,1
6,1
1,0
0,5
1,6
2,0歴史家は、0,0座標からスタートし、右下に逃げる必要があります。Part1では、上のインプットの1024番目までメモリ破損が起きた時に、逃げることができる最短ルートを求めます。
次に、Part2では、1024以降のメモリ破損で、ゴールに到達できないメモリ破損が起きる最初のバイト位置の座標の位置を求めます（ややこしいですね）。
・ネ
・
・タ
・
・バ
・
・レ
Part1、2を解いてみる
Part1は、何かしらアルゴリズムがあった方が良いです、ということで、A*（A-star）アルゴリズムを組んでみました。こちらのページを参考にしてみました。こういう問題で一般的に使われるのはダイクストラ法ですが、それより効率が良いので、こちらを採用しています。
Part1は、効率の良いアルゴリズムさえあれば特に問題ありません（が、アルゴリズムないと結構きつい）。今まででは珍しく、入力データをすべて使わず、1024とぶったぎったところまで使うというのが若干新鮮でした（そして、惑わされたポイント）。あと、ちゃんとしたアルゴリズム組み時は、集中してやらないときついです・・・。
ちなみに、A*は処理後にGoalからStartに向かってポインタを手繰っていくことで実際のルートが出てきます。
Part2は、入力データの続きである1024以降のメモリの破損（障害物を置く）を行った時、ゴールにたどり着けないポイントを探す、という問題です。だいたい自分のPCでルート探索に1分ほどかかるので、さらに2000回繰り返すのは厳しいですが・・・（単純計算で2000分ですよね）。よくよく考えると、ゴールにたどり着けなくなるのは完全にルートが塞がったときです。つまり、ある時点からゴールにたどり着けなくなるということは、逆から見ていくと、ゴールにいつからたどり着けたか、を探すのでもOKということになります。探索アルゴリズムはたどり着けない方が探索するポイント数が減るので、逆から見ていって、初めて探索できたポイントの一つ前が答えのポイントになります。
ということで、反復マクロで、メモリ破損を逆側から見ていくことで2-3分で走らせることができました。
ワークフローは以下のとおりです。
まとめ
- 忙しくてリアルタイムにやる暇なし
- 意外とA*アルゴリズム簡単に組めた気がします。今度からルート探索問題はこれ使います。コスト計算のところを改造すれば、いろいろなところで使えそうです。
- Part2は、問題文読み違えて結構時間を無駄にしました・・・。めっちゃミスリードされてる（自分自身に）。
コメント