Day 4 (Advent of Code 2022)
👋 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!
Thanks to my sponsors:
If you liked what you saw, please support my work!
Here's another article just for you:
In order to increase fluency in a programming language, one has to read a lot of it.
But how can you read a lot of it if you don't know what it means?
In this article, instead of focusing on one or two concepts, I'll try to go through as many Rust snippets as I can, and explain what the keywords and symbols they contain mean.
Ready? Go!