Advent of Code 2022 - Day 05

By Eric Burden | December 5, 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 05 - Supply Stacks

Find the problem description HERE.

The Input - Stack Attack

Well, this is just gnarly. I’ll be honest, the biggest reason I went through the exercise of writing nom parsers for both the crate stacks and the moving instructions below is because I kept saying out loud that I definitely wanted to practice parsing with nom. Thanks, Eric Wastl! Given the relatively complicated nature of input parsing in today’s puzzle, let’s take it in parts.

Input Structures - No Clever Subtitle

The first thing to get out of the way is the shape of the structures we want to parse the input into. I’ve probably (definitely) overcomplicated the input structures a bit in a bid for a more performant solution, but by now I’m tired of re-factoring it, so here’s what you get:


/// Represents a stack of crates. Each crate is represented by the character
/// given in the input. A stack is a 64-length array (enough room for all the
/// crates if need be) that keeps track of the current height of the stack.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct CrateStack {
    crates: [char; 64],
    height: usize,
}

/// By default, all crates are set to '.', indicating an empty space in the
/// buffer. I "opted" not to use options here because the code was already
/// getting complex enough without it. There are a number of other truly
/// advisable safety features that I've left out of today's puzzle implementation.
impl Default for CrateStack {
    fn default() -> Self {
        Self {
            crates: ['.'; 64],
            height: 0,
        }
    }
}

/// Represents the collected stacks of crates. We know we have 9 total stacks from
/// the input, so this data structure can accommodate up to 9 stacks of crates.
/// Each stack of crates is wrapped in `RefCell` to facilitate moving crates directly
/// from one stack to the other without needing a buffer in between. We'll use this
/// functionality in part two.
#[derive(Debug, Default, Clone)]
struct CrateStacks(pub [RefCell<CrateStack>; 9]);

/// Implement indexing into the `CrateStacks` to get a particular crate. Since stack
/// numbers are given 1-9, we can adjust the index here to allow for 1-indexing for
/// getting a particular stack of crates.
impl Index<usize> for CrateStacks {
    type Output = RefCell<CrateStack>;

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

/// Same as `Index`, just mutable! This is really the important one, but we need
/// both.
impl IndexMut<usize> for CrateStacks {
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        &mut self.0[index - 1]
    }
}


/// An Instruction represents the instructions to move one or more crates from
/// one stack to another. Includes how many crates to move, which stack to move
/// them from, and which stack to move them to.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Instruction {
    count: u8,
    origin: u8,
    destination: u8,
}

/// Conveniently convert a three-tuple of numbers to an `Instruction`
impl From<(u8, u8, u8)> for Instruction {
    fn from(value: (u8, u8, u8)) -> Self {
        let (count, origin, destination) = value;
        Instruction {
            count,
            origin,
            destination,
        }
    }
}

Conceptually, a CrateStack is just a Vec<char> with a hard limit of 64 items, which is more crates than we have, so no need to worry about that here. CratesStacks is just a collection of all the stacks of crates with 1-based indexing to accommodate the stack numbers from the input, and an Instruction is just the numbers from each line of the second part of the input, in order.

Crates - Teetering Towers

This is the hard part. In large part this is tough because we want to store each stack of crates bottom to top, but we read text left to right. This means reading in each row of crates, then transposing them into stacks. The other confounding factor is the fact that there is no placeholder for missing crates when stacks are differing heights. After more than a bit of fiddling, though, I settled on a set of parsers I’m pretty happy with.

/// I like wrapping nom parsers into their own modules. I definitely tried putting
/// these into an impl for an empty struct, but I didn't care for that style.
mod parse_crates {
    use super::*;
    use anyhow::{anyhow, Result};
    use nom::{
        branch::alt,
        bytes::complete::tag,
        character::complete::satisfy,
        combinator::{map, value},
        multi::separated_list1,
        sequence::delimited,
        IResult,
    };

    /// Nom parser to parse "[A]" -> 'A'
    fn crate_label(s: &str) -> IResult<&str, char> {
        let mut crate_char = satisfy(|c| c.is_ascii_uppercase());
        delimited(tag("["), crate_char, tag("]"))(s)
    }

    /// Nom parser to parse "[A]     [B] [C]" -> [Some('A'), None, Some('B'), Some('C')]
    fn crate_row(s: &str) -> IResult<&str, Vec<Option<char>>> {
        let mut maybe_crate = map(crate_label, Some);
        let mut empty_space = value(None, tag("   "));
        let mut crate_or_empty = alt((maybe_crate, empty_space));
        separated_list1(tag(" "), crate_or_empty)(s)
    }

    /// Nom parser to parse multiple newline-separated rows of crates into a list
    /// of rows, specified by `crate_row`.
    fn crate_rows(s: &str) -> IResult<&str, Vec<Vec<Option<char>>>> {
        separated_list1(tag("\n"), crate_row)(s)
    }

    /// Parses the first section of the input into a `CrateStacks`, where each
    /// `CrateStack` contained includes the crates from each column of the input.
    pub fn parse(s: &str) -> Result<CrateStacks> {
        let (_, rows) = crate_rows(s).map_err(|_| anyhow!("Cannot parse crate rows!"))?;
        let mut stacks = CrateStacks::default();

        for row in rows.iter().rev() {
            for (idx, maybe_crate) in row.iter().enumerate() {
                if let Some(label) = maybe_crate {
                    stacks[idx + 1].borrow_mut().push(*label);
                }
            }
        }

        Ok(stacks)
    }
}

The key insight here was to realize that the input actually had spaces where the missing crates would be, even on lines where crates were missing from the final stack. Given that, we had a way to identify when we were looking at an empty space in a stack, allowing us to know which crate went in which stack. I also really like anyhow for converting nom::IResult into something more generic.

Instructions - The Things You Follow

Parsing instructions is much more straightforward than the crates. We’re just pulling the numbers from each line.

/// Module wrapping nom parsers for instructions
mod parse_instructions {
    use super::*;
    use anyhow::{anyhow, Result};
    use nom::{
        bytes::complete::take_while,
        character::complete::u8,
        combinator::into,
        sequence::{preceded, tuple},
        IResult,
    };

    /// Nom parser for a string of non-digit characters
    fn not_number(s: &str) -> IResult<&str, &str> {
        take_while(|c: char| c.is_alphabetic() || c.is_whitespace())(s)
    }

    /// Nom parser to convert "move 1" -> 1u8 or " from 2" -> 2u8
    fn labeled_u8(s: &str) -> IResult<&str, u8> {
        preceded(
            take_while(|c: char| c.is_alphabetic() || c.is_whitespace()),
            u8,
        )(s)
    }

    /// Nom parser to convert "move 1 from 2 to 3" -> (1, 2, 3)
    fn instruction(s: &str) -> IResult<&str, Instruction> {
        into(tuple((labeled_u8, labeled_u8, labeled_u8)))(s)
    }

    /// Parse a line of instruction into an `Instruction`
    pub fn parse(s: &str) -> Result<Instruction> {
        let (_, result) =
            instruction(s).map_err(|_| anyhow!("Cannot parse line to an Instruction!"))?;
        Ok(result)
    }
}

Putting it All Together

And finally, we combine all these parts into a single function to read the input file/string into usable structures:

/// Include the input as a constant string slice
const INPUT: &str = include_str!("../../input/05/input.txt");

/// Read the input from the file (string) and parse it.
pub fn read() -> (CrateStacks, Vec<Instruction>) {
    // Split the input on the empty line
    let (mut first_chunk, mut second_chunk) = INPUT.split_once("\n\n").unwrap();

    // Parse the first section into a `CrateStacks`
    let crate_stacks = parse_crates::parse(first_chunk).expect("Failed to parse crate stacks!");

    // Parse the second section into a list of `Instruction`s
    let instructions = second_chunk
        .lines()
        .flat_map(parse_instructions::parse)
        .collect();

    // Return the pair of parsed input sections
    (crate_stacks, instructions)
}

Whew, I’m tired now. Wait, I still have to solve the puzzle. Ah, man!

Part One - Cheerful Christmas Crane

Well, looks like everything is running smoothly for the elves today, and they want to make it run even more smoothly by having us tell them where to stand for unstacking crates of supplies. Not sure if it’s just that there’s nothing for me to be snarky about today, or if I’m just tired from all that input parsing. Turns out, this part can be accomplished by just simulating the take one/place one action of the crane itself.


/// Solve Day 05, Part 1
fn solve(input: &Input) -> String {
    // Split up the input into the stacks of crates and the instructions,
    // then clone the crate stacks struct so we can have a mutable copy.
    let (crate_stacks, instructions) = input;
    let mut crate_stacks = crate_stacks.clone();

    // Execute each instruction on the `CrateStacks`, and return the
    // String resulting from the top crate in each stack
    instructions.iter().for_each(|i| crate_stacks.execute(i));
    crate_stacks.message()
}

/// Implement methods for popping crates from the top of a stack and
/// pushing new crates to the top of a stack.
impl CrateStack {
    /// To push a new crate to the `CrateStack`, just add it to the index past the
    /// last crate (just _happens_ to be `height`) and bump up the height.
    fn push(&mut self, ch: char) {
        self.crates[self.height] = ch;
        self.height += 1;
    }

    /// To pop a crate from the `CrateStack`, bump the height down and return the
    /// character from the top of the stack. Note, this doesn't actually _remove_
    /// the character from the top of the stack, but the next crate pushed to
    /// this stack will overwrite it. So long as we stick to pushing and popping,
    /// we won't have any issues.
    fn pop(&mut self) -> char {
        if self.height == 0 {
            return '.';
        }
        self.height -= 1;
        self.crates[self.height]
    }
}

impl CrateStacks {
    /// Convenience method to pop from one stack out of all the stacks. Which
    /// stack to pop from is given by `crate_idx` as indicated by an `Instruction`.
    fn pop_from(&mut self, crate_idx: u8) -> char {
        if !(1..=9).contains(&crate_idx) {
            return '.';
        }
        self[(crate_idx as usize)].borrow_mut().pop()
    }

    /// Convenience method to push to one stack out of all the stacks. Which
    /// stack to push to is given by `crate_idx` as indicated by an `Instruction`.
    fn push_to(&mut self, crate_idx: u8, ch: char) {
        if !(1..=9).contains(&crate_idx) {
            return;
        }
        self[(crate_idx as usize)].borrow_mut().push(ch);
    }

    /// Fetches the top character (crate) from each stack and builds a String
    /// out of them.
    fn message(&mut self) -> String {
        let mut out = String::new();
        for stack in self.0.iter_mut() {
            let top_crate = stack.borrow_mut().pop();
            out.push(top_crate);
        }
        out
    }
}

/// This is the trait for executing instructions on a `CrateStacks`. Using a trait
/// here so to allow for different functionality between parts one and two.
trait Execute {
    fn execute(&mut self, _: &Instruction);
}

impl Execute for CrateStacks {
    /// Really just boils down to pop crates from one stack and push them onto
    /// another, as many times as the `Instruction` says to.
    fn execute(&mut self, instruction: &Instruction) {
        let Instruction {
            count,
            origin,
            destination,
        } = instruction;
        for _ in 0..*count {
            let top_crate = self.pop_from(*origin);
            self.push_to(*destination, top_crate);
        }
    }
}

There’s probably a bit more code here than strictly necessary, but I wanted to keep all the RefCell.borrow_mut() calls encapsulated in the CrateStacks methods because they seem pretty clunky otherwise. This way, the implementation for Execute and the solve() function remains relatively nice to look at. At the end of the day, though, we’re just popping from one stack and pushing to another, over and over again.

Part Two - It’s Over 9000!

Best thing about part two is the opportunity for that subtitle pun. Turns out, the crane can lift and set as many crates at a time as it wants. Oddly enough, this actually requires less code to satisfy my nit-picking.

/// Solve Day 05, Part 2
pub fn solve(input: &Input) -> String {
    // Split up the input into the stacks of crates and the instructions,
    // then clone the crate stacks struct so we can have a mutable copy.
    let (crate_stacks, instructions) = input;
    let mut crate_stacks = crate_stacks.clone();

    // Execute each instruction on the `CrateStacks`, and return the
    // String resulting from the top crate in each stack
    instructions.iter().for_each(|i| crate_stacks.execute(i));
    crate_stacks.message()
}

impl CrateStack {
    /// Move multiple crates from one stack to another without changing their order.
    /// We do this by setting the new height of the stack to remove crates from, and
    /// taking crates from that stack starting with that new height and moving them
    /// to the other stack in a "bottoms-up" approach.
    fn transfer_many(&mut self, other: &mut Self, n: u8) {
        self.height -= n as usize;
        for offset in 0..(n as usize) {
            let mut crate_to_move = &mut self.crates[self.height + offset];
            let mut crate_destination = &mut other.crates[other.height + offset];
            std::mem::swap(crate_to_move, crate_destination);
        }
        other.height += n as usize;
    }
}

impl CrateStacks {
    /// Convenience function to specify transferring many crates from one stack
    /// to another. Essentially takes all the parameters from an `Instruction`
    /// to do it.
    fn transfer_many_between(&mut self, origin: u8, destination: u8, n: u8) {
        let mut origin_stack = self[origin as usize].borrow_mut();
        let mut destination_stack = self[destination as usize].borrow_mut();
        origin_stack.transfer_many(&mut destination_stack, n);
    }
}

/// This is the trait for executing instructions on a `CrateStacks`. Using a trait
/// here so to allow for different functionality between parts one and two.
trait Execute {
    fn execute(&mut self, _: &Instruction);
}

impl Execute for CrateStacks {
    /// Not much happening in this function other than unpacking the `Instruction`
    /// and passing its parameters to `CrateStacks.transfer_many_between()`.
    fn execute(&mut self, instruction: &Instruction) {
        let Instruction {
            count,
            origin,
            destination,
        } = instruction;
        self.transfer_many_between(*origin, *destination, *count);
    }
}

I’m a big fan of how transfer_many() turned out.

Wrap Up

I am so glad that the actual puzzle solution was as straightforward as it was given the big hill of input parsing today. That said, I can definitely tell that the practice is paying off. My initial set of parsers always seems to start out very bloated and clunky, but I’m consistently being able to pare them down into something that I’m a lot more comfortable with. The fact that I included benchmarks into my Advent of Code setup certainly makes me more cognizant of performance, but I’ll probably need to back off on the performance tweaks in coming days. I spent way too much time on AoC today, but I’d be lying if I said it wasn’t worth it.

comments powered by Disqus