Advent of Code 2022 - Day 06

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 06 - Tuning Trouble

Find the problem description HERE.

The Input - Noise to Signal

I won’t lie to you. My first pass at parsing this input was to trim the newline from the end and pass it along. But, then I decided I wanted to speed up my solver function(s) and implemented a bit of light parsing on this looooong string of characters. Since I realized that bitwise operations on integers can provide a really fast alternative to set operations (see Day 3), I decided to pre-convert each character in the input to a Signal struct, which just wraps a u32 containing a single set bit representative of that character.

use anyhow::{bail, Error};

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

/// Read in the input by converting each character to a `Signal` and returning
/// the list.
pub fn read() -> Vec<Signal> {
    INPUT.trim().chars().flat_map(Signal::try_from).collect()
}

/// Represents a single signal received on our device. Each character from the
/// input string can be represented as a `u32` with a single set bit, offset
/// from the left in alphabetic order. For example:
///  
/// 'a' -> Signal(00000000000000000000000000000001)
/// 'b' -> Signal(00000000000000000000000000000010)
/// 'x' -> Signal(00000000100000000000000000000000)
/// 'z' -> Signal(00000010000000000000000000000000)
#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
struct Signal(u32);

impl TryFrom<char> for Signal {
    type Error = Error;

    fn try_from(value: char) -> Result<Self, Self::Error> {
        /// Anything besides a lowercase letter cannot make a Signal
        if !value.is_ascii_lowercase() {
            bail!("Cannot convert {value} to a `Signal`!");
        }

        /// Set a single bit and shift it left by the letter offset, return
        /// as a Signal
        let shift = (value as u32) - 97;
        Ok(Signal(1 << shift))
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn name() {
        let input = read();
        assert_eq!(input.len(), 4095);

        let first_signal = *input.first().unwrap();
        let first_expected = Signal::try_from('d').unwrap();
        assert_eq!(first_signal, first_expected);

        let last_signal = *input.last().unwrap();
        let last_expected = Signal::try_from('j').unwrap();
        assert_eq!(last_signal, last_expected);
    }
}

I’ll point out that I’ve been using flat_map() quite a bit this year. The nice thing about flat_map() is that if your map function returns an Option or aResult, then the None and Err variants are automatically dropped. The downside is that the None and Err variants are automatically dropped, so you may end up skipping some values and not realize it. This would probably be bad practice in real life, but it’s handy for Advent of Code puzzles. To account for this possible dropping, I always include a test for the input parsing (included above today) that ensures the input is the right length and that we get the expected results for the first and last items. This approach hasn’t failed me yet, so I’m going to stick with it.

Part One - Signal Superhero

Is it just me, or do we detect a bit of snark coming from the elves’ AI? By the way, I’ve decided that the AI is operating as a bit of a hive mind that’s split it’s focus over all the elves, which is why sometimes one of them does something monumentally incompetent that we have to fix. I feel like we’re getting close to the truth, since the AI is obviously trying to distract us with these _obviously_irresistible signal-based activities. Speaking of irresistible, apparently I can’t resist re-implementing basic functionality for wrappers around primitive Rust types! For this part, we need to find the last letter in the first sequence of four unique signals and return its index (plus one).

use std::ops::{BitAnd, BitOrAssign};

/// Solve Day 6, Part 1
fn solve(input: &Input) -> u32 {
    // Instantiate a detector for sequences of length 4
    let mut detector: SequenceDetector<4> = SequenceDetector::new();

    // Pass each `Signal` in the input to the detector. Return early
    // with the index (plus one) if a unique sequence is detected.
    for (idx, signal) in input.iter().enumerate() {
        if detector.detect(*signal) { return (idx as u32 + 1); }
    }
    panic!("No start-of-packet marker detected!")
}

/// Implement bitwise _and_ for `Signal`s
impl BitAnd for Signal {
    type Output = Signal;

    fn bitand(self, rhs: Self) -> Self::Output {
        Signal(self.0 & rhs.0)
    }
}

/// Implement bitwise _or-assign_ for `Signal`s
impl BitOrAssign for Signal {
    fn bitor_assign(&mut self, rhs: Self) {
        self.0 |= rhs.0;
    }
}

/// Represents a 'detector' for unique sequences of `Signal`s of a constant length. 
/// Holds a buffer of the signals encountered so far and inserts new signals into
/// that buffer by wrapping around the length of the buffer.
#[derive(Debug)]
struct SequenceDetector<const N: usize> {
    buffer: [Signal; N],
    mark: usize,
}

impl<const N: usize> SequenceDetector<N> {
    /// Create a new `SequenceDetector` with an empty buffer and a marker set to the
    /// first index of the buffer.
    fn new() -> Self {
        let buffer = [Signal::default(); N];
        let mark = 0;
        Self { buffer, mark }
    }

    /// Given a `Signal`, indicates whether the most recent `N` signals detected
    /// comprises a unique sequence.
    fn detect(&mut self, signal: Signal) -> bool {
        // Add the signal to the buffer and bump the marker over by one to 
        // receive the next signal.
        self.buffer[self.mark] = signal;
        self.mark = (self.mark + 1) % N;

        // If the marker points to an empty signal in the buffer, this means
        // the buffer isn't full yet and we definitely haven't found `N` unique
        // signal inputs.
        if self.buffer[self.mark] == Signal(0) { return false; }

        // Check the buffer for unique signals. If any duplicate `Signal`s are
        // detected, return false early. If all `Signal`s _are_ unique, return true.
        let mut bits = Signal(0);
        for bit in self.buffer.iter() {
            if *bit & bits > Signal(0) { return false; }
            bits |= *bit;
        }
        true
    }
}

Yeah, that buffer inside the SequenceDetector made me feel clever… Granted, I could probably have iterated over windows of the input signals and achieved the same thing without copying around signals from the input, but I really_like_ my wrapping signal buffer. Also, did you notice the use of const generics_in that SequenceDetector definition. We’ve only had those since Rust 1.51, and I don’t get opportunities to use them often. I like what they can do! Speaking of what _const generics can do…

Part Two - How Good are Const Generics, Though?

/// Solve Day 6, Part 2
pub fn solve(input: &Input) -> u32 {
    // Instantiate a detector for sequences of length 14
    let mut detector: SequenceDetector<14> = SequenceDetector::new();

    // Pass each `Signal` in the input to the detector. Return early
    // with the index (plus one) if a unique sequence is detected.
    for (idx, signal) in input.iter().enumerate() {
        if detector.detect(*signal) { return (idx as u32 + 1).into(); }
    }
    panic!("No start-of-message marker detected!")
}

Can you spot the difference from part one? That’s right! We’re just changing the generic count for SequenceDetector<N> to check for unique signals of length fourteen. The generic here means that SequenceDetector<N> can be instantiated to check for signals of any length (as long as we’re not decided on the length to check for dynamically). That’s nice.

Wrap Up

Today was fun! I’m happy with the performance of today’s solution and I really do get a kick out of re-implementing traits for newtypes. Plus, I had an excuse to use const generics to make my solution function general enough to handle both parts with very minimal modification. No real parsing challenges today, but that’s honestly a bit of a relief after yesterday. This was a pretty quick one, but it’s good to get a day to catch up every now and again. See you tomorrow!