Advent of Code 2025 - Day 5

Useful Links

Concepts and Packages Demonstrated

Problem Intro
Part 1
Part 2
Results
Reflecting on this Puzzle

Problem Intro

We’ve broken through the wall and found a cafeteria! The Elves are having trouble with their new inventory management system. They need to figure out which ingredients are fresh.

Our input consists of two blocks of data:

A list of fresh ingredient ID ranges (inclusive).
A list of available ingredient IDs.

Example input:

Part 1

How many of the available ingredient IDs are fresh?

First, we need to parse the input. It’s split into two blocks separated by a blank line.

def parse_input(data: str):
    """Parse the input data into two blocks:
    - inclusive ranges (list of [start, end])
    - and available IDs (list of IDs)
    """
    inclusive_ranges, available_ids = data.split("\n\n")
    inclusive_ranges = [list(map(int, line.split("-"))) for line in inclusive_ranges.splitlines()]
    available_ids = list(map(int, available_ids.splitlines()))

    return inclusive_ranges, available_ids

Here, I’m using data.split("\n\n") to separate the two blocks. Then, for the ranges, I iterate through each line and use map(int, line.split("-")) to convert the “start-end” string into a list of two integers [start, end]. Similarly, for the available IDs, I use map(int, ...) to convert the strings to integers.

To solve Part 1, we just need to check if each available ID falls into any of the fresh ranges.

def part1(data: str):
    """ How many of the available ingredient IDs are fresh? """
    inclusive_ranges, available_ids = parse_input(data)
    
    # Check if each available ID is within any of the fresh ingredient ID ranges
    fresh_ids = [id for id in available_ids 
                 if any(id >= start and id <= end for start, end in inclusive_ranges)]

    return len(fresh_ids)

I use a list comprehension to filter the available_ids. The condition any(...) checks if the current id is within the bounds of start and end for any of the ranges in inclusive_ranges.

Part 2

How many ingredient IDs are considered to be fresh according to the fresh ingredient ID ranges?

Now we need to look at the ranges themselves. The problem is that the ranges can overlap. For example, 10-14 and 12-18 overlap. If we just summed up the lengths of the ranges, we’d double-count the overlapping parts (12, 13, 14).

Since the ranges are large (my input contains ranges like 302553299774028-302939011277575), we can’t just use set intersection to determine the valid IDs. We need to merge the intervals.

Merging Intervals

This is a classic algorithm.

Sort the intervals: We sort them by their start value. If start values are equal, Python’s default sort will use the end value as a tie-breaker.
Iterate and Merge: We iterate through the sorted intervals and maintain a stack of merged intervals.
- If the current interval overlaps with the interval at the top of the stack (i.e., current_start <= stack_top_end), we merge them. The new end is the maximum of the two ends.
- If they don’t overlap, we push the current interval onto the stack.

def merge_intervals(intervals: list[list]) -> list[list]:
    """ 
    Takes intervals in the form [[a, b][c, d][d, e]...]
    Intervals can overlap. Compresses to minimum number of non-overlapping intervals. 
    """
    intervals.sort() # Sort intervals by start; if same start, sort by end
    stack = []
    stack.append(intervals[0])
    
    # First interval already added. Process the rest.
    for interval in intervals[1:]:
        # Check for overlapping interval
        if stack[-1][0] <= interval[0] <= stack[-1][-1]:
            stack[-1][-1] = max(stack[-1][-1], interval[-1])
        else:
            stack.append(interval)
      
    return stack

Once we have the merged, non-overlapping intervals, we can simply calculate the total number of fresh IDs by summing the lengths of these merged intervals.

def part2(data: str):
    # ...
    merged_ranges = merge_intervals(inclusive_ranges)
    
    total_fresh_ids = sum(end - start + 1 for start, end in merged_ranges)
    return total_fresh_ids

I use sum() with a generator expression to calculate the total count. Note the + 1 because the ranges are inclusive (e.g., 3-5 has length 5 - 3 + 1 = 3).

Results

The output looks like this:

Part 1 soln=523
Part 2 soln=156919837966955

It runs in 0.001 seconds, so that’s pretty darn fast!

Reflecting on this Puzzle

This puzzle took me very little time to solve, which I was super happy about. But I was reflecting on my learning journey with AoC over the years. And it occurred to me: if I’d come across this puzzle three or four years ago, it would have probably taken me a couple of hours, rather than a few minutes.

Why?

I’m much faster at working with comprehensions, which just makes life easier.
The naive me would have tried to implement with the obvious choice - set algebra. It would have worked for the sample input, but then would not have scaled to the real input. I would have wasted a lot of time on this.
It would have taken me a little while to implement the merge logic. But I’ve seen these merging problems before, and I’ve previously written a merge function that I could just reuse.

So, I conclude that AoC has not only taught me how to write better code, but it has also helped me to develop good problem solving skills, how to spot the appropriate algorithm to use, and it’s helped me to quickly spot the “gotchas” to watch out for.

Thanks Eric and the AoC team!!

‹›

Learning Python with Advent of Code Walkthroughs