Day 4 (Advent of Code 2022)

This article is part of the Advent of Code 2022 series.

Part 1

Let's tackle the day 4 challenge!

In this one, we get an input like this:

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 has two ranges: the first line has ranges containing 2, 3, 4, and 6, 7, 8. We must count how many pairs have ranges where one fully contains the other.

In Rust, we can express this with "inclusive ranges" (std::ops::RangeInclusive), and those implement Iterator, so we can do:

Rust code
fn main() {
    // note: `2..4` would exclude the `4` - it would be of type `Range`,
    // whereas this syntax makes a `RangeInclusive`:
    for i in 2..=4 {
        dbg!(i);
    }
}
Shell session
$ cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.00s
     Running `target/debug/day4`
[src/main.rs:3] i = 2
[src/main.rs:3] i = 3
[src/main.rs:3] i = 4

They also implement contains, to check if a single item is contained within the range:

Rust code
fn main() {
    let range = 2..=4;
    dbg!(range.contains(&2));
    dbg!(range.contains(&3));
    dbg!(range.contains(&4));
    dbg!(range.contains(&5));
}
Shell session
$ cargo run
   Compiling day4 v0.1.0 (/home/amos/bearcove/aoc2022/day4)
    Finished dev [unoptimized + debuginfo] target(s) in 0.33s
     Running `target/debug/day4`
[src/main.rs:3] range.contains(&2) = true
[src/main.rs:4] range.contains(&3) = true
[src/main.rs:5] range.contains(&4) = true
[src/main.rs:6] range.contains(&5) = false

That means, if we have two ranges, we can check if one contains the other by simply checking every item:

Rust code
use std::ops::RangeInclusive;

fn main() {
    dbg!(contains_range(2..=4, 6..=8));
    dbg!(contains_range(6..=8, 2..=4));
    dbg!(contains_range(4..=6, 6..=6));
}

fn contains_range(bigger: RangeInclusive<i32>, smaller: RangeInclusive<i32>) -> bool {
    for i in smaller {
        if !bigger.contains(&i) {
            return false;
        }
    }
    true
}
Shell session
$ cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.00s
     Running `target/debug/day4`
[src/main.rs:4] contains_range(2..=4, 6..=8) = false
[src/main.rs:5] contains_range(6..=8, 2..=4) = false
[src/main.rs:6] contains_range(4..=6, 6..=6) = true

But that's kinda wasteful!

Instead, we can simply check if the start and the end of the range are included:

Rust code
use std::ops::RangeInclusive;

fn main() {
    dbg!(contains_range(2..=4, 6..=8));
    dbg!(contains_range(6..=8, 2..=4));
    dbg!(contains_range(4..=6, 6..=6));
}

fn contains_range(bigger: RangeInclusive<i32>, smaller: RangeInclusive<i32>) -> bool {
    bigger.contains(smaller.start()) && bigger.contains(smaller.end())
}

Extension traits

In fact, we can implement it as a method on RangeInclusive itself! And we can make that impl generic:

Rust code
use std::ops::RangeInclusive;

trait InclusiveRangeExt {
    fn contains_range(&self, other: &Self) -> bool;
}

impl<T> InclusiveRangeExt for RangeInclusive<T>
where
    T: PartialOrd,
{
    fn contains_range(&self, other: &Self) -> bool {
        self.contains(other.start()) && self.contains(other.end())
    }
}

fn main() {
    dbg!((2..=4).contains_range(&(6..=8)));
    dbg!((6..=8).contains_range(&(2..=4)));
    dbg!((4..=6).contains_range(&(6..=6)));
}

This is a neat technique, because it lets us add methods to any type, even types we haven't declared ourselves (say, types that come from the standard library, or another crate).

But if anyone can add methods to types, how does the compiler know which ones to use?

Ah, we can only use it if it's in scope! If it was in a separate module, for example:

Rust code
mod ext {
    use std::ops::RangeInclusive;

    trait InclusiveRangeExt {
        fn contains_range(&self, other: &Self) -> bool;
    }

    impl<T> InclusiveRangeExt for RangeInclusive<T>
    where
        T: PartialOrd,
    {
        fn contains_range(&self, other: &Self) -> bool {
            self.contains(other.start()) && self.contains(other.end())
        }
    }
}

fn main() {
    dbg!((2..=4).contains_range(&(6..=8)));
    dbg!((6..=8).contains_range(&(2..=4)));
    dbg!((4..=6).contains_range(&(6..=6)));
}

Then it wouldn't compile:

Shell session
$ cargo run
   Compiling day4 v0.1.0 (/home/amos/bearcove/aoc2022/day4)
error[E0599]: no method named `contains_range` found for struct `RangeInclusive` in the current scope
  --> src/main.rs:19:18
   |
19 |     dbg!((2..=4).contains_range(&(6..=8)));
   |                  ^^^^^^^^^^^^^^ help: there is a method with a similar name: `contains`
   |
   = help: items from traits can only be used if the trait is implemented and in scope
note: `InclusiveRangeExt` defines an item `contains_range`, perhaps you need to implement it
  --> src/main.rs:4:5
   |
4  |     trait InclusiveRangeExt {
   |     ^^^^^^^^^^^^^^^^^^^^^^^

(cut: the same error, twice more)

The compiler tells us exactly what we need to do.

Still, what if there's two extension traits that define a method with the same name? And they're both in scope?

Like this you mean?

Rust code
use std::ops::RangeInclusive;

trait InclusiveRangeExt {
    fn contains_range(&self, other: &Self) -> bool;
}

impl<T> InclusiveRangeExt for RangeInclusive<T>
where
    T: PartialOrd,
{
    fn contains_range(&self, other: &Self) -> bool {
        self.contains(other.start()) && self.contains(other.end())
    }
}

trait EvilInclusiveRangeExt {
    fn contains_range(&self, other: &Self) -> bool;
}

impl<T> EvilInclusiveRangeExt for RangeInclusive<T>
where
    T: PartialOrd,
{
    fn contains_range(&self, other: &Self) -> bool {
        panic!("ahAH! you thought you were getting a real implementation, but it was me, DIO!");
    }
}

fn main() {
    dbg!((2..=4).contains_range(&(6..=8)));
    dbg!((6..=8).contains_range(&(2..=4)));
    dbg!((4..=6).contains_range(&(6..=6)));
}

Then it complains, too:

Shell session
$ cargo run
Compiling day4 v0.1.0 (/home/amos/bearcove/aoc2022/day4)
error[E0034]: multiple applicable items in scope
  --> src/main.rs:30:18
   |
30 |     dbg!((2..=4).contains_range(&(6..=8)));
   |                  ^^^^^^^^^^^^^^ multiple `contains_range` found
   |
note: candidate #1 is defined in an impl of the trait `InclusiveRangeExt` for the type `RangeInclusive<T>`
  --> src/main.rs:11:5
   |
11 |     fn contains_range(&self, other: &Self) -> bool {
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: candidate #2 is defined in an impl of the trait `EvilInclusiveRangeExt` for the type `RangeInclusive<T>`
  --> src/main.rs:24:5
   |
24 |     fn contains_range(&self, other: &Self) -> bool {
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
help: disambiguate the associated function for candidate #1
   |
30 |     dbg!(InclusiveRangeExt::contains_range(&(2..=4), &(6..=8)));
   |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
help: disambiguate the associated function for candidate #2
   |
30 |     dbg!(EvilInclusiveRangeExt::contains_range(&(2..=4), &(6..=8)));
   |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

(cut)

And once again, the compiler tells how to fix it:

Rust code
fn main() {
    dbg!(InclusiveRangeExt::contains_range(&(2..=4), &(6..=8)));
    dbg!(InclusiveRangeExt::contains_range(&(6..=8), &(2..=4)));
    dbg!(InclusiveRangeExt::contains_range(&(4..=6), &(6..=6)));
}

This works fine.

Anyway, we can now solve part 1:

Shell session
$ cargo add itertools
(cut)
Rust code
use std::ops::RangeInclusive;

use itertools::Itertools;

trait InclusiveRangeExt {
    fn contains_range(&self, other: &Self) -> bool;

    // 👋 new! we can have trait methods with default implementations
    fn contains_or_is_contained(&self, other: &Self) -> bool {
        self.contains_range(other) || other.contains_range(self)
    }
}

impl<T> InclusiveRangeExt for RangeInclusive<T>
where
    T: PartialOrd,
{
    fn contains_range(&self, other: &Self) -> bool {
        self.contains(other.start()) && self.contains(other.end())
    }
}

fn main() {
    let redundant = include_str!("sample-input.txt")
        .lines()
        .map(|l| {
            l.split(',')
                .map(|range| {
                    range
                        .split('-')
                        .map(|n| n.parse().expect("range start/end should be u32"))
                        .collect_tuple::<(u32, u32)>()
                        .map(|(start, end)| start..=end)
                        .expect("each range should have a start and end")
                })
                .collect_tuple::<(_, _)>()
                .expect("each line must have a pair of ranges")
        })
        .filter(|(a, b)| a.contains_or_is_contained(b))
        .count();
    dbg!(redundant);
}
Shell session
$ cargo run
   Compiling day4 v0.1.0 (/home/amos/bearcove/aoc2022/day4)
    Finished dev [unoptimized + debuginfo] target(s) in 0.39s
     Running `target/debug/day4`
[src/main.rs:41] redundant = 2

Part 2

I expected part 2 to be harder, but... nope! It now just wants to know about the number of pairs that overlaps.

We can just add more methods to our extension trait:

Rust code
trait InclusiveRangeExt {
    fn contains_range(&self, other: &Self) -> bool;

    fn contains_or_is_contained(&self, other: &Self) -> bool {
        self.contains_range(other) || other.contains_range(self)
    }

    // 👋 new!
    fn overlaps(&self, other: &Self) -> bool;

    fn overlaps_or_is_overlapped(&self, other: &Self) -> bool {
        self.overlaps(other) || other.overlaps(self)
    }
}

impl<T> InclusiveRangeExt for RangeInclusive<T>
where
    T: PartialOrd,
{
    fn contains_range(&self, other: &Self) -> bool {
        self.contains(other.start()) && self.contains(other.end())
    }

    // 👇 implementation is here
    fn overlaps(&self, other: &Self) -> bool {
        self.contains(other.start()) || self.contains(other.end())
    }
}

Now we can change the call from a.contains_or_is_contained(b) to a.overlaps_or_is_overlapped(b), and try it with the sample input first:

Shell session
$ cargo run
   Compiling day4 v0.1.0 (/home/amos/bearcove/aoc2022/day4)
    Finished dev [unoptimized + debuginfo] target(s) in 0.35s
     Running `target/debug/day4`
[src/main.rs:52] overlapping = 4

And... it works with the real input too. That's it for today!

This article is part 4 of the Advent of Code 2022 series.

Read the next part

If you liked what you saw, please support my work!

Github logo Donate on GitHub Patreon logo Donate on Patreon

Latest video View all

video cover image
C++ vs Rust: which is faster?

I ported some Advent of Code solutions from C/C++ to Rust, and used the opportunity to compare performance. When I couldn't explain why they performed differently, I had no choice but to disassemble both and look at what the codegen was like!

Watch now
Looking for the homepage?