※過去記事はこちら。AlteryxユーザーのためのAdvent of Codeの始め方、１日目、２日目、３日目、４日目、５日目、６日目、７日目。
第八話 「Haunted Wasteland」
タイトルは「幽霊の出る荒れ地」。
前回からラクダに乗っているのですが、砂嵐が来て道案内のエルフとははぐれてしまったようです。この幽霊の出る砂漠から脱出するにはラクダのポーチに入っていた地図に従って進む必要があるようです。ただ、基本的に左（L）か右（R）にしか命令できないようです。また、地図の現在位置は「AAA」でどうやら出口は「ZZZ」のようです。道順は以下のようなフォーマットで書かれています（インプット）。
RL
AAA = (BBB, CCC)
BBB = (DDD, EEE)
CCC = (ZZZ, GGG)
DDD = (DDD, DDD)
EEE = (EEE, EEE)
GGG = (GGG, GGG)
ZZZ = (ZZZ, ZZZ)一行目は進み方が書かれています。つまり最初は右、次は左。それ以降の行が道順です。最初はAAAから始まりますが、経路としてはBBBかCCCに行くことができます。最初は「R」に「行け」なので、右側、つまりCCCに行きます。CCCでは左がZZZ、右がGGGですが、Lに行け、なので、ZZZに行きます。ZZZが出ぐりなので、2 Stepで脱出できた、ということになります。
ただ、このRLの指示ですが、ZZZに行くまでに数が足らないことがあります。この場合は、RLを繰り返すことになります。
この条件で、インプットを使って何ステップで脱出できるか、を計算します。
Part2は、、、なぜかPart1の方法では脱出できなかったことになっています。実は地図は幽霊用かもしれないということで確かめる必要があります。よくMAPを見ると、最後がZになっているものは最後がAになっているものと同じだけあるようです。幽霊であれば、すべてのAで終わるノード最初から辿った場合にZまで同時に辿れるそうです。
例えば、以下のようなインプットを考えます。
LR
11A = (11B, XXX)
11B = (XXX, 11Z)
11Z = (11B, XXX)
22A = (22B, XXX)
22B = (22C, 22C)
22C = (22Z, 22Z)
22Z = (22B, 22B)
XXX = (XXX, XXX)一番右の文字がAで始まるノードは11Aと22Aの2つがあります。これを同時におっかけていきましょう。最初はLなので、11Aは11B、22Aは22Bへ行きます。次、11BはRの11Z、22Bは22Cへ行きます。同時にZに行ってないのでさらに進みます。あとはRLを繰り返すので、以下のようになります。
Step1：L：11A = (11B, XXX)：22A = (22B, XXX)
Step2：R：11B = (XXX, 11Z)：22B = (22C, 22C)
Step3：L：11Z = (11B, XXX)：22C = (22Z, 22Z)
Step4：R：11B = (XXX, 11Z)：22Z = (22B, 22B)
Step5：L：11Z = (11B, XXX)：22B = (22C, 22B)
Step6：R：11B = (XXX, 11Z)：22C = (22Z, 22Z)
ということで6stepになります。
・ネ
・
・タ
・
・バ
・
・レ
Part1を解いてみる
ようこそ、反復マクロの世界へ。
ルートをたどる問題は、基本反復マクロでしか解くことができません。ベースは次々に結合ツールでJoinしていく、ということになります。
Part1は、まさにそのマクロを作っていくことになります。高速な反復マクロを作るためには、なるべく繰り返すデータを少なく、が鉄則です。ただ、場合によってはデータ量が多くなってしまう場合もあります。基本的に反復入力・出力は一つしか持てないので、色々と工夫する必要があります。特にデータが変化しないデータについては、反復入力ではなく、通常の入力で問題ありません。例えば、今回のデータは常に現在の地点を保持しておく必要があります。逆にそれ以外は不要です。スタートはAAAなので、フィルタで抽出しましょう。
ルートデータは以下のように入力します。このデータは上から一つずつ使うだけなので、繰り返し回数のパラメータでフィルタをかければオッケーです（271レコードあります）。D入力です。
メインのルートデータは、以下のように保持しました（814レコードあります）。P入力です。
マクロとしては以下のとおりです。
まぁ、極めてシンプルなマクロです。最終的には、マクロを繰り返した回数＋１が答えです。
最終的には15,000Step以上かかりました。
次はPart2ですが、結論として６つのルートを調べていく必要がありました。この６つのルートが同時にZに行くポイントを探さなければなりません。ちなみに、Alteryxの反復マクロの限界まで回してもゴールに辿り着くことはありませんでした。
Part2については、力技で回すと、天文学的な時間がかかるようになっています。結論としては、それぞれのルートのZへの到達時間の最小公倍数が答えとなります。なので、各ルートについてPart1の答えを算出し、その出たStepの最小公倍数を計算すれば回答が出ます。
スタート地点のデータは、以下のようにインプットのおしりがAのデータです。今回は６つありました。
これをそのままPart1マクロで終了条件だけ変えたマクロに突っ込みます（ラストのフィルタツールです）。
これにより、それぞれのスタート地点からの移動回数が出ます（つまり、各スタートからゴールまでにかかったステップ数です）。これに対して最小公倍数を取っていきます。これは過去のウィークリーチャレンジで遊んでいて作ったマクロです。ベースは最小公約数ですが、それをさらに発展させたマクロです。ちなみにこれも反復マクロですが、さらに内部にGCD（最小公約数を計算するマクロが入っています）。
GCDマクロの中身。
これ、たまたま作ってなければまた大変だったろうな、、、という感じです。最終的なワークフローは以下のとおりです。
まとめ
- Part1は約45分（Private Leaderボードで5位）、Part2は最初解法がわからなかったのでハマりました。LCMということがわかれば昔Weekly Challengeで作ったLCMマクロが役に立ちました。
- 最速の人で1時間34分。Part2は結構諦めている人も多いです。
おまけ
最初の作ったマクロの赤色の部分ですが、外に組み込んでおくことも可能です。
これをマクロ内外で比べてみました。
カウント＋フィールド付加をマクロ外に出す：22秒
カウント＋フィールド付加をマクロ内で実行：52秒
かなり高速化されました。というか実はこれ、結構負荷が大きい作業なんですね・・・。
コメント