Advent of Code 2025 - Python - Day 4

05 Aug, 2026

Today, we've reached the North Pole cafeteria through the newly-made hole in the wall. The elves here are having trouble determining what food is fresh and what food is spoiled as they've just switched to a new inventory management system. They have a database, which looks like:

The format here is that the top portion gives us ranges for fresh ingredient IDs and the bottom portion gives us a list of available ingredient IDs. Anything that's available but not fresh is spoiled.

Part 1

We need to determine how many of the available ingredient IDs are fresh.

This problem seems straightforward enough: we'll read the file, encode the ranges, then test each ID against each range. If an ID is outside of all the ranges, then it must be spoiled. If it's inside any range, it's fresh.

This has the downside of O(n*m) complexity, where n and m are the number of ranges and number of IDs to check, respectively. As we add more of each, the number of checks we have to perform skyrockets. I have some ideas for making our algorithm more efficient, but for now we'll take this straightforward, inefficient approach.

I think I'll use classes for the first time, here. What I'd really like is just a C-style struct, but those don't exactly exist in Python. At least, they didn't for a long time. Now we have to use a decorator on a class which I think is fairly obtuse for what should be a simple operation of defining the shape of some data, but we can only use the Python we've got:

from dataclasses import dataclass

@dataclass
class Range:
	first: int
	last: int

This class will give our ranges some structure. In a previous day we also had to deal with ranges provided by our input file, and back then we used a tuple where we just knew that the 0th index was the start of the range and the 1st index was the end. Here, we can encode that information more directly.

To parse our input file, we'll read it as normal. Then, we'll read ranges until we get to a blank line, and read single IDs from there:

# Parse ranges
ranges = []
separationLineIdx = 0
for index, line in enumerate(rawLines):
    # If we've reached the separation line between ranges and IDs,
    #   note the index and exit the loop
    if line == "":
        separationLineIdx = index
        break

    parts = line.split("-")
    ranges.append(Range(int(parts[0]), int(parts[1])))

# Parse IDs
IDs = []
for line in rawLines[separationLineIdx+1:]:
    IDs.append(int(line))

Here we're building on some of the techniques we tried in previous puzzles - we're using enumerate, we're casting values to ints to make numerical comparison easier later on, and using Pythons : operator when slicing up lists. I've said it in most of my posts so far, but I'll say it again: Python is really good at parsing text and doing this kind of simple processing on it.

With our data all parsed and in the right formats, our processing logic is straightforward:

# Compute which IDs are fresh
freshIDs = 0
for ID in IDs:
    for thisRange in ranges:
        if ID >= thisRange.first and ID <= thisRange.last:
            freshIDs += 1
            break

As stated at the start of this section, the approach here is a simple one. We simply check every range for every ID, and if it fits in any of the ranges we increment our counter and move on to the next ID.

This gives us a complete Part 1 script:

from dataclasses import dataclass


@dataclass
class Range:
    first: int
    last: int


rawLines = []
with open("data/5.long", "r") as f:
    rawLines = [line.strip() for line in f.readlines()]

# Parse ranges
ranges = []
separationLineIdx = 0
for index, line in enumerate(rawLines):
    # If we've reached the separation line between ranges and IDs,
    #   note the index and exit the loop
    if line == "":
        separationLineIdx = index
        break

    parts = line.split("-")
    ranges.append(Range(int(parts[0]), int(parts[1])))

# Parse IDs
IDs = []
for line in rawLines[separationLineIdx+1:]:
    IDs.append(int(line))

# Compute which IDs are fresh
freshIDs = 0
for ID in IDs:
    for thisRange in ranges:
        if ID >= thisRange.first and ID <= thisRange.last:
            freshIDs += 1
            break

print(freshIDs)

This gives us the correct answer of 3 for the short input, shown at the top of this post, and 848 for the longer "real" input. The real input took 0.029 seconds to run, so even though we chose a relatively poor algorithm for this problem, it was still perfectly sufficient for what we needed.

Part 2

For Part 2, the elves are thinking ahead, to when they get new food stocks and I'm not around to help them determine what's fresh and what's not. They want a count of how many unique ingredient IDs are fresh.

This is complicated by the fact that some of the provided ranges overlap, so we can't just add up the lengths of the ranges.

Luckily, Python provides a collection type aimed exactly at this sort of problem: a set. A set is like a list, but it doesn't allow duplicate elements. If you try to add a value to a set and that value is already present in the set, nothing happens. Our plan will be to create a set of all allowable IDs and then query the set to see how many items are in it.

We no longer need to compute which IDs are fresh, and in fact we don't care about the IDs part of the input at all, just the ranges. We'll remove the "Parse IDs" and "Compute which IDs are fresh" sections of the code, and replace it with a new processing loop that adds every ID in every range to our set:

# Create set of all valid IDs
idSet = set()
for thisRange in ranges:
    for i in range(thisRange.first, thisRange.last + 1):
        idSet.add(i)

This logic is simple and straightforward. We're using built-in Python functionality to solve our problems. It's all very Pythonic. It computes the correct answer for our short input - 14 - at blazing speeds.

And for the long input, it runs out of memory and is killed by my OS after requesting 70GB to try and hold all the values that are being put into my set.

So this approach is a nonstarter. A good lesson that just because something is theoretically sound doesn't mean it'll actually work in practice. For a theoretical computer with infinite memory and infinitely-fast processing, this is the easiest solution. For a real computer, though, this approach is not workable.

We need to get more complicated. I can think of two approaches:

Count unique IDs based on whether and how much each range overlaps other ranges. A per-ID approach won't work, as we've seen, but checking if one range is fully inside another, or if the end of a range is inside another range, and so on might be feasible.
Modify the ranges themselves by combining them if they overlap. By the time processing is finished, we'll have a list of fully-unique ranges and we can just add their lengths together to get the count of total valid IDs.

I'll start with #2 since that seems easier. We'll parse our ranges as before. When it's time to process them, we'll take each range in turn and compare it to every range farther on in the range list (i.e., for ranges [A, B, C, D] we compare A with B, A with C, and A with D; then B with C and B with D; then C with D). If the start or end of either is inside the other, we'll delete one of the ranges and adjust the start/end of the other appropriately to cover the extents of the combined range. At the end, we'll have a list of exclusive ranges that we'll be able to iterate through and quickly compute the length of.

Instead of actually deleting ranges (using e.g. the del keyword, or using a "tombstone" marker), since that could be a little complicated, we'll keep a separate list where we put our merged lists. We won't be too precious about making sure that list only has finalized ranges, but that'll mostly be the case. The code will explain:

# Sort the ranges by their starting ID
sortedRanges = sorted(ranges, key=lambda r: r.first)

# Initialize the finalized list of ranges with the earliest range in the
#   sortedRanges list
merged = [sortedRanges[0]]

for thisRange in sortedRanges[1:]:
    # Check thisRange against the latest (last) range in the finalized list
    #   of ranges
    latest = merged[-1]

    if thisRange.first <= latest.last + 1:
        # If thisRange starts before the end of the latest range in merged,
        #   or if the ranges touch, merge the ranges
        latest.last = max(latest.last, thisRange.last)
    else:
        # If not, append thisRange to merged
        # It will be the latest range in our next loop iteration
        merged.append(thisRange)

countSum = sum(thisRange.last - thisRange.first + 1 for thisRange in merged)

This uses a couple new python constructs:

sorted sorts a collection of objects based on the sorting function you provide. I think there are also some built-in sorting functions, and I think you can provide function names to use "full" functions here. As you can see, I use a lambda. I don't really like sorted - it changes things in-place and I always get the syntax mixed up with <list>.sort(). But using sorted is more efficient in cases where you don't need to use the old data later.
lambdas are little mini "anonymous" (unnamed) functions that you define in-line. They operate over "closures", where they capture some variable or variables from the context in which they reside and then use those values inside their function. In this case, the lambda captures r and returns r.first. This is basically saying "for every object in the collection you give me, which I'll refer to as r, I'll return r.first". In the context of a sorted function, it means that the ranges will be sorted based on their first value.

I think the comments do a good job explaining the code, here. The higher-level "algorithm" we're trying to model here is that of a "working stack" of lists in merged, where anything that's not the last item in the list is finalized. For each new range (and remember, the list of new ranges is sorted with low first IDs first in the list and high IDs last), we compare it against the last item in the merged list. That item is also, by definition, the item in the merged list with the latest starting ID and the latest ending ID.

If thisRange's start is before, equal to, or directly adjacent to (that's the +1) latest's end, then the ranges can be merged. We do that by extending latest's end, if necessary (it's possible that thisRange both starts and ends within latest, in which case we wouldn't want to change latest's end - that's why we use max). If we extend latest, then we don't append thisRange to merged and after extending we move on to the next thisRange in our list.

If thisRange doesn't overlap with latest, then we append thisRange to the merged list, and on the next loop iteration it'll be the value we retrieve from merged when we take the last range from the list.

I think this is a very elegant solution - we end up filling merged with a single range, extending that range until there's a discontinuity, adding a new range, extending that one until there's a discontinuity, and so on. The key insight is that if you sort the ranges by first you get some useful properties our of your resulting list.

This took me a few hours to think up while doing other work. I've found that sometimes the best way to solve a problem isn't to lock in and stare at it until you work it out, it's to go do something else and give your mind time to chew on the issue. This was definitely one of those times.

Now, our final code is as follows:

from dataclasses import dataclass
from typing import List


@dataclass
class Range:
    first: int
    last: int


def combineRanges(rangeList: List[Range], idxOne: int,
                  idxTwo: int) -> List[Range]:
    # Get a local reference to the ranges, for brevity
    rangeOne = rangeList[idxOne]
    rangeTwo = rangeList[idxTwo]

    # Disable the second range
    rangeTwo.enabled = False

    # Set the first range's first and last to the extremes of the two
    rangeOne.first = min(rangeOne.first, rangeTwo.first)
    rangeOne.last = max(rangeOne.last, rangeTwo.last)

    # Recompute its count
    rangeOne.count = rangeOne.last - rangeOne.first + 1

    # Update then return the range list
    rangeList[idxOne] = rangeOne
    rangeList[idxTwo] = rangeTwo

    return rangeList


rawLines = []
with open("data/5.long", "r") as f:
    rawLines = [line.strip() for line in f.readlines()]

# Parse ranges
ranges = []
for index, line in enumerate(rawLines):
    # If we've reached the separation line between ranges and IDs,
    #   note the index and exit the loop
    if line == "":
        break

    parts = line.split("-")
    ranges.append(Range(int(parts[0]), int(parts[1])))

# Sort the ranges by their starting ID
sortedRanges = sorted(ranges, key=lambda r: r.first)

# Initialize the finalized list of ranges with the earliest range in the
#   sortedRanges list
merged = [sortedRanges[0]]

for thisRange in sortedRanges[1:]:
    # Check thisRange against the latest (last) range in the finalized list
    #   of ranges
    latest = merged[-1]

    if thisRange.first <= latest.last + 1:
        # If thisRange starts before the end of the latest range in merged,
        #   or if the ranges touch, merge the ranges
        latest.last = max(latest.last, thisRange.last)
    else:
        # If not, append thisRange to merged
        # It will be the latest range in our next loop iteration
        merged.append(thisRange)

countSum = sum(thisRange.last - thisRange.first + 1 for thisRange in merged)

print(countSum)

For our short input, this gives us the same answer as before: 14. All that for no change in result.

For the longer input, though this approach actually works, and gives me the apparently-correct result of 334714395325710. In only 0.018 seconds! Seeing that there are 33.4 trillion unique IDs makes me see that trying to use a set was hopeless folly. It's the most straightforward way to handle the problem, but the memory demands of holding all those values in memory are intractable. The resource demands of our final solution, meanwhile, are miniscule.

I think it's clear that this puzzle was specifically designed to have so many unique IDs that you had to do some sort of clever range-combination or range-counting scheme. I appreciate that they setup a clear solution and then managed to disallow it at the same time. Great work by the AoC team.

On to Day 6!