Advent of Code 2025 - Day 5
While the forklift breaks through the wall in the fifth day of Advent of Code, I feel like I need a break after a week's worth of 6 AM morning wake-up calls. Thank God it's Friday and almost weekend, but not before solving today's puzzles.
Check out my full solution for day 5 at GitHub.
As always, let's start with the first part.
Part one
We are given a dual-part input today. The top part contains id-ranges of ingredients that are considered fresh. The top part is a list of id's of ingredients that are available. Both parts are split by an empty line, like so (the id's of the actual input are much, much bigger):
3-5
10-14
16-20
12-18
1
5
8
11
17
32
Our job for the first part is to count how many of the available ingredients are within any of the ingredient ranges. Once we have parsed the id ranges and the separate id's to integers, we can iterate over all id's and see if they fit within any of the ranges. If we've found a range that contains the id, we can break from checking any other ranges, as we only need to count each "fresh" id once.
Checking whether an id (let's call it x) is within a range comes down to a condition in the form a <= x <= b. Python allows us to write this condition down in exactly this way, which is pretty neat.
[fresh_ranges, ingredient_ids] = data
fresh_count = 0
for ingredient_id in ingredient_ids:
for fresh_range in fresh_ranges:
start, end = [int(x) for x in fresh_range.split('-')]
if start <= ingredient_id <= end:
fresh_count += 1
break
The resulting value of fresh_count gives us the answer for part one.
Part two
For the second part, we can disregard the list id's of available ingredients and focus solely on the ranges. Our job is to find all unique id's within all given ranges.
Because the size of the id-ranges in the input, it is not possible to just create a new list (or set) that contains all unique id's by iterating over all ranges and adding these id's one by one. The total number of iterations we would need per range are just too big. So we need to be smarter.
We can solve this by iterating over the ranges and for each next range, check if it (partly) overlaps with a range we checked earlier. If so, we can lower the beginning of the range or raise the end of the current range, based on how it overlaps with the previous range we added. Doing things this way, we don't need to know all id's, but only the unique ranges (without overlap). We only add a new range if it has no overlap with any of the other ranges that we already checked.
A pre-condition here is that the initial list of ranges are sorted by their starting id. Only then we can check an overlap of the current range with the previous range.
Let's look at how we can do this in code:
non_overlapping_ranges = fresh_ranges[:1]
for begin, end in fresh_ranges[1:]:
prev_begin, prev_end = non_overlapping_ranges[-1]
if prev_end >= begin - 1:
non_overlapping_ranges[-1] = (prev_begin, max(prev_end, end))
else:
non_overlapping_ranges.append((begin, end))
As the initial list of ranges is sorted, we can start by adding that first range into non_overlapping_ranges, which will contain the complete list of unique ranges once we're done iterating over all ranges.
If prev_end (the end if of the previously checked range) is bigger or equal to the start of the currently checked range, we know there is an overlap. In that case, we need to update the previously checked range rather than adding a new range. We do this by setting a new end for the previously checked range, which is either the previous end of the current end.
If there is no overlap, we just add the currently checked range as a new one.
Let's assert this logic with the example input, sorted by their start ids:
3-5
10-14
12-18
16-20
non_overlapping_ranges first contains a single range, namely the first one:
non_overlapping_ranges = [(3-5)]
Let's consider the next range (10-14) next. The previous end (5) is not bigger than the start of this next range (10), so we add this next range to the list:
non_overlapping_ranges = [(3-5), (10-14)]
For the next range (12-18) we do have an overlap, as the previous end (14) is bigger than the start of this next range (12). We use the previous start and update the end to the maximum of the previous end (14) and the end of this next range (18). That gives us the updated range (10-18).
non_overlapping_ranges = [(3-5), (10-18)]
In a similar way, we find an overlap between the next range (16-20) and the last range in the non_overlapping_ranges list (10-18). Again we update it's start and end to new values, with the updated range (10-20) as a result:
non_overlapping_ranges = [(3-5), (10-20)]
This shows that we get the correct result when following this algorithm, in this case two unique ranges without overlap. The final thing to do is count how many id's exist within these unique ranges, taking care of adding one for each range as its inclusive.
sum(end - begin + 1 for begin, end in non_overlapping_ranges
This sum is the result for part two.