Advent of Code 2022 - Day 14
Tags: adventofcode, rust, programming
Published: 2022-12-27 21:21:11

---
title: Advent of Code 2022 - Day 14
published: true
date: 2022-12-14 00:00:00 UTC
tags: adventofcode, rust, programming
canonical_url: https://www.ericburden.work/blog/2022/12/14/advent-of-code-2022-day-14/
cover_image: https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rry3cse5tb5qo53ioibz.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 14 - Regolith Reservoir

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

## The Input - Can You Smell What the Rocks Are Cooking

Today, we’ve essentially got a list of lists. Each of our lines consists of a list of x/y coordinates separated by arrows, like so:

```
498,4 -> 498,6 -> 496,6
503,4 -> 502,4 -> 502,9 -> 494,9

```

Since we want to map sand flowing over the “lines of rock” indicated by the line segments indicated as starting and ending at these points, we’ll want to collect these points and all the points in those line segments into a map of some kind. Since we’re not given the dimensions of the cave system up-front. let’s go with a `HashSet<Point>`, where a `Point` indicates a point in the 2D space of the cave.

```rust
use itertools::Itertools;
use std::cmp::Ordering;
use std::collections::HashSet;
use std::ops::{Add, AddAssign};

/// Represents a point on the 2D grid where the rocks are
#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, Hash)]
struct Point(u32, u32);

/// An offset to a point, used to adjust `Point`s
#[derive(Debug, Default, Clone, Copy)]
struct Offset(i32, i32);

impl Point {
    /// Calculate the unit offset from one `Point` to another. This represents
    /// the incremental step that, if taken repeatedly, will take you from
    /// `other` to `self`.
    fn offset_from(&self, other: &Self) -> Offset {
        let Point(x1, y1) = self;
        let Point(x2, y2) = other;
        match (x1.cmp(x2), y1.cmp(y2)) {
            (Ordering::Less, Ordering::Less) => Offset(-1, -1),
            (Ordering::Less, Ordering::Equal) => Offset(-1, 0),
            (Ordering::Less, Ordering::Greater) => Offset(-1, 1),
            (Ordering::Equal, Ordering::Less) => Offset(0, -1),
            (Ordering::Equal, Ordering::Equal) => Offset(0, 0),
            (Ordering::Equal, Ordering::Greater) => Offset(0, 1),
            (Ordering::Greater, Ordering::Less) => Offset(1, -1),
            (Ordering::Greater, Ordering::Equal) => Offset(1, 0),
            (Ordering::Greater, Ordering::Greater) => Offset(1, 1),
        }
    }
}

/// Implementation to allow adding an `Offset` to a `Point` to
/// move the `Point` in 2D space.
impl Add<Offset> for Point {
    type Output = Point;

    fn add(self, rhs: Offset) -> Self::Output {
        let Point(px, py) = self;
        let Offset(ox, oy) = rhs;
        let x = px.saturating_add_signed(ox);
        let y = py.saturating_add_signed(oy);
        Point(x, y)
    }
}

/// Module wrapping the input parser to parse lines from the input.
mod parser {
    use super::*;
    use anyhow::{anyhow, Result};
    use nom::{
        bytes::complete::tag,
        character::complete::{newline, u32},
        multi::separated_list1,
        sequence::separated_pair,
        Finish, IResult,
    };

    /// Nom parser for "15,30" -> Point(15, 30)
    fn point(s: &str) -> IResult<&str, Point> {
        let (s, (first, second)) = separated_pair(u32, tag(","), u32)(s)?;
        Ok((s, Point(first, second)))
    }

    /// Nom parser to convert a list like
    /// "15,30 -> 15,45" -> [Point(15, 30), Point(15, 45)]
    fn point_list(s: &str) -> IResult<&str, Vec<Point>> {
        separated_list1(tag(" -> "), point)(s)
    }

    /// Nom parser to convert all lines to a list of lists of `Point`s
    fn point_lists(s: &str) -> IResult<&str, Vec<Vec<Point>>> {
        separated_list1(newline, point_list)(s)
    }

    /// Parse the input file into a list of lists of `Point`s
    pub fn parse(s: &str) -> Result<Vec<Vec<Point>>> {
        let (_, result) = point_lists(s).finish().map_err(|e| anyhow!("{e}"))?;
        Ok(result)
    }
}

/// A struct to house everything we need to iterate one space on the 2D grid
/// at a time to follow a line of rocks, given by a start and end `Point`.
/// We'll use this iterator to produce all the `Point`s containing rocks
/// between `start` and `end`.
struct RockLineIter {
    start: Point, // The point where the rock line starts
    end: Point, // The point where the rock line ends
    offset: Offset, // The incremental change from `start` to `end`
    next: Option<Point>, // The next item to return from this iterator
}

/// A trait for a pair of points to implement to produce a list of rocky points
/// in the line from one point to another.
trait RockLine {
    fn rock_line(self) -> RockLineIter;
}

/// Take a pair of points and return a `RockLineIter`.
impl RockLine for (Point, Point) {
    fn rock_line(self) -> RockLineIter {
        let (start, end) = self;
        let offset = end.offset_from(&start);
        RockLineIter {
            start,
            end,
            offset,
            next: Some(start), // The first point returned is the start
        }
    }
}

/// Let `RockLineIter` be used for iteration! Produces all the points containing
/// rocks from `start` to `end`.
impl Iterator for RockLineIter {
    type Item = Point;

    fn next(&mut self) -> Option<Self::Item> {
        match self.next {
            None => None, // This is how we know when `RockLineIter` is empty
            Some(current) => {
                // If we're currently on the end point, then we've emptied the
                // iterator. Otherwise, the next point returned will be the
                // current point plus the offset.
                self.next = if current == self.end {
                    None
                } else {
                    Some(current + self.offset)
                };

                Some(current)
            }
        }
    }
}

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

/// Parse the input!
pub fn read() -> HashSet<Point> {
    // List of lists of `Point`s, basically the input file
    let point_lists = parser::parse(INPUT).unwrap();

    // The set of points that contain obstacles (rocks)
    let mut obstacles = HashSet::new();

    // For each list of `Point`s...
    for point_list in point_lists {
        // For each pair of points in that list...
        for point_pair in point_list.into_iter().tuple_windows::<(_, _)>() {
            // For each "rocky" point in the line of rocks...
            for rock_point in point_pair.rock_line() {
                // Add that rock point to the set of obstacles
                obstacles.insert(rock_point);
            }
        }
    }

    // Return our set of points that sand can't cross
    obstacles
}

```

A little bit of extra work there setting up and running the iterators for lines of rock, but worth it for the practice!

## Part One - Don’t Go Chasin’ Waterfalls

See, this is why you don’t go running into deep dark caves after mysterious distress signals. Now we’re trapped over some bottomless abyss with sand flowing down from above. Great. And we’re looking at things “just for fun”? We need professional help.

```rust
use std::collections::HashSet;

/// Solve Day 14, Part 1
fn solve(input: &HashSet<Point>) -> u32 {
    // Turn that set of impassable points into a `CaveMap`
    let mut cave_map = CaveMap::new(input.clone());

    // We'll drop up to 10K grains of sand. This is overkill, but I'd rather
    // use a `for` loop here instead of a `loop`. Mostly so I have the grain
    // number in the loop without maintaining a separate variable and mutating
    // it each loop.
    for grains in 1..10_000 {
        // When we find the first grain of sand that falls into the infinite
        // abyss, we stop and return the current grain count minus one as
        // the number of grains _before_ this poor soul was lost to the void.
        if let GrainStatus::LostToTheAbyss = cave_map.add_sand() {
            return (grains - 1);
        }
    }

    // If we ever get here, something has gone horribly wrong
    unreachable!()
}

/// This enum represents the status of a grain of sand flowing down from the
/// ceiling. May represent the result of a single step or the entire flow of
/// that grain from start to finish.
#[derive(Debug)]
enum GrainStatus {
    MovedTo(Point),
    StoppedAt(Point),
    LostToTheAbyss,
}

/// Represents the map of our cave. We're keeping up with a set of the points in
/// space that sand can't flow through in `obstacles`, the point where the sand
/// enters the map in `entrypoint`, and the y-index of the lowest point containing
/// rock in `depth`. Past that is the timeless void.
#[derive(Debug, Clone)]
struct CaveMap {
    obstacles: HashSet<Point>,
    entrypoint: Point,
    depth: u32,
}

impl CaveMap {
    /// Create a new `CaveMap` from a set of points representing impassable points
    /// in the cave (for sand).
    fn new(obstacles: HashSet<Point>) -> Self {
        // Find the lowest y-coordinate for any rock
        let depth = obstacles
            .iter()
            .map(|point| point.1)
            .max()
            .unwrap_or_default();

        // Could have been a constant...
        let entrypoint = Point(500, 0);

        CaveMap {
            obstacles,
            entrypoint,
            depth,
        }
    }

    /// Add one grain of sand to the map and follow it as it flows down. Returns
    /// the final status of the grain.
    fn add_sand(&mut self) -> GrainStatus {
        let mut sand = self.entrypoint; // Sand flows in from here

        // Infinite loop!!! It'll stop eventually (we hope).
        loop {
            // Try to flow the grain of sand down one step
            let sand_flow = self.try_move_sand(sand);

            // Do different things depending on what happened when the grain of sand
            // attempted to move down one step.
            match sand_flow {
                // If the grain moved to a new point, update the grain and keep going
                GrainStatus::MovedTo(point) => sand = point,

                // If the grain stopped moving, add it as an obstacle to the cave
                // and break the loop, returning this final status of the grain.
                GrainStatus::StoppedAt(point) => {
                    self.obstacles.insert(point);
                    break sand_flow;
                }

                // If the grain of sand is now tumbling through the dark, slowly
                // forgetting what the sun looks like, break the loop and return
                // this depressing (for the grain of sand) result.
                GrainStatus::LostToTheAbyss => break sand_flow,
            }
        }
    }

    /// Try to move a grain of sand from it's current position downwards.
    fn try_move_sand(&self, sand: Point) -> GrainStatus {
        // A grain of sand can try to move down, down-left, and down-right, in
        // that order.
        let offsets = [Offset(0, 1), Offset(-1, 1), Offset(1, 1)];

        // Try each step in order...
        for offset in offsets {
            // The position that we want the grain of sand to take
            let try_pos = sand + offset;

            // If there's an obstacle there, then try moving another direction
            if self.obstacles.contains(&try_pos) {
                continue;
            }

            // If we're at the y-coordinate representing the depth, then we know
            // there is no hope for the grain of sand and it will spin down into
            // darkness. Return this status.
            if sand.1 >= self.depth {
                return GrainStatus::LostToTheAbyss;
            }

            // If the grain were able to move to the new position, return that result.
            return GrainStatus::MovedTo(try_pos);
        }

        // If all three directions were tried and failed, this grain can go no
        // further. Return that status.
        GrainStatus::StoppedAt(sand)
    }
}

```

That poor, sacrificial grain of sand. Guess we’ll be joining him soon…

## Part Two - Don’t Look Down

Or, actually, maybe not? Turns out we neglected to map the floor _we’re currently standing on_. Just, wow. Well, I guess we got all worked up for nothing, huh? Oh, wait, we’re on the floor all the sand is flowing down to! Better count how many grains of sand can fit in here!

```rust
use std::collections::{HashSet, VecDeque};

/// Solve Day 14, Part 2
fn solve(input: &Input) -> Output {
    // Turn that set of impassable points into a `CaveMap`
    let cave_map = CaveMap::new(input.clone());

    // Now turn that `CaveMap` into a `FillMap` to determine how
    // much sand it takes to fill the pile.
    let mut fill_map = FillMap::from(cave_map);

    // Pour sand into the cave until it fills up to the entrypoint
    // and report the number of grains it took to do so.
    fill_map.sand_capacity().into()
}

/// A slight variation on the `CaveMap`. Mostly using a new struct for different
/// behaviors more than different data types.
#[derive(Debug, Clone)]
struct FillMap {
    obstacles: HashSet<Point>,
    entrypoint: Point,
    depth: u32,
}

impl FillMap {
    /// Unpack a `CaveMap` into a `FillMap`
    fn from(grid_map: CaveMap) -> Self {
        // Get the attributes from the `CaveMap`
        let CaveMap {
            obstacles,
            entrypoint,
            depth,
        } = grid_map;

        // Adjust the depth to represent the floor. Hey, look, there's that grain of
        // sand we thought was gone forever, breathing a huge sigh of relief. Good
        // for him!
        let depth = depth + 2;

        // Now it's a `FillMap`!
        FillMap {
            obstacles,
            entrypoint,
            depth,
        }
    }

    /// From a given Point, return an array indicating which points a grain of sand
    /// can flow into (e.g., that aren't blocked by an obstacle or the floor).
    fn get_neighbors(&self, point: Point) -> [Option<Point>; 3] {
        // The same three potential moves as the first part
        let offsets = [Offset(0, 1), Offset(-1, 1), Offset(1, 1)];

        // Array to hold the neighbors that can be moved to
        let mut neighbors = [None; 3];

        // For each possible offset...
        for (idx, offset) in offsets.iter().enumerate() {
            // The position we might move to.
            let try_pos = point + *offset;

            // If there's an obstacle there, skip it. Can't move there.
            if self.obstacles.contains(&try_pos) {
                continue;
            }

            // If there's floor there, skip it. Can't move there.
            if try_pos.1 >= self.depth {
                continue;
            }

            // Otherwise, we can move there. Add this point to our neighbors array.
            neighbors[idx] = Some(try_pos);
        }

        // Return the list of neighbors
        neighbors
    }

    /// Calculate the number of sand grains it'll take to fill in the pile and
    /// block off the entrypoint. Using Dijkstra's Algorithm! Nah, just kidding,
    /// it's a breadth-first search.
    fn sand_capacity(&self) -> u32 {
        let mut queue = VecDeque::from([self.entrypoint]);
        let mut visited = HashSet::new();
        let mut counted = 0; // Keep up with the number of grains

        // So long as we've got positions to try moving _from_...
        while let Some(point) = queue.pop_back() {
            // If we've visited this space before, skip it. Been here, done that.
            if visited.contains(&point) {
                continue;
            }
            visited.insert(point); // Mark `point` as visited
            counted += 1; // Count this grain of sand

            // For each reachable neighbor point from the current point
            for neighbor in self.get_neighbors(point).iter().flatten() {
                // If we've visited that point before, skip it.
                if visited.contains(neighbor) {
                    continue;
                }

                // Add that point to the list of points to visit
                queue.push_front(*neighbor);
            }
        }

        counted // Return the number of grains of sand we counted
    }
}

```

Well, given that this problem gives us a map and asks us to fill in a space with some movement rules, we can actually use a breadth-first search instead of trying to simulate each grain of sand one at a time. This basically just means simulating a lot of grains of sand all at once, really, but it’s neat that it works this way.

## Wrap Up

Today was a blast! It had everything: iterators, `nom` parsing, enums, multiple kinds of structs, and endless void, a waterfall, _and_ a graph search algorithm that, while not immediately obvious, is actually a really good solution! Looks like Advent of Code peaked early this year. I do really like the way we can create custom iterators in Rust. After using Julia for past years, I appreciate just how much more intuitive it is to have a struct with nicely named fields to store your iterator state in instead of some nebulous data structure being passed in and out of an iterator function. Given that they both work similarly, I find I prefer the Rust syntax overall. On a strange note, I noticed that my input had a bunch of duplication in it today. It turned out not to really matter since I was storing all the “rocks” in a `HashSet` which de-duplicated everything anyway, but this may have thrown a curveball to other approaches. If you’re having trouble, maybe that’s part of it. Either way, I hope you’re having as much fun as I am, and I’ll see you tomorrow!