# Advent of Code 2022 - Day 18

By Eric Burden | December 19, 2022

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 18 - Boiling Boulders

Find the problem description HERE.

## The Input - A “Notch” In Your Belt

Ooh, goody. Today we’re dealing with voxels! Parsing input today is pretty straightforward. Just three numbers, separated by commas. Given that I’m trying to catch up on blog posts, that’s all the exposition you’re getting today!


/// Represents a 1x1x1 cube in 3D space
#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, Hash)]
struct Cube(i32, i32, i32);

// Just some convenience functions for working with Cubes
impl Cube {
fn new(x: i32, y: i32, z: i32) -> Self {
Cube(x, y, z)
}

fn inner(&self) -> (i32, i32, i32) {
let Cube(x, y, z) = self;
(*x, *y, *z)
}
}

/// Convert a tuple of i32s into a Cube
impl From<(i32, i32, i32)> for Cube {
fn from(value: (i32, i32, i32)) -> Self {
let (x, y, z) = value;
Cube(x, y, z)
}
}

/// Module wrapping the parsing functions for today's puzzle input
mod parser {
use super::*;
use anyhow::{anyhow, Result};
use nom::{
branch::alt,
bytes::complete::tag,
character::complete::{i32, newline},
combinator::map,
multi::separated_list0,
sequence::{terminated, tuple},
Finish, IResult,
};
use std::collections::HashSet;

/// Nom parser for ("5," || "5") -> 5i32
fn number(s: &str) -> IResult<&str, i32> {
alt((terminated(i32, tag(",")), i32))(s)
}

/// Nom parser for "1,2,3" -> (1, 2, 3)
fn coordinates(s: &str) -> IResult<&str, (i32, i32, i32)> {
// Using tuple instead of separated_list1 here because I want
// to avoid allocating the Vec
tuple((number, number, number))(s)
}

/// Nom parser for "1,2,3" -> Cube(1, 2, 3)
fn cube(s: &str) -> IResult<&str, Cube> {
map(coordinates, Cube::from)(s)
}

/// Parses a list of input lines into a list of Cubes
fn cubes(s: &str) -> IResult<&str, Vec<Cube>> {
separated_list0(newline, cube)(s)
}

/// Parses the input file into a HashSet of Cubes
pub fn parse(s: &str) -> Result<HashSet<Cube>> {
let (_, result) = cubes(s).finish().map_err(|e| anyhow!("{e}"))?;
Ok(result.into_iter().collect::<HashSet<_>>())
}
}

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

/// Parse that input!
fn read() -> HashSet<Cube> {
parser::parse(INPUT).unwrap()
}


That’s it, 3D points. Now, on to the show…

## Part One - Drop It Like It’s Hot

Ah, yes. When one finds oneself standing underneath flying globs of lava, the only reasonable reaction is to estimate their volumes! Clearly. The elephants are on-board, so seems like it must be a good idea. The tricky bit here is that we can’t count on all the little blobbies to be connected, so we’ll need to account for that.

use std::collections::HashSet;
use std::ops::Add;

/// Solve Day 18, Part 1
fn solve(input: &HashSet<Cube>) -> u32 {
let mut surface_area = 0;

// For each cube in the input, look at each cube that shares
// a face with it. For every one of those neighboring cubes that
// is not lava, add one to the total surface area.
for cube in input.iter() {
for neighbor in cube.neighbors() {
if !input.contains(&neighbor) {
surface_area += 1;
}
}
}

surface_area
}

/// Represents an offset used to adjust a Cube location
#[derive(Debug, Clone, Copy)]
struct Offset(i32, i32, i32);

impl Offset {
/// All the offsets of interest. Provides the offsets that will result
/// in a Cube that shares a face with an existing Cube.
const fn all() -> [Offset; 6] {
[
Offset(-1, 0, 0),
Offset(1, 0, 0),
Offset(0, -1, 0),
Offset(0, 1, 0),
Offset(0, 0, -1),
Offset(0, 0, 1),
]
}

/// Convenience!
fn new(x: i32, y: i32, z: i32) -> Self {
Offset(x, y, z)
}

/// Convenience!
fn inner(&self) -> (i32, i32, i32) {
let Offset(x, y, z) = self;
(*x, *y, *z)
}
}

/// Allows for adding an Offset to a Cube to get a Cube offset from the original
impl Add<Offset> for Cube {
type Output = Cube;

fn add(self, offset: Offset) -> Self::Output {
let (cx, cy, cz) = self.inner();
let (ox, oy, oz) = offset.inner();
let x = cx + ox;
let y = cy + oy;
let z = cz + oz;

Cube::new(x, y, z)
}
}

impl Cube {
/// Get all the neighboring Cubes that share a face with this one.
fn neighbors(&self) -> [Cube; 6] {
let mut cubes = [Cube::default(); 6];
let offsets = Offset::all();
for (slot, offset) in cubes.iter_mut().zip(offsets.iter()) {
*slot = *self + *offset;
}
cubes
}
}


Turns out, we can account for that by checking each little voxel individually. Well, that wasn’t so bad. What about part two?

## Part Two - It’s What’s on the Outside That Counts

Turns out, not all the lava is exposed to the open air, some of it is exposed to the “closed” air, i.e. the inside of the blob. No worries, we can find the outside of the blob by searching the area around the blob.

use std::collections::HashSet;
use std::ops::RangeInclusive;

/// Solve Day 18, Part 2
fn solve(input: &HashSet<Cube>) -> u32 {
// Identify the bounding box that contains all the Cubes for the lava
// plus at least one extra in each dimension.
let bounds = input.get_bounds();

// Adding up surface area, like before
let mut surface_area = 0;

// Prepare for a Depth-First Search through all the Cubes that are within
// the bounding box but that _aren't_ lava. Each "air" cube that touches
// a lava cube adds one to the total observed surface area.
let mut stack = Vec::with_capacity(input.len() * 2);
let mut seen = HashSet::with_capacity(input.len() * 2);

// This isn't technically a corner of the bounding box or anything, but
// I checked my input and there isn't any lava at this location. It really
// doesn't matter _where_ you start the search, so long as it's a Cube
// outside the lava blob.
let start = Cube::new(0, 0, 0);
stack.push(start);

// So long as there are still Cubes outside the lava blob to check...
while let Some(cube) = stack.pop() {
// If the cube we're on has already been explored or it falls outside
// the bounding box, skip it.
if seen.contains(&cube) || !bounds.contains(&cube) {
continue;
}

// If the cube we're on contains lava, then we add one to our surface area
// and move on. We don't want to explore the lava-containing cubes.
if input.contains(&cube) {
surface_area += 1;
continue;
}

seen.insert(cube);

// For each cube that shares a face with the current Cube, if we haven't
// explored it already, add it to the stack for later exploration.
for neighbor in cube.neighbors() {
if seen.contains(&neighbor) {
continue;
}
stack.push(neighbor);
}
}

surface_area
}

/// Represents the 3D range that contains all the air Cubes we want to explore,
/// encapsulating the lava Cubes.
struct Bounds(
RangeInclusive<i32>,
RangeInclusive<i32>,
RangeInclusive<i32>,
);

/// This trait provides a convenient way to get the bounding box of
/// a HashSet of Cubes
trait GetBounds {
fn get_bounds(&self) -> Bounds;
}

impl GetBounds for &HashSet<Cube> {
/// Nothing fancy here. Identify the minimim and maximum values on each axis
/// for all the lava-containing cubes, then set the bounding box to be one
/// greater in each dimension. This leaves a one-wide gap around the lava
/// blob that is OK to explore.
fn get_bounds(&self) -> Bounds {
let (mut min_x, mut max_x) = (0, 0);
let (mut min_y, mut max_y) = (0, 0);
let (mut min_z, mut max_z) = (0, 0);

for cube in self.iter() {
let (x, y, z) = cube.inner();
min_x = min_x.min(x);
max_x = max_x.max(x);
min_y = min_y.min(y);
max_y = max_y.max(y);
min_z = min_z.min(z);
max_z = max_z.max(z);
}

let x_range = (min_x - 1)..=(max_x + 1);
let y_range = (min_y - 1)..=(max_y + 1);
let z_range = (min_z - 1)..=(max_z + 1);

Bounds(x_range, y_range, z_range)
}
}

impl Bounds {
/// Indicates whether a Cube lies within the Bounds
fn contains(&self, cube: &Cube) -> bool {
let (x, y, z) = cube.inner();
let Bounds(x_range, y_range, z_range) = self;
x_range.contains(&x) && y_range.contains(&y) && z_range.contains(&z)
}
}


For some reason, I’m unreasonably fond of that little Bounds struct. I really can’t put a finger on why I like it so much, but I do like it.

## Wrap Up

Well, I’m getting this blog post out late on the day after this puzzle was released, so I’m clearly a bit behind. Today was a bit of a breather, which I appreciate. Since it’s the day after, I can give you a dispatch from the future: tomorrow is going to be a tough one. Get ready!

comments powered by Disqus