Advent of Code 2025 Day 5: Cafeteria
"""Advent of Code 2025: Day 5 - Cafeteria"""
from advent import parse, positive_ints
Ingredient = int
Range = tuple[int, int]
section1, section2 = parse(5, str.split, sep='\n\n')
fresh_ranges: list[Range] = [positive_ints(r) for r in section1] # type: ignore
ingredients: list[Ingredient] = [int(i) for i in section2]
def merge_overlapping_ranges(fresh_ranges: list[Range]) -> set[Range]:
"""Compute a set of disjoint fresh ranges by merging overlapping ranges.
We first sort the ranges so overlapping ranges are contiguous."""
fresh_ranges = sorted(fresh_ranges)
ranges_overlap = lambda p1, p2: p1[0] <= p2[0] <= p1[1] or p1[0] <= p2[1] <= p1[1]
merge_ranges = lambda pair, p: (min(pair[0], p[0]), max(pair[1], p[1]))
disjoint_ranges = set()
while fresh_ranges:
a_range = fresh_ranges.pop(0)
while fresh_ranges and ranges_overlap(a_range, fresh_ranges[0]):
other_range = fresh_ranges.pop(0)
a_range = merge_ranges(a_range, other_range)
disjoint_ranges.add(a_range)
return disjoint_ranges
def part1(fresh_ranges: list[Range], ingredients: list[Ingredient]) -> int:
"""Return the number of fresh ingredients by counting the number of ingredients
in any fresh range."""
is_fresh = lambda ingredient: any(low <= ingredient <= high for low, high in fresh_ranges)
return sum(1 for ingredient in ingredients if is_fresh(ingredient))
def part2(fresh_ranges: list[Range]) -> int:
"""Return the total possible fresh ingredient IDs by summing the length of
each range after merging overlapping ranges."""
range_size = lambda low, high: high - low + 1
return sum(range_size(*r) for r in merge_overlapping_ranges(fresh_ranges))
assert part1(fresh_ranges, ingredients) == 707
assert part2(fresh_ranges) == 361615643045059
Type Aliases
First, I created a couple type aliases to provide more meaningful types:
Input Parsing
Today is the first puzzle of the year with sections in the input. We're given two sections separated by a blank line. The first section is a list of ranges of "fresh product IDs", e.g.:
3384729050352-7936448865239
312542493529001-320844283048233
303215714751321-303735832077393
546740807916189-549412906179109
...
The second section is a list of product IDs, e.g.:
The following code provides us with our list of Ranges and list of Ingredients:
section1, section2 = parse(5, str.split, sep='\n\n')
fresh_ranges: list[Range] = [positive_ints(r) for r in section1] # type: ignore
ingredients: list[Ingredient] = [int(i) for i in section2]
Helper Functions
We only need one helper function today, merge_overlapping_ranges(). Our list of ranges of
fresh ingredient IDs can be in any order, and ranges may overlap. Our goal is to compute
a set of disjoint (i.e. non-overlapping) regions, which we'll need for part 2.
If we sort the list of ranges, we're assured that sets of overlapping ranges will be contiguous, then we can iterate over the ranges one by one, and merge any overlapping ranges into a single range.
def merge_overlapping_ranges(fresh_ranges: list[Range]) -> set[Range]:
"""Compute a set of disjoint fresh ranges by merging overlapping ranges.
We first sort the ranges so overlapping ranges are contiguous."""
fresh_ranges = sorted(fresh_ranges)
ranges_overlap = lambda p1, p2: p1[0] <= p2[0] <= p1[1] or p1[0] <= p2[1] <= p1[1]
merge_ranges = lambda pair, p: (min(pair[0], p[0]), max(pair[1], p[1]))
disjoint_ranges = set()
while fresh_ranges:
a_range = fresh_ranges.pop(0)
while fresh_ranges and ranges_overlap(a_range, fresh_ranges[0]):
other_range = fresh_ranges.pop(0)
a_range = merge_ranges(a_range, other_range)
disjoint_ranges.add(a_range)
return disjoint_ranges
Solution
With the parsing and helper function out of the way, the parts are straightforward. For part 1, we just need to count the number of fresh ingredients:
def part1(fresh_ranges: list[Range], ingredients: list[Ingredient]) -> int:
"""Return the number of fresh ingredients by counting the number of ingredients
in any fresh range."""
is_fresh = lambda ingredient: any(low <= ingredient <= high for low, high in fresh_ranges)
return sum(1 for ingredient in ingredients if is_fresh(ingredient))
For part 2, we compute our set of disjoint regions, and then sum up the sizes of all the regions:
def part2(fresh_ranges: list[Range]) -> int:
"""Return the total possible fresh ingredient IDs by summing the length of
each range after merging overlapping ranges."""
range_size = lambda low, high: high - low + 1
return sum(range_size(*r) for r in merge_overlapping_ranges(fresh_ranges))