Module aoc::year2022::day19

Not Enough Minerals

The solution is branch and bound using a depth first search to enumerate every possible combination combined with heuristics to prune those combinations in order to achieve a reasonable running time.

The most import heuristic is:

• Assume ore is infinite.
• Always build a clay robot.
• Check if we can do better than the highest score so far in the remaining time, building only geode or obsidian bots.

As these simplified rules will always score higher than the real rules, we can immediately prune any branch that can’t possibly exceed the current high score.

The second helpful heuristic is:

• Don’t build more bots for a particular mineral than the maximum possible consumption in a single turn.

As we can only build one bot per turn, we will never need to generate more resources than that bot can use. For example, if ore robots need 2 ore, clay robots 3 ore, obsidian robots 4 ore and geode robots 5 ore, then the most possible ore robots that we need to build is 5. Any more would go to waste. The same applies for clay and obsidian.

The third helpful heuristic is:

• Don’t build any robot during the last minute
• Don’t build ore or obsidian robots during the last 3 minutes.
• Don’t build clay robots during the last 5 minutes.

Building any robot during the last minute means that it will be ready after the time runs out so it will contribute nothing. The other two rules are corollaries of this rule.

For example say we build an obsidian robot with 3 minutes left. It will be ready and collect a resource with two minutes left, which can be spent on a geode robot with 1 minute left, which is too late.

Since we only need clay for obsidian robots it doesn’t make sense to build clay robots less than two minutes before the cutoff for obsidian robots.

The final important optimization is that we don’t increment minute by minute. Instead once we decide to buld a robot of a particular type, we “fast forward” in time until there are enough resources to build that robot. This cuts down on a lot of duplicate intermediate states.

Structs

• Blueprint
• Mineral 🔒

Constants

• CLAY_BOT 🔒
• GEODE_BOT 🔒
• OBSIDIAN_BOT 🔒
• ORE_BOT 🔒
• ZERO 🔒
  Each robot generates 1 mineral of a particular type.

Functions

• dfs 🔒
  Depth first search over every possible combination pruning branches using heuristics.
• heuristic 🔒
  Simplify the blueprints so that we only attempt to build either geode or obsidian robots, then check that the estimated maximum possible score is greater than the current high score. Additionally we always build a clay robot each turn.
• maximize 🔒
• next 🔒
  “Fast forward” in time until we can build a robot of a particular type. This could possibly by the next minute if we already have enough resources.
• parse
• part1
• part2