Advent of Codeをデータ分析ツールAlteryxでやってみるシリーズ、2024年10日目です。
※過去記事はこちら。AlteryxユーザーのためのAdvent of Codeの始め方、１日目、２日目、３日目、4日目、５日目、6日目、7日目、8日目、9日目。
Day 10「Hoof It」
タイトルは「歩く」、ですかね？「踊る」という意味もあるようで、意味が取りにくい・・・。
ストーリーとしては、地図が失われたハイキングコースを調べたい、とのことです。
ということでMAPの問題です。地図は以下のように高さで示されていて、0が低くて、9が高くなります。
0123
1234
8765
98760はスタート地点（トレイルヘッド）です。複数あることがあります。9はゴールです。複数あることがあります。基本的に移動する時は段差が1以内である必要があります。なので、0の次は必ず1です。
以下のような地図がある場合、「.」は歩けない場所です。0からスタートすると、ゴールである2つの9はどちらも到達することができます。このスタート地点のスコアは2とします。
...0...
...1...
...2...
6543456
7.....7
8.....8
9.....9例えば、実際は以下のような地図になります。
89010123
78121874
87430965
96549874
45678903
32019012
01329801
10456732スタート地点は9箇所あります。各スタート地点から9にたどり着けるゴールの数（スコア）は、5、6、5、3、1、3、5、3、5で、これらを足すと36になります。
Part2は、各ゴールにたどり着くための経路の数を求めます。あるスタート地点からあるゴールへの経路は一つではなく複数あることがあります。このルートの数を求めます。
・ネ
・
・タ
・
・バ
・
・レ
Part１，２を解いてみる
久しぶりに簡単な問題です。といっても、Advent of Code経験者はさんざんこのようなMAP問題を解かされるのですが、その中では入門編として非常に良い問題です。
このパターンの問題は、どのようなデータ構造にするか、というのが一つのポイントです。だいたいやってるうちにあれがほしい、これがほしい、となるケースが多いですが、ベースになるのは以下のようなデータ構造です。
Part1の時点では、正直ルートを保存する必要がないのですが、だいたいPart2では必要だろう、ということもあり入れています（デバッグにも使えますし、実際に正解でした）。
RouteはポイントにふったIDにしてみました。代わりにx,y座標にして、1-2、2-1、、、みたいな形で保存することもできます。一つ前のポイントを保存するPrevIDという項目を作っていたのですが、今回の問題の特性で、次のポイントは今のポイントの＋１にしかいけない、ということで省きました。
ちなみに、反復マクロ内で繰り返すデータは、変化するデータのみにするべきです。なので、MAP構造自体は繰り返さず、今の地点のみを保存してそれを繰り返すというふうにしています。MAP構造ごと繰り返しに入れてしまうと反復マクロの処理に非常に時間がかかります。
マクロ内では、入力ポイントから隣のポイントを作成します。具体的には、x座標、y座標を±1することで4つの隣接ポイントを作ります。今回は高さの差分は1のみ許容されるので、高さの差が今のポイントから+1ポイントになっているところのみをフィルターします。
今回はいわゆる幅優先探索（BFS）という手法です。一度にたくさんのルートを作ってそれぞれのルートがどうなっていくか、というのを見ています。結果として9回の反復が行われると終了するので、レコード数としてはそれほど増えません。Alteryxと非常に相性の良い問題です。まぁ、ルートが長くなるとデータ量が爆発してくるので、また別の対処が必要です。
一方で深さ優先探索（DFS）にすると、繰り返し回数が多いとAlteryxでは時間がかかってしまいますね・・・。
まとめ
- 久々（？）のオアシス問題、というのを10日目で言うとは思いませんでしたが、間違いなくオアシス問題です。
- ほっと一息。
- Private Leaderboardでは、簡単と言いつつも集中できなくてPart1は6位、Part2は7位です。
コメント