※過去記事はこちら。AlteryxユーザーのためのAdvent of Codeの始め方、１日目、２日目、３日目、４日目、５日目、６日目、７日目、８日目、９日目、10日目、11日目、12日目、13日目、14日目、15日目、16日目。
未解決問題です。 ようやくクリアできました！
第拾質話 「Clumsy Crucible」
タイトルは「不器用なるつぼ」。
前回溶岩製造に成功したので、溶岩が流れ出しました。溶岩の滝の底につくと、エルフたちは「るつぼ」に溶岩を積み込みます。このるつぼを部品工場まで運ぶ必要があります。
地図があり、各都市ブロックには１～９の数字が書かれており、通過するたびに書かれた数値の分熱損失が発生します。今回も左上から出発し、右下のポイントを目指します。
2413432311323
3215453535623
3255245654254
3446585845452
4546657867536
1438598798454
4457876987766
3637877979653
4654967986887
4564679986453
1224686865563
2546548887735
4322674655533るつぼは重く、以下のルールに従って運ぶ必要があります。
- 同じ方向に3マスまでしか直進できない
- 移動時は前、右、左のいずれか（で、バックできない）
熱損失を最小限に抑えるルートを確定させ、その熱損失の値がパズルの答えになります。
Part2では、「るつぼ」が「ウルトラるつぼ」になり、よりじゃじゃ馬になりました。方向転換したら最低４歩歩く必要があり、かわりに１０歩まで同じ方向に歩けます。
・ネ
・
・タ
・
・バ
・
・レ
Part1,2を解いてみる
上のルールを考えると、以下のようなアルゴリズムが必要になります。
過去通ったポイントに戻る場合は、移動後の熱損失が自分より小さくなければならない（さらにその先に行く可能性があるが、さらに自分より小さいケースは少ないと思われるので、ループはしない）最初のポイントは熱損失を含まない（移動後に熱損失が発生する）
Part1は最終的にダイクストラ法ベースで解いてみました。組むのに苦労しましたが、一旦シンプルなダイクストラ法で組んでみました（ワークフローとしては結構複雑です）。
インプットは以下の通りで、全マップデータを保持して回します。その他ダイクストラ法で必要な現在のノードを保持するフラグと、確定ノードを示すFixedフラグ、コストを管理しているtotal_heatlossです。
マクロは以下の通り。
テストデータだと結構高速で1.3秒で回ります。しかし、本番データだと19881レコードを反復するので結構遅いです（反復回数も10093回になります）。普通に5分くらいかかります・・・。なお、ダイクストラ法の場合はレコード数が増えず、初回が最大レコードで、そこから確定させたノードは捨てるため少しずつ減っていくので、徐々に早くなります。
その後、今回の条件「同じ方向に３歩しか歩けない」を組み込みます。これ、ダイクストラ法でいくとするなら、入力データ側を工夫する必要があります。つまり、各ノードに対して方向とステップ数の状態も考慮したノードを入力として使います。つまり、通常ｘ軸、ｙ軸だけなのですが、これに上下左右の方向とステップ数１～３を組み合わせます。結論として、元のｘ軸、ｙ軸のデータの４×３＝１２倍のデータになります。もちろん、ダイクストラ法の中身も少しカスタマイズする必要があります（ただ、４歩目は削除するなどしなくても、４歩目のノードが存在しないので勝手に落ちてくれたり、というところでアルゴリズム的に少し楽ができます）。ただ、データ量が多く、結論として完走に６時間かかりました・・・。
また、注意点としてAMP Engineオンだとエラーで止まってしまったので、E1エンジンで動かしたところ正常に終了できました（しかもなぜだかAMPより５倍早い）。
マクロ全景は以下のとおりです。結合ツールと隣接ルート作るところがオリジナルのダイクストラ法から変えているポイントです。
ちなみに、テストデータでも、レコード数が2028件となり、834回繰り返すため結構時間がかかります（12秒かかりました）。
インプットとしては、全マップデータ保持のため、以下のようなデータを作っています（今回Cacheというフィールドが結局使っていません）。DirとStepsが重要で、ルートの結合時も使っており、方向と歩数、x、y座標を含めて一つのノードと考えています。
ワークフロー全景は以下の通り。Viz化のためにお尻に色々なツールがついています。
Part2については、一旦未解決事件として筆を置きます。ダイクストラをさらに修正するか、、、ダイクストラだと７×４＝２８倍のデータになってしまうのでもっと時間がかかってしまいそうです・・・。ということで、BFSに戻ります。今回は、方向転換時に4歩～10歩歩くルートを作ってしまう、というアルゴリズムにしました。これによりループ後に行く方向は直線が省かれるため、２方向だけになります。
Part2は、結論としてブルートフォースで行きました。ダイクストラだとデータ量が多すぎます（データ作ってみたところ、3,703,224レコードになりました・・・これは１反復結構遅くなりそうです）。
こちらは単純です。４～１０歩のルートを作って、以下のルートを捨てています。
- 過去に歩いたルートを通るルート
- 到着地点が同じで、方向、今回歩いた歩数で最小コスト意外のルート
- これまでに歩いた歩数×４よりコストが大きいもの（コストは平均４とみなしています）
- x、y座標が歩いた歩数より60歩より小さいもの
- リファレンスのコストを1000としてそれより大きいもの（結果的に900くらいにしても良かったです）
- ルートが異なるがそれ意外が同じもの（単に経路が違うだけのものは捨てられる）
結果的には、４時間かかって走りきりました。
ワークフロー全景です。
まとめ
- 結果として、最後まで残った問題となりました。
- Private Leaderboardでは、Part1は13位、Part2は14位でした。一番はやい人でも2時間30分くらいかかっています。いや、これ2時間で解けるのか、、、んー、って感じです。
- Part1から全然進みませんでした。テストでは正解が出るのに本番データでは動かない日々。結局ダイクストラ法でいきましたが、Part2をクリアした今では色々なバグがおそらくあったであろうと想定しています（Part2のデバッグでボロボロと出てきたので・・・）。
- はまった分、チューニングとかもしていたら新しい発見もありました（ソートツールは辞書を使わないと倍以上高速化される、とかデータ量が多い場合RegEx_CountMatchは使わず代替手段を使う、とか）。
- 似たような問題が、過去のAoCにもあったので流用したらできそうです（2021年15日目）。
- ダイクストラ法以外にも、A*というアルゴリズムもあるので、これでやったらもう少し高速化されそうです（Part1は）。ダイクストラ法との比較はこちらが面白いです。
- なお、今回のダイクストラ法はx、y座標用のものなので、通常のグラフ理論で使うためには改修が必要です・・・。
- 記念に貼っておきます！
コメント