※過去記事はこちら。AlteryxユーザーのためのAdvent of Codeの始め方、１日目、２日目、３日目、４日目、５日目、６日目、７日目、８日目、９日目、１０日目、１１日目、１２日目、１３日目、１４日目、１５日目
１６日目です。１６日目の問題を回答できた時点の画像としています。
タイトルは、「Proboscidea Volcanium」。テングザル火山、とのこと。
今回の問題は、センサーで特定した遭難信号で発見した洞窟を探検し、ゾウを追い出すという話なのですが、洞窟内のバルブを開いて行く問題です。
サンプルの入力データとしては、以下のようになっています。
Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
Valve BB has flow rate=13; tunnels lead to valves CC, AA
Valve CC has flow rate=2; tunnels lead to valves DD, BB
Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE
Valve EE has flow rate=3; tunnels lead to valves FF, DD
Valve FF has flow rate=0; tunnels lead to valves EE, GG
Valve GG has flow rate=0; tunnels lead to valves FF, HH
Valve HH has flow rate=22; tunnel leads to valve GG
Valve II has flow rate=0; tunnels lead to valves AA, JJ
Valve JJ has flow rate=21; tunnel leads to valve IIこのパズルの条件として、１つのバルブを開くのに１分、バルブ間を移動するのに１分かかります。Rateが圧力ですが、0になっているものは開いても意味がありません。移動とバルブを開くのを繰り返し、３０分でどれだけの圧力を開放できるか、というのがPart1の問題です。
いわゆるグラフ理論っぽい問題ですが、これを可視化してみましょう。今回は、AlteryxのRインストーラーにより導入できる、ネットワーク分析ツールを使います。ノードの大きさはRateの大きさを割り当てています。
Part2では、なぜか追い出していた象の一頭と自分の２名で洞窟を探検してバルブを開くという問題です。象に教える時間が４分必要とのことで、30分から２６分に時間が短くなっています。
・ネ
・
・タ
・
・バ
・
・レ
解いてみる
未解決問題です。解けたらアップします！
これ、単に経路探索しても、バルブを開くタイミングもパラメータとしてあるので、ちょっとどう解くのか悩みどころです・・・。
まず、自分用のデータを可視化してみました。黄色のノードはRateが0なので単なる通過点です。青色は開ける必要のあるバルブで、円の大きさはRateの大きさを示しています。
ちなみに、このようなグラフを作るツールは、ネットワーク分析ツールです（Rツールのインストールが必要です）。ノードリストとエッジリストを作ることで可視化が可能です。ちょっとレンダリングに時間がかかるツールです・・・。
Part1はグラフ理論ということで、バルブをあける必要のないRate０のバルブのルートを削除し、エッジに各ノード間の距離を入れたグラフを作成しました。
その後、反復マクロで行ける可能性のあるルートを全て辿っていきながらバルブを開けるようなアルゴリズムとしています。
基本的に、繰り返す情報は最低限とし、自分の現在のノードの位置、時間、開けたバルブ、現在のPressure、トータルのPressureとしています。それ以外のエッジ、ノードの情報は繰り返す情報に入れず、毎回処理前に結合するようにしています。
ちなみに30分の時間で流れるPressureを計算するのですが、開くべきバルブは９分くらいで開ききってしまうため、すべてのバルブを開いたら終了するような条件にしています。ただ、これでも処理に10分程度かかってしまいました。
Part2はロジックを完全に作り直して対応しています（こんなのほとんど別の問題じゃないですか・・・）。そもそも、自分と象を動かさないといけないので、まともなグラフ理論じゃ無理と判断しました。反復マクロで保持するデータとして、自分と象でそれぞれ保持するデータとして、現在の場所、通ったルート（これはなくても良いですが、デバッグ用としています）、次のアクションとし、自分と象の共用の項目として時間、開けたバルブ、現在のPressure、トータルのPressureとして反復しながら処理を行っています。
最終的なワークフローです。Part2の方は、２６分中２５分かかってすべてのバルブを開くような形になっていたので、まともにやると終わりません。そのため、処理するレコードは、トータルで流れたPressureとPressureの降順にして大きい方から5000レコードに絞って処理を行っています。ある程度Pressureが大きいものでなければ最大のものにはならないので現実的な方法かと思います。ここはCommunityのヒントが大いに役に立ちました。これがなければ解けてなかったでしょう・・・。
まとめ
- １６日目も、グラフ問題でしたが、動きが若干複雑で単なるグラフ問題としては解けなかったように思います。基本的に全パターンやろうとすると非常に多くのレコードになってしまうため、強制的に可能性が高いレコードにPressureの多い順などで絞り込まないと難しい問題でした。
- 意外と後半戦の中ではクリアされてる方の多い問題でした（が、なかなかCommunityに解決策がアップロードされなかった問題でもあります）。
- 個人タイム：ゆっくりやらせていただきました！
コメント