※過去記事はこちら。AlteryxユーザーのためのAdvent of Codeの始め方、１日目、２日目、３日目、４日目、５日目、６日目、７日目、８日目、９日目、１０日目、１１日目
１２日目です。
タイトルは、「Hill Climbing Algorithm」。丘を登るアルゴリズム、です。
今回の問題は、山を登って行き、高いところ（ゴール）に到達するのが目的です。
サンプルの入力データとしては、以下のようになっています。
Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghiSがスタート、Eがゴールです。アルファベットのa、b、c・・・というのが高さで、今いるところから隣り合ったマスの一つ上の段しか登れません。例えば、aにいると、隣り合ったaもしくはbにしか行けない、ということです（斜めはNG）。
いわゆるグラフ理論的な問題になります。
x、y座標をそれぞれのポイントに与え、隣接するマスに到達できるかどうか、というのを調べていくと、ノード（点）とエッジ（辺）のリストがそれぞれできあがります。
これを使って最短距離を求める、というのが趣旨です（まず、ここまで持ってくるのが大変・・・）。
サンプルデータは40ポイントしかありませんが、本番データは2501ポイントあり、すべてのルートの探索は困難であるため、何かしら効率的に探索できるアルゴリズムが必要です。
・ネ
・
・タ
・
・バ
・
・レ
解いてみる
ノードとエッジのリストをまず作る必要があります。
ノードのリストはノードの位置を示す「x,y」と入力データの組のリストです。エッジのリストは、出発ノードと到着ノードのリストです。以下のようなワークフローで作っています。
ノードリストは以下のようになりました（先頭から１０レコード）。
エッジリストは以下のようになりました（先頭から１０レコード）。
ここから、実際に最短ルートを特定しますが、今回は幅優先探索（breadth first search）を使っています。ネット調べるとアルゴリズムは出てくるので、組めなくはないと思います。
基本的には反復マクロです。スタート地点から隣り合ったところがあれば距離を＋１します。これを次のループの始点にします。隣り合ったところがない（行き止まり）ルートは捨てられます。基本的にこれを繰り返すだけですが、ルートの深さ分まで繰り返しを行います。また、繰り返すデータ量はノード数が最大です。なので、それほどめちゃくちゃ時間がかかるアルゴリズムではありません。
そのマクロはこちらです。
最終的な完成形はこちら。
Part2は、高いところから下がっていって、レベルがaの高さになるところまでを探索します。今回はデータを逆向きにして同じマクロに突っ込んでいます。おかげで、Part1できてからPart2までにかかった時間は７分程度でした。
このアルゴリズムのおかげで、4秒程度で解答が出ます。アルゴリズムバンザイ！！
まとめ
- １２日目は、Advent of Codeによくある問題で、x,y座標にプロットされているデータを使って一定のルールにそって処理を行う問題です。このような問題は、それなりのアルゴリズムがないと結構厳しいことも多いです・・・。
- 最速の人で1時間10分。その他結構かかった時間はバラバラです。
- 個人タイム：Part1 10時間51分11秒、Part2 10時間59分02秒（Private Leaderboardで6位）
※短時間で解けなかったのでゆっくりやっています・・・
コメント