It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Rust. I’ll post my solutions and code to GitHub as well. After finishing last year (and 2015-2019) in Julia, 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.
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!
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.
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 threeBlueprints left to check. So, we check the first three blueprints for 32 minutes each. Otherwise, it’s the same as part one.
/// 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 rayonfor parallel procesing, and the absolute delight that was the ResourceCountArray, this was a pretty good day.
Top comments (0)