Advent of CodeをAlteryxでやってみる2024_16日目

Advent of Codeをデータ分析ツールAlteryxでやってみるシリーズ、2024年16日目です。

※過去記事はこちら。AlteryxユーザーのためのAdvent of Codeの始め方、１日目、２日目、３日目、4日目、５日目、6日目、7日目、8日目、9日目、10日目、11日目、12日目、13日目、14日目、15日目。

結局最後に解けた問題になりました！

Contents

Day 16「Reindeer Maze」
Part1,2を解いてみる
まとめ

Day 16「Reindeer Maze」

タイトルは「トナカイの迷路」。ほんと迷ってました・・・。

ストーリー的にはトナカイオリンピックというのが行われ、最低得点を競うイベントのようです。以下のように壁が＃、Sがスタート、Eがゴールの地図が与えられます。右を向いてSから開始し、Eにたどり着く必要がありますが、1マス進むと1ポイント90°向きを変えると1000ポイントが与えられます。もちろん、最低得点を競うので、このポイントが一番少なければ勝ち、となります。

###############
#.......#....E#
#.#.###.#.###.#
#.....#.#...#.#
#.###.#####.#.#
#.#.#.......#.#
#.#.#####.###.#
#...........#.#
###.#.#####.#.#
#...#.....#.#.#
#.#.#.###.#.#.#
#.....#...#.#.#
#.###.#.#.#.#.#
#S..#.....#...#
###############

最短路で歩くと、以下のように367歩の7036ポイントでゴールできます。

###############
#.......#....E#
#.#.###.#.###^#
#.....#.#...#^#
#.###.#####.#^#
#.#.#.......#^#
#.#.#####.###^#
#..>>>>>>>>v#^#
###^#.#####v#^#
#>>^#.....#v#^#
#^#.#.###.#v#^#
#^....#...#v#^#
#^###.#.#.#v#^#
#S..#.....#>>^#
###############

Part1ではこの最短路を求め、ポイントがパズルの答えです。

Part2では、最短路が複数あることがわかります。例えば以下のようになります。

###############
#.......#....O#
#.#.###.#.###O#
#.....#.#...#O#
#.###.#####.#O#
#.#.#.......#O#
#.#.#####.###O#
#..OOOOOOOOO#O#
###O#O#####O#O#
#OOO#O....#O#O#
#O#O#O###.#O#O#
#OOOOO#...#O#O#
#O###.#.#.#O#O#
#O..#.....#OOO#
###############

この時塗りつぶされたマス数がパズルの答えです。

・ネ

・

・タ

・

・バ

・

・レ

Part1,2を解いてみる

完全に今年のブロッカーになりました。ワークフロー全景以下のとおりですが、いかに困難な道程だったかが伺い知れるかと思います。

まぁ、もっと最適な感じで作れるとは思いますが・・・。

まず、Part1、何も工夫なしでダイクストラ法で解くことは可能です。

以下ダイクストラ法です。

ただし、これ、そこそこワークフローを回すのに時間がかかります（といっても20分程度です）。

さて、このような迷路系の問題（ロールプレイングゲームなら地上のMAPではなくダンジョン的な通路を歩く感じ）はルート圧縮が非常に効きます。つまり、直線は一気に移動する、ということです。これによりグラフ問題に置き換わり、処理量を大幅に削減できます（ルート削減は意外と時間がかかりません・・・削減を考えるのが大変ですが）。

とにかくルート削減部分が非常に冗長になってしまいました。また、ダイクストラを改良したのですが、MAP問題をグラフ問題に変換するためのデータの作り部分が非常に冗長になってしまいました。

以下はノードリストを作っています。

各ノードが、短縮した時に不要かどうか、を付与しています。

さらに、エッジ（辺）を作っていきます。

そして、ダイクストラに入力するノードリストを作成し、ルートサーチを行います。

このダイクストラは、グラフ用に作成したものです。

このルート圧縮版により、２分２１秒で完了するようになりました。

Part2も難関です。基本的なスタイルとして、Part1で求められた最適路をベースに考えていきます。このうち、交差点があるポイント（ノード）を「あるポイントから３方向もしくは４方向に行けるノード」とすると、交差があるノードから別の交差点のノードへの別の最適路を求めればオッケーということになります。また、もう一つの条件として、それらの交差点のポイントの差分がルート検索した時に同じであればオッケーということになります。この２つの性質を使って求めましたが、それでも候補となる検索路は3000くらいになります。もう一つの特徴として、直線状の別ルートはないので（直線で別ルートがあれば、それが最適候補になっているはず）、コストの差分が1000を超えたものに絞り込むことができます。探索ワークフロー自体は、P1から少し変えて、コストの差分より現在のコストが大きくなったらループをやめるようにしています（これをしないとうちのダイクストラちゃんが無限ループに入るので、仕方なくやっている、という節もあります）。

実際のワークフローとして、P1の結果から、サーチすべきスタートとゴールの組み合わせを入手します。

その後、ダイクストラで各スタートとゴールの最短経路を計算し、ゴールに到達できてポイントが同じものだけ抽出し、最終的なステップ数を計算します。

ここのダイクストラはバッチマクロになっていて、すべてのスタートとゴールの組み合わせを順次計算します。

内部のダイクストラは現在のコストがコスト差分を超えると強制終了するように改造したものです。

結果論的ではありますが、発見されたルートは13000ポイントが最大だったので、差分は1000から13000に絞り込むことでワークフロー自体の速度はあがります（これで答えがあわなければ、少しずつ大きくしていきましょう）。コストが小さければ、その分速度も早いです。

ちなみに、探り探りやっていたのもあり、かなり乱雑な作りになっています。途中経過としては、P1を求めるワークフロー、P1の結果からルート検索するWF、そしてその結果から歩数を求めるワークフロー、と三段階で作っていました。投稿するワークフローはすべて合体したものに整理していますが・・・。

トータルでは約8分で回ります。

まとめ

疲れました・・・
毎回苦戦するこのシリーズ。来年はさくっとできるかしら・・・。
A*はうまくいきませんでした。シンプルなものにしか使えないかもしれません（どうしても最適路にならない）
去年実装したダイクストラはどうも若干ダイクストラを曲解していたらしく今見直すとかなりシンプルということがわかりました（どのサイトの説明もわかりにくいんですよね）
ルート圧縮しなくてももしかしたらP2戦えたのかな、、、？（でも、たぶん６時間とかかかるWFになっていたと想定される）
とにかく最適ルート検索アルゴリズムがなかなか決まらなかったです。
ルート圧縮も、直線上での圧縮は比較的すんなりいったのですが、さらに曲がりくねったところを一つのルートにしようとして、うまくいきませんでした。これが決まればもっと高速に動くはず・・・。
本当に試行錯誤が多くて、あとから必要になったものをたくさん付加したので、冗長なWFになってしまいました・・・。
とりあえずこれでクリアです！