Advent of Code 2022: Day 19

• The puzzle
• My solution

To be honest, this one made me give up for a long time. It’s now April and I’m just returning to it.

We have 4 robots and 4 types of resource. We need to maximise the number of geodes we can crack. Some key insights:

• For each resource R, each robot costs a certain quantity of that resource. Among those quantities, there is a maximum Q. We can only build one robot at a time, and during that time all R-producing robots produce one R; so there is no benefit in owning more than Q R-producing robots. In a state-search, we can safely prune states where we own more than Q R-producing robots.
  • We want to maximise geode-cracking robots, so there is no such maximum for geodes.
• Each state (that is, quantities of robots and ore) may be reachable via multiple paths of different lengths. There is no benefit in spending more time getting to a state. In a state-search, we can safely prune any states which have been reached at a prior point in time.