※過去記事はこちら。AlteryxユーザーのためのAdvent of Codeの始め方、１日目、２日目、３日目、４日目、５日目、６日目、７日目、８日目、９日目、１０日目、１１日目、１２日目、１３日目、１４日目、１５日目、１６日目、１７日目、１８日目
１９日目です。トップの画像は１９日目の問題が解けた画像にしています！
タイトルは、「Not Enough Minerals」。ミネラル不足。
今回の問題は、鉱石や粘土を切り出し運搬するロボットを複数作り、24分後にGeodeを最も生成できる設計書を見つける問題です。
サンプルの入力データとしては、以下のようになっています。
Blueprint 1:
Each ore robot costs 4 ore.
Each clay robot costs 2 ore.
Each obsidian robot costs 3 ore and 14 clay.
Each geode robot costs 2 ore and 7 obsidian.
Blueprint 2:
Each ore robot costs 2 ore.
Each clay robot costs 3 ore.
Each obsidian robot costs 3 ore and 8 clay.
Each geode robot costs 3 ore and 12 obsidian.これは、ロボットの設計図で、４種類のロボットがあります。それぞれのロボットを作るのに必要なレシピが書かれています。
- Oreロボット：最初から１台持っています。Oreを算出します。製作にはOreが必要です。
- Clayロボット：Clayを算出します。製作にはOreを必要とします。
- Obsidianロボット：Obsidianを算出します。製作にはOreとClayを必要とします。
- Geodeロボット：Geodeを算出します。製作にはOreとObsidianを必要とします。
各ロボットは１分に１つの対象物を生成します。また、各ロボットを制作するにも１分間かかります。
その上で、生成できるGeodeの数とBlueprintのIDをかけたものが品質レベルとなります。最終的には全レシピの品質レベルの合計を求めるのがPart1です。
Part2は、30枚あったBlueprintのうち先頭の３つだけを使います（ゾウが食べたらしいです）。そして、Part1では24分の時間がありましたが、32分の時間があるようです。この時間で作成できるGeodeの最大数を各Bluepointで算出し、3つの数を掛け算した値を取得します。
・ネ
・
・タ
・
・バ
・
・レ
解いてみる
未解決問題です。解けたらアップします。
最初、Geodeを優先して作るようなアルゴリズムを作って進める問題かと思いましたが、どのロボットを優先して作るか、それを作るために待つこともある、ということがわかり、しばらく寝かしていましたが、結局すべてのパターンを作るような方向性で解くことができました。
基本的に反復マクロでの対応ですが、各時間ごとに反復する形になります。反復するごとに５つのパターン（何もしない、Oreロボットを作る、Clayロボットを作る、Obsidianロボットを作る、Geodeロボットを作る）を実行します。とりあえず全パターン作っていくとレコード数が多くなりすぎるので、各ソースとなる鉱石が足りる場合のみに生成することでレコード数を減らしています。
また、Geodeが最大となっているパターンだけ常に抜き出すようにすることでレコード数を減らしています（これがないとデータ数が多くなりすぎて厳しかったです）。
マクロ自体はPart1、2同じものを使っています。
Part1ワークフローは以下のとおりです。
Part2はBlueprintの数を頭３つに絞って反復回数を32に増やすところと、出てきた結果の計算方法を変えるだけです。
まとめ
１９日目は一種の線形計画問題でしょうか？Geodeを算出する最大数を決めるのが簡単なアルゴリズムで自動的に出せるものではないので解き方がよくわからない感じです。- １９日目は、データ量の爆発をどう抑え込むか、という問題でした。一見、Geodeの最大数を作るパターンは一意に決まるかと思いましたが、複数のパターンでできてしまうので、単純にGeodeを効率的に作るアルゴリズムを作ろうとすると難しいかと思います。結局、すべてのパターンを作っていく形で対応しました。
- 今年の問題で一番解いた人が少ない問題です（現時点で４名）
- 個人タイム：ゆっくり時間をかけてやりました。方針を変えてからは比較的さくっとできたように思います。
コメント