Advent of Code 2022 - Day 19
Tags: adventofcode, rust, programming
Published: 2022-12-27 21:28:02

---
title: Advent of Code 2022 - Day 19
published: true
date: 2022-12-21 00:00:00 UTC
tags: adventofcode, rust, programming
canonical_url: https://www.ericburden.work/blog/2022/12/21/advent-of-code-2022-day-19/
cover_image: https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8xg0grid1txp71r4p7w3.png
---

It’s that time of year again! Just like last year, I’ll be posting my solutions to the [Advent of Code](https://adventofcode.com/) puzzles. This year, I’ll be solving the puzzles in [Rust](https://www.rust-lang.org/). I’ll post my solutions and code to [GitHub](https://github.com/ericwburden/advent_of_code_2022) as well. After finishing last year (and 2015-2019) in [Julia](https://julialang.org/), I needed to spend some time with Rust again! If you haven’t given AoC a try, I encourage you to do so along with me!

# Day 19 - Not Enough Minerals

Find the problem description [HERE](https://adventofcode.com/2022/day/19).

## The Input - I Like The Way You Array

I hope you like code, because there’s a bunch of it today! For the inputs, the actual parsing bit really isn’t so bad. Each line has 5 sections, the first section indicates the blueprint ID and the remaining four sections indicate the recipes for making various robots. No, the interesting bit is just how darn useful it is to be able to define your own types and implement traits for them for various useful things. For example, I had no idea how handy it could be to index a wrapped array with an `enum`! Now, the code can be much more expressive!

```rust
use std::ops::{Add, AddAssign, Index, IndexMut, Mul, Sub, SubAssign};

/// Represents one of the resource types we're dealing with today.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Resource {
    Ore,
    Clay,
    Obsidian,
    Geode,
}

/// This little newtype right here is the star of today's show, as
/// if you couldn't tell by all the basic arithmetic trait implementations
/// down below. This fella is being used to represent the number of
/// robots we have active, the number of resources we've gathered, and
/// the recipe costs for making new robots. Who knew one little array
/// could be so versatile!
#[derive(Debug, Default, Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Hash)]
struct ResourceCountArray([u32; 4]);

/*----------------------------------------------------------------------------------
* This section contains a whole bunch of trait implementations for our hero, the
* ResourceCountArray. We can index the array by resource type, add them together,
* subtract them, multiply them by a scalar, and iterate over them. Truly a marvel!
*/

impl Index<Resource> for ResourceCountArray {
    type Output = u32;

    fn index(&self, index: Resource) -> &Self::Output {
        match index {
            Resource::Ore => &self.0[0],
            Resource::Clay => &self.0[1],
            Resource::Obsidian => &self.0[2],
            Resource::Geode => &self.0[3],
        }
    }
}

impl IndexMut<Resource> for ResourceCountArray {
    fn index_mut(&mut self, index: Resource) -> &mut Self::Output {
        match index {
            Resource::Ore => &mut self.0[0],
            Resource::Clay => &mut self.0[1],
            Resource::Obsidian => &mut self.0[2],
            Resource::Geode => &mut self.0[3],
        }
    }
}

impl Index<usize> for ResourceCountArray {
    type Output = u32;

    fn index(&self, index: usize) -> &Self::Output {
        &self.0[index]
    }
}

impl IndexMut<usize> for ResourceCountArray {
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        &mut self.0[index]
    }
}

impl Add<ResourceCountArray> for ResourceCountArray {
    type Output = ResourceCountArray;

    fn add(self, other: ResourceCountArray) -> Self::Output {
        let mut sum: ResourceCountArray = Default::default();
        for (idx, (lhs, rhs)) in self.into_iter().zip(other.into_iter()).enumerate() {
            sum[idx] = lhs + rhs;
        }
        sum
    }
}

impl AddAssign<ResourceCountArray> for ResourceCountArray {
    fn add_assign(&mut self, rhs: ResourceCountArray) {
        for (idx, value) in rhs.into_iter().enumerate() {
            self[idx] += value;
        }
    }
}

impl SubAssign<ResourceCountArray> for ResourceCountArray {
    fn sub_assign(&mut self, rhs: ResourceCountArray) {
        for (idx, value) in rhs.into_iter().enumerate() {
            self[idx] -= value;
        }
    }
}

impl Mul<u32> for ResourceCountArray {
    type Output = ResourceCountArray;

    fn mul(self, rhs: u32) -> Self::Output {
        let mut product: ResourceCountArray = Default::default();
        for (idx, value) in self.into_iter().enumerate() {
            product[idx] = self[idx] * rhs;
        }
        product
    }
}

impl IntoIterator for ResourceCountArray {
    type Item = u32;
    type IntoIter = std::array::IntoIter<Self::Item, 4>;

    fn into_iter(self) -> Self::IntoIter {
        self.0.into_iter()
    }
}

/* -----------------------------------------------------------------------------------
* Ok, back to normal non-trait stuff.
*/

impl ResourceCountArray {
    /// But only because _saturating_sub()_ isn't from a trait. We needed this one
    /// for a _very_ important performance optimization, though. You'll see that in
    /// the code for part one.
    fn saturating_sub(&self, other: ResourceCountArray) -> ResourceCountArray {
        let mut difference: ResourceCountArray = Default::default();
        for (idx, (lhs, rhs)) in self.into_iter().zip(other.into_iter()).enumerate() {
            difference[idx] = lhs.saturating_sub(rhs);
        }
        difference
    }
}

/// Represents a recipe for making a new robot
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Recipe {
    bot: Resource,
    cost: ResourceCountArray, // See, everywere.
}

/// Represents an entire blueprint, with ID and recipe for each bot type.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Blueprint {
    id: u32,
    recipes: [Recipe; 4],
}

/// The usual module wrapping the parsers for today's input. I'll be honest, the whole
/// inner module thing still seems a little odd to me, but it's the best way I could
/// come up with to namespace the parsing functions so far. So, I'm keeping it until
/// I can think of (or steal) a better idea.
mod parser {
    use super::*;
    use anyhow::{anyhow, Result};
    use nom::{
        branch::alt,
        bytes::complete::tag,
        character::complete::{newline, space1, u32},
        combinator::{opt, value},
        multi::separated_list0,
        sequence::{delimited, pair, preceded, separated_pair, tuple},
        Finish, IResult,
    };

    /// Nom parser for "ore" -> Resource::Ore
    fn ore(s: &str) -> IResult<&str, Resource> {
        value(Resource::Ore, tag("ore"))(s)
    }

    /// Nom parser for "clay" -> Resource::Clay
    fn clay(s: &str) -> IResult<&str, Resource> {
        value(Resource::Clay, tag("clay"))(s)
    }

    /// Nom parser for "obsidian" -> Resource::Obsidian
    fn obsidian(s: &str) -> IResult<&str, Resource> {
        value(Resource::Obsidian, tag("obsidian"))(s)
    }

    /// Nom parser for "geode" -> Resource::Geode
    fn geode(s: &str) -> IResult<&str, Resource> {
        value(Resource::Geode, tag("geode"))(s)
    }

    /// Parses any resource name into the relevant `Resource`
    fn resource(s: &str) -> IResult<&str, Resource> {
        alt((ore, clay, obsidian, geode))(s)
    }

    /// Nom parser for "4 ore" -> ResourceCountArray([4, 0, 0, 0])
    fn cost(s: &str) -> IResult<&str, ResourceCountArray> {
        let (s, (amt, resource)) = separated_pair(u32, space1, resource)(s)?;
        let mut cost: ResourceCountArray = Default::default();
        cost[resource] += amt;
        Ok((s, cost))
    }

    /// Nom parser for "3 ore and 14 clay" -> ResourceCountArray([3, 14, 0, 0])
    fn cost2(s: &str) -> IResult<&str, ResourceCountArray> {
        let mut resources: ResourceCountArray = Default::default();
        let (s, (cost1, cost2)) = separated_pair(cost, tag(" and "), cost)(s)?;
        Ok((s, cost1 + cost2))
    }

    /// Nom parser for
    /// "Each ore robot costs 4 ore"
    /// -> Recipe { bot: Resource::Ore, cost: ResourceCountArray([4, 0, 0, 0]) }
    fn recipe(s: &str) -> IResult<&str, Recipe> {
        let (s, _) = tag("Each ")(s)?;
        let (s, bot) = resource(s)?;
        let (s, _) = tag(" robot costs ")(s)?;
        let (s, cost) = alt((cost2, cost))(s)?;
        let (s, _) = tag(".")(s)?;
        Ok((s, Recipe { bot, cost }))
    }

    /// Nom parser for all four recipes from a line
    fn recipes(s: &str) -> IResult<&str, [Recipe; 4]> {
        let (s, (r1, r2, r3, r4)) = tuple((
            preceded(space1, recipe),
            preceded(space1, recipe),
            preceded(space1, recipe),
            preceded(space1, recipe),
        ))(s)?;
        Ok((s, [r1, r2, r3, r4]))
    }

    /// Nom parser for a single line of the input, producing a Blueprint
    fn blueprint(s: &str) -> IResult<&str, Blueprint> {
        let (s, id) = delimited(tag("Blueprint "), u32, tag(":"))(s)?;
        let (s, recipes) = recipes(s)?;
        Ok((s, Blueprint { id, recipes }))
    }

    /// Parses each line of the input into a Blueprint and return the list
    fn blueprints(s: &str) -> IResult<&str, Vec<Blueprint>> {
        separated_list0(newline, blueprint)(s)
    }

    /// Entrypoint for the parsing functions
    fn parse(s: &str) -> Result<Vec<Blueprint>> {
        let (_, result) = blueprints(s).finish().map_err(|e| anyhow!("{e}"))?;
        Ok(result)
    }
}

const INPUT: &str = include_str!("../../input/19/input.txt");

/// Parse that input
fn read() -> Vec<Blueprint> {
    parser::parse(INPUT).unwrap()
}

```

We don’t actually _use_ all those implementations while parsing the input, but we’ll use them in the actual puzzle. The code for part one is already cluttered enough though, and it’s enough to know ahead of time how these various operations work on the `ResourceCountArray`.

## Part One - Oh Factory, My Factory

Looks like the blobs of superheated molten rock have stopped randomly flying through the air, so that’s good, I guess. But, you know what would be even better? Collecting some of that obsidian! Plus, if we get enough of it, we can probably build a nether portal to helps us get out of this jungle. The puzzle doesn’t say, but I assume the elephants are on board with this bit of a delay, since they didn’t seem to mind playing a gazillion rounds of rock Tetris with us a couple days ago.

```rust
use rayon::prelude::*;
use std::collections::{BinaryHeap, HashMap, HashSet};
use std::iter::zip;
use std::ops::{Index, IndexMut};
use Resource::*;

/// Solve Day 19, Part 1
///
/// I finally found a good an legitimate use for `rayon`! I probably could have used
/// parallel processing on Day 16, too. May try that later. Here, though, we can
/// process each blueprint in parallel, really helping with speed.
fn solve(input: &Vec<Blueprint>) -> u32 {
    input
        .par_iter()
        .map(|blueprint| Factory::new(*blueprint, 24))
        .map(|factory| factory.quality_level())
        .sum::<u32>()
}

/// It's a Factory that produces Factories! Represents each state of resource
/// production and includes the original blueprint, the number of turns remaining,
/// the current bot count, the current stockpile of resources, and the total number
/// of each type of resource produced.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Factory {
    blueprint: Blueprint,
    remaining: u32,
    bots: ResourceCountArray,
    stockpile: ResourceCountArray,
    produced: ResourceCountArray,
}

/// Sorting for Factory, so that the state closest to completion floats to
/// the top of the Binary Heap we'll use for the graph search algorithm. "Greater"
/// values for Factory are those where the most geodes can possibly be produced
/// using the best-guess estimate.
impl Ord for Factory {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        let self_estimate = self.best_estimate(Geode);
        let other_estimate = other.best_estimate(Geode);
        self_estimate.cmp(&other_estimate)
    }
}

impl PartialOrd for Factory {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Factory {
    /// Create a new Factory!
    fn new(blueprint: Blueprint, time: u32) -> Self {
        Factory {
            blueprint,
            remaining: time,
            bots: ResourceCountArray([1, 0, 0, 0]),
            stockpile: Default::default(),
            produced: Default::default(),
        }
    }

    /// Try to produce a bot from the given recipe. Attempts to fast-forward the
    /// state until the given bot is produced, if it can be. There are a few
    /// different guard clauses that aim to prevent creating new states that won't
    /// lead to the optimal solution.
    fn produce_recipe(&self, recipe: Recipe) -> Option<Factory> {
        let Recipe { bot, cost } = recipe;

        // Don't produce this recipe if the factory can't produce enough
        // resources to build this bot
        let max_production = (self.bots * self.remaining) + self.stockpile;
        if zip(cost, max_production).any(|(lhs, rhs)| lhs > rhs) {
            return None;
        }

        // If there's only one turn left, then skip it. This factory won't
        // produce anything else.
        if self.remaining == 1 {
            return None;
        }

        // If this factory could have produced the current recipe in its last
        // incarnation, then it should have produced that bot back then. Too
        // late, now!
        let last_turn_resources = self.stockpile.saturating_sub(self.bots);
        if zip(cost, last_turn_resources)
            .filter(|(lhs, _)| *lhs > 0)
            .all(|(lhs, rhs)| lhs < rhs)
        {
            return None;
        }

        /// If we're actually going to produce this bot, we need to advance the
        /// current Factory state minute-by-minute until we've gathered enough
        /// resources to produce the bot. Then we pay the price, produce the bot,
        /// and return the state.
        let mut new_state = *self;
        while new_state.remaining > 0 && self.bots == new_state.bots {
            let available = new_state.stockpile;
            new_state.remaining -= 1;
            new_state.stockpile += new_state.bots;
            new_state.produced += new_state.bots;

            if zip(available, cost).all(|(lhs, rhs)| lhs >= rhs) {
                new_state.bots[bot] += 1;
                new_state.stockpile -= cost;
            }
        }

        Some(new_state)
    }

    /// Identify all the next states that can be reached from the current Factory.
    /// Tries to produce one of each bot and includes a "wait" state where the
    /// Factory just lets time run out. This is for cases when not enough resources
    /// will be generated to produce any more bots before time runs out.
    fn next_states(&self) -> impl Iterator<Item = Factory> + '_ {
        let mut wait_state = *self;
        wait_state.stockpile += self.bots * self.remaining;
        wait_state.produced += self.bots * self.remaining;
        wait_state.remaining = 0;

        let wait_state_iter = std::iter::once(wait_state);

        self.blueprint
            .recipes
            .into_iter()
            .flat_map(|recipe| self.produce_recipe(recipe))
            .chain(wait_state_iter)
    }

    /// Identify the most possible resources of a given type that could be
    /// produced under ideal circumstances.
    fn best_estimate(&self, resource: Resource) -> u32 {
        // Assume that we can make one new bot per minute for
        // the remaining time. In that perfect scenario, how many
        // `resource` would we have a the end of time?
        // This is also our A* heuristic, which will always _overestimate_
        // how close we are to the goal. We're using a max heap,
        // so we need to overestimate to get an admissible heuristic.
        let resource_bots = self.bots[resource] + self.remaining;
        let new_resources = resource_bots * self.remaining;
        new_resources + self.produced[resource]
    }

    /// This is our unique identifier for a given Factory. It's the simplest
    /// value that identifies a Factory uniquely _enough_ to find the right
    /// solution.
    fn key(&self) -> ResourceCountArray {
        self.bots + self.produced
    }

    /// Performs a modified A* search through the possible Factory states,
    /// seeking a state that produces the most possible geodes.
    fn geodes_produced(&self) -> u32 {
        let mut heap = BinaryHeap::from([*self]);
        let mut seen = HashSet::new();
        let mut most_geodes = 0; // Used for optimization

        // So long as the heap still has items on it...
        while let Some(state) = heap.pop() {
            // If we reached a state where time runs out, we've identified
            // the state producing the most geodes, assuming we've implemented
            // the ordering of Factories correctly.
            if state.remaining == 0 {
                return state.stockpile[Geode];
            }

            // If we've seen this state already, skip it.
            if seen.contains(&state.key()) {
                continue;
            }

            // Otherwise, mark it as seen. Update the most geodes produced
            // by any state seen so far.
            seen.insert(state.key());
            most_geodes = most_geodes.max(state.produced[Geode]);

            for next_state in state.next_states() {
                // If we've seen this `next_state` before, skip it.
                if seen.contains(&next_state.key()) {
                    continue;
                }

                // If the best possible geode production for this state is still
                // less than the most geodes we've actually seen in a state so
                // far, skip it. The best estimate is an overestimate by design.
                if next_state.best_estimate(Geode) < most_geodes {
                    continue;
                }

                // Add this state to the heap to be checked.
                heap.push(next_state);
            }
        }

        // This should never happen
        unreachable!()
    }

    /// Calcualate the quality level of this Factory
    fn quality_level(&self) -> u32 {
        self.blueprint.id * self.geodes_produced()
    }
}
```

There’s a lot of code going into that, but the crux of it is a modified A\* search through the interesting states of a graph, with some aggressive pruning of branches that can’t lead to the desired outcome of maximum obsidian gains. The trickiest bits were actually identifying the criteria for pruning branches as well as what value or values from the `Factory` would provide a sufficiently unique identifier without being _so_ unique that we couldn’t really keep up with which states we’d seen before. Overall, this one required quite a bit of tuning, but I’m happy with how it turned out.

## Part Two - Hungry Hungry Heffalumps

Looks like the elephants weren’t as on board with this process as we previously thought. Hope those blueprints tasted bad. Luckily, now they’re all fibered up and we have an extra eight minutes or so to run our Factory and three`Blueprint`s left to check. So, we check the first three blueprints for 32 minutes each. Otherwise, it’s the same as part one.

```rust
/// Solve Day 19, Part 2
pub fn solve(input: &Input) -> u32 {
    // That's right, it's basically the same as part one, with the slight
    // modifications that we're only examining the first three blueprints,
    // keeping the number of geodes per Blueprint as opposed to the quality
    // level, and multiplying instead of adding the results.
    input
        .par_iter()
        .take(3)
        .map(|blueprint| Factory::new(*blueprint, 32))
        .map(|factory| factory.geodes_produced())
        .product::<u32>()
}
```

Nailed it!

## Wrap Up

Today’s puzzle was an exercise in absolute frustration as my initial solution to this puzzle was pretty quickly achieved (for me), but the total runtime for input parsing and solving both parts was ~2.5 _seconds_! That’s unacceptably slow, which sparked the quest for the right optimizations. I tried a fair number of things, but the biggest performance gains came from choosing the right key for the `seen` list, skipping branches that couldn’t afford to build the bot I wanted _ever_, and skipping branches that could have produced a bot in a prior round but didn’t. Taken all together, I got runtime down to about 86ms, which was a massive improvement. Between that, the chance to use `rayon`for parallel procesing, and the absolute delight that was the `ResourceCountArray`, this was a pretty good day.