※過去記事はこちら。AlteryxユーザーのためのAdvent of Codeの始め方、１日目、２日目、３日目、４日目、５日目、６日目、７日目、８日目、９日目、10日目、11日目、12日目、13日目、14日目、15日目、16日目、17日目、18日目、19日目、20日目、21日目、22日目、23日目、24日目。
２５日のPart1をクリアした時のスクリーンショットです。
2024/1/3にコンプリートしました！
第弐拾伍話「Snowverload」
タイトルは「スノーバーロード」。
調べた限りでは、無料MMO「RuneScape」の季節限定のボスの名前・・・？なんですかね。
前回雹をぶつけて雪を降らせることが、、、できなかったようで、雪の島の中心部を調べることになりました。そこには降雪装置があるのですが、稼働していません。どうやら電力過負荷エラーで止まっているようです。いくつかのコンポーネントを取り外す必要があります。
装置から半分を切断する方法を見つける必要があります。３本のワイヤを切断する時間しかないようですが、コンポーネントの配線図（パズルのインプット）がここにあります。
jqt: rhn xhk nvd
rsh: frs pzl lsr
xhk: hfx
cmg: qnr nvd lhk bvb
rhn: xhk bvb hfx
bvb: xhk hfx
pzl: lsr hfx nvd
qnr: nvd
ntq: jqt hfx bvb xhk
nvd: lhk
lsr: lhk
rzs: qnr cmg lsr rsh
frs: qnr lhk lsr各コンポーネントは「：」の左側にあり、それと接続されているコンポーネントが右側に書かれています。３本カットして２つのグループに分けることができたら、そのグループの数をかけあわせたものがパズルの答えです。
・ネ
・
・タ
・
・バ
・
・レ
Part1,2を解いてみる
Part2は全クリア専用の★なので、25日はPart1しかありません。
普通に考えるとグラフ理論で考えます。三本のエッジを順番に削除して2つのグループにできるか、をすべて調べれば良いだけですが、非常に時間がかかります。
しかしながら、この問題については可視化が非常に役に立ちます。Alteryxではネットワーク解析ツールでグラフの可視化ができます。例えば、サンプルデータを可視化してみましょう。
これもう見た目で（nvd、jqt）、（nvd、bvb）、（pzl、hfx）とわかりますね！
本番データはノード数が多いためかなり表示するまで待たされますが、動きます。ノード数は1408個、エッジ数は3148個もあります。
がんばって拡大すればノードのラベルが見えます（といっても、最初の表示に時間がかかるだけなので、そんなに苦労しないと思います）。
クリックすればハイライトされるので比較的簡単に発見できるでしょう。
ちなみに、ネットワーク解析ツールは、2つインプットがあり、N入力には、以下のようなノードリストを入れます。
E入力はエッジリストを入れます。
フィールド名は決め打ちなので気をつけてください。
削除すべきノードさえわかれば、あとはグループ作成ツールで簡単に出すことができます。
ワークフロー全体は以下のとおりです。
まとめ
- 思わぬところで役に立つネットワーク解析ツール。
- Private LeaderボードではPart1は２位でした（27分）。負けたのはPCスペックのせいもあったもしれません、、、
- 気になるポイントは、これ、力技で解くとすればどうするか、ですね。ひたすら三本のエッジを削除し、グループ化ツールで2つにわかれるかどうかを探ることになると思います。3148の三乗の回数繰り返せば答えが出ると思います（311億回か、、、あまり現実的じゃない・・・）。ということで、グラフ理論の最小カット問題を実装すれば解けそうです。その他の可能性として、グラフを描くことができれば、通常のクラスタリングアルゴリズムでグループ化して解くことができそうです。まぁ、描くのが結構大変なのですが、、、（大学時代の卒論がkamada-kawaiアルゴリズムの改良だったので）。ベースはエッジをバネ、ノードを重りと見立ててある程度収束するまで計算をかけていくといい感じになるはずです。時間があったらなにかやってみたいところです・・・。→ 無事に最小カット問題で解くことが出来ました。こちら参照。
コメント