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 std::ops::Range;
15
16use crate::util::iter::*;
17use crate::util::parse::*;
18
19type Input = (Vec<Range<u64>>, Vec<u64>);
20
21pub fn parse(input: &str) -> Input {
22    let (prefix, suffix) = input.split_once("\n\n").unwrap();
23    let mut ranges: Vec<_> = prefix.iter_unsigned().chunk::<2>().collect();
24    let mut ids: Vec<_> = suffix.iter_unsigned().collect();
25    let mut range = 0..0;
26    let mut merged = Vec::new();
27
28    ranges.sort_unstable();
29    ids.sort_unstable();
30
31    // Merge ranges together.
32    for [from, to] in ranges {
33        if from < range.end {
34            range.end = range.end.max(to + 1);
35        } else {
36            merged.push(range);
37            range = from..to + 1;
38        }
39    }
40
41    merged.push(range);
42    (merged, ids)
43}
44
45pub fn part1(input: &Input) -> usize {
46    let (merged, ids) = input;
47    let position = |id| ids.partition_point(|&next| next < id);
48    merged.iter().map(|range| position(range.end) - position(range.start)).sum()
49}
50
51pub fn part2(input: &Input) -> u64 {
52    let (merged, _) = input;
53    merged.iter().map(|range| range.end - range.start).sum()
54}
aoc/year2025/day05.rs

aoc/year2025/
day05.rs
