aoc/year2025/
day05.rs

1//! # Cafeteria
2//!
3//! We speed things up by first merging ranges. This is possible in `O(n log n)` instead of `O(n²)`
4//! complexity by first sorting the ranges in ascending order of their start.
5//!
6//! Interestingly, part one is harder than part two. We could check every ID against every range,
7//! however this is slow. It's much faster instead to first sort IDs in ascending order,
8//! then for each range use a [binary search](https://en.wikipedia.org/wiki/Binary_search) to count
9//! the number of IDs that it contains. Rust even provides a handy built-in
10//! [`partition_point`] method on slices that returns the index of the first ID not less than
11//! a given value.
12//!
13//! [`partition_point`]: https://doc.rust-lang.org/std/primitive.slice.html#method.partition_point
14use crate::util::iter::*;
15use crate::util::parse::*;
16use std::ops::Range;
17
18type Input = (Vec<Range<u64>>, Vec<u64>);
19
20pub fn parse(input: &str) -> Input {
21    let (prefix, suffix) = input.split_once("\n\n").unwrap();
22    let mut ranges: Vec<_> = prefix.iter_unsigned().chunk::<2>().collect();
23    let mut ids: Vec<_> = suffix.iter_unsigned().collect();
24    let mut range = 0..0;
25    let mut merged = Vec::new();
26
27    ranges.sort_unstable();
28    ids.sort_unstable();
29
30    // Merge ranges together.
31    for [from, to] in ranges {
32        if from < range.end {
33            range.end = range.end.max(to + 1);
34        } else {
35            merged.push(range);
36            range = from..to + 1;
37        }
38    }
39
40    merged.push(range);
41    (merged, ids)
42}
43
44pub fn part1(input: &Input) -> usize {
45    let (merged, ids) = input;
46    let position = |id| ids.partition_point(|&next| next < id);
47    merged.iter().map(|range| position(range.end) - position(range.start)).sum()
48}
49
50pub fn part2(input: &Input) -> u64 {
51    let (merged, _) = input;
52    merged.iter().map(|range| range.end - range.start).sum()
53}
aoc/year2025/day05.rs

aoc/year2025/
day05.rs
