Advent of Code 2025 - Day 5: Cafeteria

#adventofcode #rust #programming #algorithms

The Problem

The Elves have a database with fresh ingredient ID ranges and need to check their inventory. Part 1 asks: given specific ingredient IDs, how many are fresh (fall within the ranges)? Part 2 reveals the real question: how many total IDs do these ranges cover?

Example:

Ranges: 3-5, 10-14, 16-20, 12-18
IDs to check: 1, 5, 8, 11, 17, 32
Fresh IDs from list: 3 (IDs 5, 11, 17)
Total IDs covered by ranges: 14

My Approach

When I saw overlapping ranges in Part 1, I knew Part 2 would likely ask about the ranges themselves. A brute-force check works for Part 1, but counting all IDs with overlaps is messy. So I merged the ranges upfront; if ranges overlap, combine them into one. This made Part 2 trivial.

Merging Ranges

Sort ranges and merge overlapping intervals. Ranges like 10-14 and 12-18 become 10-18.

fn merge_ranges(fresh_ranges: &mut Vec<(u64, u64)>) -> Vec<(u64, u64)> {
    // Sort ranges in descending order by start value
    // This allows us to pop from the end (smallest start) for processing
    fresh_ranges.sort_by(|a, b| b.0.cmp(&a.0));
    let mut merged_ranges: Vec<(u64, u64)> = Vec::new();

    while fresh_ranges.len() > 0 {
        // Pop the range with the smallest start value
        let mut range = fresh_ranges.pop().unwrap();

        if fresh_ranges.len() == 0 {
            // Last range, just add it
            merged_ranges.push(range);
        } else {
            // Check if the current range overlaps with the next range
            // Ranges overlap if current end >= next start
            if range.1 >= fresh_ranges.last().unwrap().0 {
                // Merge: pop the next range and extend the current range's end
                let another = fresh_ranges.pop().unwrap();
                range.1 = range.1.max(another.1);
                // Push merged range back to continue merging
                fresh_ranges.push(range);
            } else {
                // No overlap, add to merged list
                merged_ranges.push(range);
            }
        }
    }
    merged_ranges
}

Part 1: Check Specific IDs

Check if each ingredient falls within any merged range.

fn fresh_ingredients(fresh_ranges: &Vec<(u64, u64)>, ingredients: &Vec<u64>) -> u32 {
    let mut count = 0;
    for ingredient in ingredients {
        for range in fresh_ranges {
            if range.0 <= *ingredient && range.1 >= *ingredient {
                count += 1;
                break;
            }
        }
    }
    count
}

Part 2: Count All Fresh IDs

Sum the size of each merged range.

fn all_fresh_ingredients(fresh_ranges: &Vec<(u64, u64)>) -> u64 {
    let mut count = 0;
    for range in fresh_ranges {
        count += range.1 - range.0 + 1;
    }
    count
}