Advent of Code 2022 - Day 04

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 04 - Camp Cleanup

Find the problem description HERE.

The Input - Just the Two of Us

Hooray! I can justify parsing today’s input with nom! Now, you may look at the input file and think to yourself: “That seems like overkill. There are obvious characters here to split the input on!”. And you’d be right! And also wrong! So there. Really, though, it’s a good excuse to practice, and I think I’m starting to get a handle on how I want to use nom moving forward.

/// Represents a range of beach assignments for a particular elf
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub struct AssignmentRange {
    pub start: u8,
    pub stop: u8,
}

/// Convert a pair of integers to an `AssignmentRange`
impl From<(u8, u8)> for AssignmentRange {
    fn from(value: (u8, u8)) -> Self {
        let (start, stop) = value;
        AssignmentRange { start, stop }
    }
}

/// Represents a pair of elf beach cleaning assignment ranges
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd)]
pub struct AssignmentRangePair(pub AssignmentRange, pub AssignmentRange);

/// Convert a pair of assignment ranges into an `AssignmentRangePair`
impl From<(AssignmentRange, AssignmentRange)> for AssignmentRangePair {
    fn from(value: (AssignmentRange, AssignmentRange)) -> Self {
        let (first, second) = value;
        AssignmentRangePair(first, second)
    }
}

/// I find that I like having the `nom` parser functions bundled under a module
/// like this. It helps to namespace the parser combinators by usage and keeps
/// me from polluting the parent module with a bunch of otherwise ambiguously
/// named functions. Another option I'm playing with is bundling them as impl
/// functions under an empty struct. Not sure which I like better yet, but this has
/// the advantage of allowing me to include the `use::nom::*` imports close to where
/// the parser combinators are defined. I'll need to try it out in a few more
/// situations to get a better handle on the pros and cons.
mod arp_parser {
    use super::{AssignmentRange, AssignmentRangePair};
    use nom::{
        bytes::complete::tag, 
        character::complete::u8, 
        combinator::into, 
        error::Error as NomError,
        sequence::separated_pair, 
        Finish, IResult,
    };

    /// Nom parser for "12-22" -> (12u8, 22u8)
    fn number_pair(s: &str) -> IResult<&str, (u8, u8)> {
        separated_pair(u8, tag("-"), u8)(s)
    }

    /// Nom parser for "12-22" -> AssignmentRange { start: 12, stop: 22 }
    fn range(s: &str) -> IResult<&str, AssignmentRange> {
        into(number_pair)(s)
    }

    /// Nom parser for "12-22,18-24" -> AssignmentRangePair(
    /// AssignmentRange { start: 12, stop: 22 },
    /// AssignmentRange { start: 18, stop: 24 },
    /// )
    pub fn parse(s: &str) -> Result<AssignmentRangePair, NomError<&str>> {
        let pair_parser = separated_pair(range, tag(","), range);
        let parse_result = into(pair_parser)(s);
        let (_, ranges) = parse_result.finish()?;
        Ok(ranges)
    }
}

// Keep the input file as a compile time constant string slice
const INPUT: &str = include_str!("../../input/04/input.txt");

/// Read the input by parsing each line into an `AssignmentRangePair` and discarding
/// any lines that return an Error. We'll check in the tests to make sure every line
/// is parsed.
pub fn read() -> Vec<AssignmentRangePair> {
    INPUT
        .lines()
        .flat_map(arp_parser::parse)
        .collect()
}

This seems a lot cleaner than my previous strategy of “just leave a bunch of parsing functions lying around in my input.rs module”. Granted, now they’re in input::arp_parser, so it’s not like it’s a big change, but I like it. I don’t often use nested modules like this, so it’s something to experiment with, at least.

Part One - A Glitch in the Matrix

OK, is it just me or is the AI running the elves becoming less reliable? (See my posts for previous days for the origin of this particular conspiracy theory). Today, it seems that Deep Tinsel (what I’ve just now decided to call the elf-AI) has produced a set of beach cleanup assignments with certain…redundancies. Or, maybe there were just some elves who thought they’d get away without doing chores and no one would notice? Either way, we bring our mighty problem-solving skills to the rescue!

/// Solve Day 4, Part 1
pub fn solve(input: &Input) -> u32 {
    // For each assignment pair in the input, check to see if one assignment
    // complete contains another. Count only the pairs where this check returns
    // true.
    input
        .iter()
        .map(|pair| pair.full_containment())
        .filter(|x| *x)
        .count() as u32
}

/// Trait for determine whether one `AssignmentRange` completely contains another
trait RangeContains {
    fn contains(&self, other: &Self) -> bool;
}

impl RangeContains for AssignmentRange {
    fn contains(&self, other: &Self) -> bool {
        // Return true if one range is completely inside another
        self.start <= other.start && self.stop >= other.stop
    }
}

impl AssignmentRangePair {
    /// Return true if either range in the pair completely contains the other one.
    fn full_containment(&self) -> bool {
        let AssignmentRangePair(first, second) = self;
        first.contains(second) || second.contains(first)
    }
}

That’s it, huh? Turns out checking for completely overlapping ranges isn’t particularly difficult when you’ve already got them paired up like this. Glad we didn’t have to check all the possible pairs.

Part Two - Picking Nits

Yeah, sure, we probably should have just checked for partial overlaps the first time through, but we didn’t think of it. Good thing that only requires minor modifications to our code from part one.

/// Solve Day 4, Part 2
pub fn solve(input: &Input) -> u32 {
    input
        .iter()
        .map(|pair| pair.ranges_overlap())
        .filter(|x| *x)
        .count() as u32
}

/// Trait for determine whether one `AssignmentRange` overlaps another
trait RangeOverlap {
    fn overlaps(&self, other: &Self) -> bool;
}

impl RangeOverlap for AssignmentRange {
    fn overlaps(&self, other: &Self) -> bool {
        // Return true if one range overlaps another
        self.start <= other.stop && self.stop >= other.start
    }
}

impl AssignmentRangePair {
    /// Return true if either range in the pair overlaps another
    fn ranges_overlap(&self) -> bool {
        let AssignmentRangePair(first, second) = self;
        first.overlaps(second) || second.overlaps(first)
    }
}

See, no big deal. The biggest change is just the comparison of the two ranges. Everything else is just re-naming for the sake of clarity.

Wrap Up

I honestly don’t have much to say about today’s puzzle. It was a good one for practicing nom since the parsing was fairly straightforward, though, so I got to experiment with my code organization a bit. I had originally thought about using a struct containing a parsing function and building up that function with a “builder pattern” kind of approach. I may still try that another day, but it seems like it might be way over-complicating matters. Either way, that’s another fun coding puzzle in the books, and I’m looking forward to tomorrow!