This is part of the series Advent of Code 2022.
Day 4 - Advent of Code 2022
7 minute read  (1357 words)
rust advent-of-code

Welcome to day 4 of the Advent Of Code challenge.

Today is camp cleanup day. Elves need to clean up the area before unloading the ships. The camp on the beach is organized into sections, each section has a unique ID number, each elf is assigned a range of section IDs.

Part 1

When the elves compare their section assignments with each other, they realize the assignments overlap. Given the following assignment pairs.

2-4,6-8
2-3,4-5
5-7,7-9
2-8,3-7
6-6,4-6
2-6,4-8

Each line consists of an assignment for a pair of elves, each elf is assigned a range of sections. Reading the first line, the first elf has sections 2-4 (2, 3, 4), the second has 6-8 (6, 7, 8). The example uses single digit section IDs for illustration, the given input file contains bigger section IDs.

Given the first pair 2-4,6-8 the section ranges can be visualized as follows:

.234.....  2-4
.....678.  6-8

The sections do not overlap. Other assignments do overlap partially, while still others do overlap completey, for example pair 2-8,3-7

.2345678.  2-8
..34567..  3-7

which means the elf with the smaller assignment (3-7) is completely contained by the first range already.

The task is to determine how many assignments exist where one section range fully contains the other? The given sample input contains two assignments that fully overlap one of the ranges, 2-8,3-7 & 6-6,4-6.

Let's start with the basic logic in src/main.rs.

fn part1(sections: &[&str]) -> u32 {
    todo!()
}

fn parse(input: &str) -> Vec<&str> {
    todo!()
}

fn main() {
    let input = parse(include_str!("input.txt"));
}

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

    const INPUT: &str = r#"
        2-4,6-8
        2-3,4-5
        5-7,7-9
        2-8,3-7
        6-6,4-6
        2-6,4-8
    "#;

    #[test]
    fn check_part1() {
        assert_eq!(2, part1(&parse(INPUT)));
    }
}

After a bit of thought we want to determine that one range contains the other range. This is when the bounds of one range are completely covered by the other bounds. Using the earlier example pair 2-8,3-7:

.2345678.  2-8
..34567..  3-7

The lower bound (2) of the first range is smaller than the lower bound of the second (3), while the upper bound (8) is larger than the second upper bound (7). One idea is to simply check the range. There is a RangeInclusive type in Rust, but let's define our own custom type for now.

#[derive(Debug)]
struct Range {
    min: u32,
    max: u32,
}

impl Range {
    /// Constructor
    pub fn new(min: u32, max: u32) -> Self {
        Self {min, max}
    }

    /// Returns `true` if this Range contains the other completely.
    pub fn contains(&self, rhs: &Self) -> bool {
        self.min <= rhs.min && self.max >= rhs.max
    }
}

#[cfg(test)]
mod tests {
    // ...

    #[test]
    fn check_range_bounds() {
        let l = Range::new(2, 8);
        let r = Range::new(3, 7);
        assert!(l.contains(&r));
        assert!(!r.contains(&l));
    }
}

The new Range struct contains both bounds min & max as u32. The constructor function new helps to build a new Range. The method contains checks if a given Range is fully covered by the other. The test check_range_bounds in the test module checks the coverage for the assignment 2-8,3-7.

The next step is to parse the input text into a suitable list. For now the parse function returns a Vec<(Range, Range)> consisting of tuples with Range.

fn parse(input: &str) -> Vec<(Range, Range)> {
    input
        .lines()
        .map(str::trim)
        .filter(|s| !s.is_empty())
        .filter_map(|s| s.split_once(","))
        .map(|(l, r)| (l.into(), r.into()))
        .collect::<Vec<_>>()
}

There is some code missing. A good practice is to support to convert a &str into the struct it represents. In this case we ignore error handling again (which is usually not recommended). To make the call of l.into() work, an implementation of the From trait is required. A better approach would to implement TryFrom to recover from any wrong input string.

A naive implementation without error handling could look like:

impl From<&str> for Range {
    fn from(range: &str) -> Self {
        let (min, max) = range.split_once("-").expect("Failed to parse range.");
        let min = min.parse::<u32>().expect("Not a number");
        let max = max.parse::<u32>().expect("Not a number");
        Range::new(min, max)
    }
}

That parses the text 2-7 into a Range. It assumes the format is always <min>-<max> where the first number is always lower than the second. Thankfully the input text conforms to these expectations.

Having a tuple of two ranges in (Range, Range) feels a bit inconvenient. It's often a good idea to use types that represent a concept, in our case that is the assignment. Therefore a new type Assignment is added that holds both sections / ranges.

struct Assignment {
    /// First or left sections
    pub l: Range,
    /// Second or right sections
    pub r: Range,
}

impl Assignment {
    pub fn new(l: Range, r: Range) -> Self {
        Self { l, r }
    }
}

It's a simple struct with two fields and a constructor method. We should now have most of the logic to implement part 1 of the challenge. We want to iterate overall assignments and see which assignments overlap, meaning where one section completely covers the other one of the same assignment. We then filter all assignments for which this is true and count their occurrences. The next code also refactors the list of tuples (Vec<(Range, Range)>) into a list of assignments (Vec<Assignment>).

fn part1(sections: &[Assignment]) -> usize {
    sections
        .iter()
        .filter(|assignment| {
            assignment.l.contains(&assignment.r) || assignment.r.contains(&assignment.l)
        })
        .count()
}

// Updated return type of function
fn parse(input: &str) -> Vec<Assignment> {
    input
        .lines()
        .map(str::trim)
        .filter(|s| !s.is_empty())
        .filter_map(|s| s.split_once(","))
        .map(|(l, r)| (l.into(), r.into()))
        .map(|(l, r)| Assignment::new(l, r))
        .collect::<Vec<_>>()
}

fn main() {
    let input = parse(include_str!("input.txt"));
    println!("Overlaps: {}", part1(&input));
}

The part1 function does not really use the Assignment type yet, it mainly forwards to its inner fields. Therfore the map closure to determine the overlap feels as if it exposes some detail. Let's move this check into the Assignment type itself in a new function called overlaps that returns a bool.

impl Assignment {
    fn overlaps(&self) -> bool {
        self.l.contains(&self.r) || self.r.contains(&self.l)
    }
}

Then the function part1 can be refactored to:

fn part1(sections: &[Assignment]) -> usize {
    sections
        .iter()
        .filter(|assignment| assignment.overlaps()) // <-- updated
        .count()
}

Running the program with cargo run should provide the first answer.

Part 2

The second part of the challenge is to also count all partially overlapping assignments. To find a partial overlap we have to find if both ranges intersect with each other. Using one of the assignments from the sample data, e.g. 5-7,7-9 the intersection looks as follows.

....567..  5-7
......789  7-9
      ^

They intersect on section 7. Coming up with a method to find the intersection between two ranges is not that difficult, fortunately this is fairly well covered already, for example on this Computational Science board. Thankfully the boolean expression is simplified using boolean algebra (applying De Morgan's laws to transform boolean expressions).

Let's add intersection methods to Range and Assignment.

impl Range {
    pub fn intersect(&self, rhs: &Self) -> bool {
        self.max >= rhs.min && rhs.max >= self.min
    }
}

impl Assignment {
    fn intersects(&self) -> bool {
        self.l.intersect(&self.r)
    }
}

The Range::intersect determines if both ranges intersect with each other. The check in Assignment::intersects is similar to overlaps and checks if there is any intersection. Its calling Range::intersect only once, because the other way around self.r.intersect(&self.l) provides the exact same result.

With that in place part2 will look then very similar to part1, in addition to the overlap check it also tests if both ranges intersect.

fn part2(sections: &[Assignment]) -> usize {
    sections
        .iter()
        .filter(|&assignment| assignment.intersects() || assignment.overlaps())
        .count()
}

fn main() {
    let input = parse(include_str!("input.txt"));
    println!("Overlaps: {}", part1(&input));
    println!("Intersections: {}", part2(&input));
}

The function returns the number of intersections, including all completely overlapping ones. With this in place cargo run should output the correct total number now.