Thanks to my sponsors: Max Bruckner, Daniel Wagner-Hall, Marcin Kołodziej, Adam Lassek, David White, Marco Carmosino, qrpth, Tom Forbes, Joshua Roesslein, Tiziano Santoro, Alex Krantz, genny, Noel, Michael Mrozek, James Brown, Jacob Cheriathundam, Matt Heise, Makoto Nakashima, Lev Khoroshansky, Moritz Lammerich and 230 more

Dec 04, 2022

4 min #rust · #advent-of-code · #ranges · #extension-traits

Day 4 (Advent of Code 2022)

From the series Advent of Code 2022

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

👋 This page was last updated ~2 years ago. Just so you know.

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:

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);
    }
}

$ 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:

fn main() {
    let range = 2..=4;
    dbg!(range.contains(&2));
    dbg!(range.contains(&3));
    dbg!(range.contains(&4));
    dbg!(range.contains(&5));
}

$ 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:

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
}

$ 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:

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:

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:

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:

$ 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?

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:

$ 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:

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:

$ cargo add itertools
(cut)

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);
}

$ 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:

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:

$ 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!

You're reading the Advent of Code 2022 series.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

Comment on /r/fasterthanlime

(JavaScript is required to see this. Or maybe my stuff broke)

Here's another article just for you:

Declarative memory management

Sep 19, 2019

34 min #rust · #memory

It feels like an eternity since I've started using Rust, and yet I remember vividly what it felt like to bang my head against the borrow checker for the first few times.

I'm definitely not alone in that, and there's been quite a few articles on the subject! But I want to take some time to present the borrow checker from the perspective of its , rather than as an opponent to fend with.