🦀 Solving with Rust: Advent of Code 2022 – Day 04

View the code on GitHub.

See the entire, unedited problem on the Advent of Code website.

Sample input:

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

A more visual representation:

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

.23......  2-3
...45....  4-5

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

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

.....6...  6-6
...456...  4-6

.23456...  2-6
...45678.  4-8

Part 1

Problem: Every line contains the sections—represented as ranges of unsigned integers—covered by a pair of elves. Calculate the number of instances where the range of one of the elves wholly covers the other's.

Let's break this down into two parts. First, we must extract the textual input into usable form. Checking for overlaps can come afterward.

use itertools::Itertools;

pub fn process_part_1(input: &str) -> usize {
    input
        .lines()
        .map(|line| {
            line.split(',')
                .map(|sections| {
                    sections
                        .split('-')
                        .map(|section_id| {
                            section_id
                                .parse::<u32>()
                                .expect("Section IDs should be unsigned integers.")
                        })
                        .collect_tuple()
                        .expect("Covered sections should be described with a '-'.")
                })
                .collect_tuple()
                .expect("Pairs of covered sections should be separated by a ','.")
        })
    // ...
}

Tedious but straightforward. Notice the use of collect_tuple(). That's a convenience function from the trait itertools::Itertools that lets us avoid calling .next().unwrap() on the iterator twice. Since Rust doesn't allow collecting into arrays, this is the best we can do (that I know of).

Now, it's time to move on to the actual problem. There are several ways to solve it, but let's make use of Rust's built-in ranges.

All we need to find out is how many times overlaps happen. Or, to simplify, we must count the number of elements that satisfy some condition. That's a big, fat hint right there, and it tells us, "Use filter() and count()."

pub fn process_part_1(input: &str) -> usize {
    input
        .lines()
        .map(|line| {
            line.split(',')
                .map(|sections| {
                    sections
                        .split('-')
                        .map(|section_id| {
                            section_id
                                .parse::<u32>()
                                .expect("Section IDs should be unsigned integers.")
                        })
                        .collect_tuple()
                        .expect("Covered sections should be described with a '-'.")
                })
                .collect_tuple()
                .expect("Pairs of covered sections should be separated by a ','.")
        })
+       .filter(|((min1, max1), (min2, max2))| {
+           (min1..=max1).contains(&min2) && (min1..=max1).contains(&max2)
+               || (min2..=max2).contains(&min1) && (min2..=max2).contains(&max1)
+       })
+       .count()
}

The use of collect_tuple() lets us pattern-match on the section IDs in the closure signature. All that's left is to check whether each section range contains the start and the end of the other.

• Make sure that the ranges are inclusive—in other words, don't forget the = after the ...

Part 2

Problem: The same as before, except that partial overlaps should be included, too.

The only change we need to make is replace the and operators (&&) with the or ones (||). Everything else stays identical.

.filter(|((min1, max1), (min2, max2))| {
    (min1..=max1).contains(&min2)
        || (min1..=max1).contains(&max2)
        || (min2..=max2).contains(&min1)
        || (min2..=max2).contains(&max1)
})

Simple, right?

---

Got any suggestions for improvements? Feel free to share them in the comments.

Comments

[verified_tinker]

After a spree of LeetCode problems where I shared (on its website) what solutions I was proud of, I felt the same urge when I finished today's Advent of Code, only to realize it doesn't have the feature to do that. That led to the thought, Why not post it on Dev?

If anyone would like the solutions for the previous days, let me know, and I'll put 'em up, too. 😊