DEV Community

Robert Mion
Robert Mion

Posted on

Not Enough Minerals

Advent of Code 2022 Day 19

Part 1

  1. Assembly line feels like assembly code
  2. Building each blueprint
  3. Could I use recursion?
  4. My recursive function's parameters
  5. Letting conditions reveal my blocker
  6. Not Enough Computer Science Skills

Assembly line feels like assembly code

I'm not feeling great about this puzzle:

  • Each blueprint requires playing out several scenarios
  • Meaning, underlying all of this is a graph data structure filled with each possible move available in each subsequent minute for each blueprint
  • I'm not well-practiced in graphs
  • I'm still intimidated by recursion and search algorithms

Working in my favor:

  • I understand the problem
  • I know I can parse the list of blueprints into a dictionary of the mineral costs of each robot
  • I sense I could play out a scenario where the moment a robot capable of making a mineral of the next type can be made, my code would make it

The problem comes in the branches where the factory could choose to wait for more resources to make more of a lesser-type robot instead of one that is closer to a geode robot.

Let's see how this goes, and how far I get!

Building each blueprint

  • The example input features convenient line breaks
  • My puzzle input does not
  • This should be a doozy

Thankfully, the list of robots is in the same order.

Example:

Blueprint 1: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 16 clay. Each geode robot costs 3 ore and 20 obsidian.
Enter fullscreen mode Exit fullscreen mode

Oh, and it looks like each line features exactly 7 numbers!

Wow, then this is a simple regex!

/\d+/g
Enter fullscreen mode Exit fullscreen mode

That matches each digit.

I can then de-structure each one as a variable:

let [
  id, 
  oreRobotOreCost,
  clayRobotOreCost,
  obsidianRobotOreCost,
  obsidianRobotClayCost,
  geodeRobotOreCost,
  geodeRobotObsidianCost
] = [...blueprint.matchAll(/\d+/g)]
     .map(match => +match[0])
Enter fullscreen mode Exit fullscreen mode

Could I use recursion?

  • I need to simulate 24 minutes of a factory running a blueprint
  • Each blueprint can produce different types of robots depending on how much minerals the produced robots have generated
  • I therefore also need to play out (all?) branches for each blueprint to identify the one that eventually produces the most geode-collecting robots
  • This smells like recursion to me
  • It's a stinky smell
  • But I gotta wade through it either long enough to survive or until I hit an insurmountable algorithmic hurdle

My recursive function's parameters

I think I need to track:

  • The current minute
  • The minerals collected thus far
  • The robot types - and quantity - produced thus far

My legend of mineral requirements is in a local scope that the function can always access.

And I'll externally track and update the largest number of geode robots producible from the already-explored blueprint's scenarios.

Next, how will I use and update these parameters to successfully play out a scenario?

Letting conditions reveal my blocker

  • I started building conditions related to how much of a particular mineral I had collected
  • Doing this revealed a gap in my algorithm
  • I have no idea how to account for that gap

That gap:

  • How could I programmatically tell my algorithm when to build a robot or when to wait, collect more minerals, and build a different robot?

Not Enough Computer Science Skills

I truly feel stumped as to how to solve this problem using an algorithm.

Sadly, I have to turn away empty-handed from another puzzle.

This is feeling like the toughest year of puzzles thus far.

Top comments (0)