Day 4 (Advent of Code 2022)

Dec 4, 2022 4 minute read rust · advent-of-code · ranges · extension-traits

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

Part 1
Extension traits
Part 2

Part 1

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

Discuss this article on /r/fasterthanlime

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

Donate on GitHub Donate on Patreon

Looking for the homepage?

Another article: I am a Java, C#, C or C++ developer, time to do some Rust

Day 4 (Advent of Code 2022)

Contents

Part 1

Extension traits

Part 2