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

aoc/year2025/
day05.rs
