※過去記事はこちら。AlteryxユーザーのためのAdvent of Codeの始め方、１日目、２日目、３日目、４日目、５日目、６日目、７日目、８日目、９日目。
第拾話 「Pipe Maze」
タイトルは「パイプの迷路」。本当に迷い込んでしまっていました・・・。
ストーリーとしては、ハンググライダーで空に飛んでいた金属の浮島についたところから始まります。この島はすべてが金属でできており、花も木も金属です。やがて動物が走り回っているのに気がつくのですが、これはパイプの中を走り回っているようで、この動物を見つけたいようです（ほっとけばいいじゃん！）。
そのパイプは以下のような地図で表されます（この時点で、MAP問題ということがわかりますね）。
.....
.F-7.
.|.|.
.L-J.
......・・・ドットは、、、何もないことを示します
F・・・右から下へいけるパイプ（逆も可能）
|・・・これこそまさにパイプ記号ですが、上下をつなぐパイプ
-・・・横棒ですね。左右をつなぐパイプ
L・・・上から右にいけるパイプ（逆も可能）
J・・・これだけ湾曲してません？上から左に抜けるパイプ（逆も可能）
７・・・どう見ても数字の７ですが、左から下に抜けるパイプ（逆も可能）
ところでスタート地点は「S」と書かれています。基本的に、スタート地点からこのパイプに沿って移動するとまたスタート地点に戻ってくるようにパイプでループが組まれています。
Part1は、パイプ内で一番遠い場所を見つけることです。上のサンプルだと以下のようになるので、4が答えです。
.....
.012.
.1.3.
.234.
.....Part2は、パイプ内を移動する動物を追い詰めたかに思いましたが、実は動物はパイプの中ではなく、パイプのループに囲まれた内部のどこかにいるとのことです。つまり、以下のようなインプットを考えてみます。
...........
.S-------7.
.|F-----7|.
.||.....||.
.||.....||.
.|L-7.F-J|.
.|..|.|..|.
.L--J.L--J.
...........動物のいそうな場所は以下の地図の「I」がある場所になります（Oは外部と繋がっているのでNG）。
...........
.S-------7.
.|F-----7|.
.||OOOOO||.
.||OOOOO||.
.|L-7OF-J|.
.|II|O|II|.
.L--JOL--J.
.....O.....もしくは、以下のようなパターンです。
..........
.S------7.
.|F----7|.
.||OOOO||.
.||OOOO||.
.|L-7F-J|.
.|II||II|.
.L--JL--J.
..........こちらは、なぜかパイプのループ内が「O」になっていますが、実は赤い部分が外に繋がっている判定になっています（まぁ、たしかに隙間ありそうです）。
・ネ
・
・タ
・
・バ
・
・レ
Part1,2を解いてみる
今日も恒例の反復マクロの日です。スタート地点から、行けるポイントを調べて最後まで行く問題です。Part1は、一番遠いところなので、スタート地点からパイプの両側に向けて調べることも可能ですが、片方に向けて調べていきましょう。マクロとしては以下のとおりです。
今回は、一つ前のポイントのデータを持たせて、パイプのどちらから侵入したかというのを判断し、次の移動先を決めるようなアルゴリズムにしています。よって、以下のようなデータを入力としています（これをそのまま反復しています）。ちなみに、一度使ったポイントは捨てて（といっても、結果として出力し、繰り返し出力からは省きます）、反復のレコード数を少なくするようにしています。
終了条件は、次のルートがマッチしなくなったところで終わるようにしています。経路は反復出力ではない方から出ていくのでPart2でもそのまま使えるようになっています。
Part1の解答としては、スタート地点からゴールまでの移動回数を２で割ったものです。全体としては冗長になっているように思います。
Part2は、パイプのループ内を調べるうまい解決法を思いつかなかったので、悩んだ末空間の問題に変換しました。結局パイプ自体でポリゴンを書いてあげればいいのですが、パイプを一筆書きするための順番を調べる必要があります。今回はPart1の反復出力ではない方に途中の経路を出力するようにしているため、その結果がそのまま使えます。
空間の問題にしたので、図示すると以下のようになります。ちょっときもいです。
グリーンのがパイプ、赤い点が、動物のいる可能性のあるポイントらしいです（パイプ内の空間）。ちなみに、空間と言ってもドットの部分だけではなく、ループしていない空間も含まれています（これもちょっとわかりにくいポイント）。
ワークフローとしては、以下のようになります（Part1の出力以降です）。
緑の空間系のツール部分は比較的シンプルです。Part2だけなら11個のツールで解答が出せています。
ワークフロー全体です。
まとめ
- 今回は、かなり無駄が多かったです。Part2だけ見ると、Day5くらい絶望感溢れる感じでした。Part1も、実は最初はスタート地点のパイプの両側を調べていって解答は出たのですが、なにか変なバグがあったようで、使ったパイプが無惨な形になっていました。どのみち、Part2は経路を調べなければならないためパイプの両側を探索すると使えません（正確に言うと使えるのかもしれませんが、いずれにしても経路を保存しておく必要がありました）。
- Part2については、昔似たような問題がありました。気泡を取り除く問題でしたが、外から隣接しているブロックを中に調べていくという形でした。最初これをなぞって作りましたが結果は惨敗。またもや時間を無駄に・・・。
- 今回は試行錯誤の時間が非常に長く、Part2で空間でやろう、と思いついてからも、ルートを出すマクロの作成に時間を費やしてしまいました。そのデバッグが終わってからはすぐ答えは出ましたが・・・さすが空間ツール様々ですね！ほんと今回は空間ツール使えないと解けてなかったと思います。
- なにげにコミュニティ見ると、空間ツールなしで解いている人がいてびっくりしました。
- Part1だけならPrivate Leaderボードで3位（1時間6分）。Part2含めると6位となりました。トータル5時間30分の長丁場となりました。最速の人は、1時間40分程度で解いているのですごいですね・・・。最初からスパッと決まっていたらそれくらいで解けたかもしれません。
コメント