Advent of Code 2025; Day 5: Cafeteria

· 8 min read

Optimising the elves stock management of fresh ingredients.

Part 1: Stock Management

The cafeteria was not a mirage, but I’m not sure I would want to eat here.

It turns out that they have a new stock management system which is incredibly complex for the elves to understand. They need help sorting out which of their available inventory is still fresh.

The stock management database stores the fresh products as a range, e.g. 12-24 - this represents an inclusive set of fresh products, these ranges can also overlap. This is just what is fresh however, if they are actually in stock is determined by following list of individual product IDs.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

3-5
10-14
16-20
12-18

1
5
8
11
17
32

I can see why they are struggling.

Having done a few of these before I can see where this is going - but I’ll play a little dumb and demonstrate for this write up. The obvious answer here is an intersection of two sets. Building one set up from the available products is easy. Building the set of fresh products is a little more involved, I would need to enumerate the values in each range (inclusive both ends).

That’s easy peasy (I’ve used a loop as that was easier for me to write than a python generator):

python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def load_stock(input_data: str) -> tuple[set[int], set[int]]:
    sections = input_data.strip().split("\n\n")

    fresh = set[int]()
    for r in sections[0].splitlines():
        r2 = r.split("-")
        for id in range(int(r2[0]), int(r2[1]) + 1):
            fresh.add(id)

    available = set(map(int, sections[1].splitlines()))
    return (fresh, available)

The solution to which products are still fresh is as simple as:

python
1
2
3

def part1(input_data: str) -> int:
    fresh, ingredients = load_stock(input_data)
    return len(fresh.intersection(ingredients))

Hey presto, 3 of the available ingredients are good to go!

Let’s try it on the real data… oh.

I’ll have to explain to the elves that I need more resources; I can’t even load their database!

Or, I can just avoid unnecessary computation! That’ll save some effort. I said before that I could see where it was going - this was exactly that trap.

The key is to identify what I actually need to compute to solve this problem.

What do I need to know about each ingredient? I just need to know if it falls within any of the fresh ranges. Forget set theory for now, and just think of that algorithm.

I’ll parse my input without expanding anything, using a tuple representing each range:

python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def load_stock(input_data: str) -> tuple[list[tuple[int, int]], set[int]]:
    sections = input_data.strip().split("\n\n")
    fresh = [
        (int(start), int(end)) 
        for start, end in (
            r.split("-") 
            for r in sections[0].splitlines()
        )
    ]
    available = set(map(int, sections[1].splitlines()))
    return (fresh, available)

As a sort of naive approach to this I can now just do the exact algorithm I mentioned; iterate through each ingredient, and then check if it falls within any of the ranges:

python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def isfresh(fresh: list[tuple[int, int]], id: int) -> bool:
    for start, end in fresh:
        if id >= start and id <= end:
            return True
    return False 

def part1(input_data: str) -> int:
    fresh, ingredients = load_stock(input_data)
    return sum(
        1
        for ingredient in ingredients
        if isfresh(fresh, ingredient)
    )

And that simple change is able to complete almost instantly! It’s not even that well optimised as it still checks every possible range for each ingredient - I suspect this will probably be an issue in part 2.

Part 2: Fresh Ingredients

The elves are now able to remove their spoiled inventory items. They just want to untange their ridiculous database and need a list of all ingredient IDs that are considered fresh.

That seems simple, just sum each range:

python
1
2
3
4
5
6

def part2(input_data: str) -> int:
    fresh, _ = load_stock(input_data)
    return sum(
        end - start
        for start, end in fresh
    )

Not quite, I fell for the trap because I forgot an important point: the ranges can overlap. I need to count each distinct fresh ingredient ID, regardless of how many ranges it appears within.

I already know what not to do here as that is exactly what I demonstrated at the beginning - I can’t just enumerate all the ranges into a set and count the result.

So what can be done? What if I just take the smallest start value of a range, and the largest end value?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

          3     5
          ├─────┤
                               10         14
                               ├───────────┤
                                                 16         20
                                                 ├───────────┤
                                     12               18
                                     ├─────────────────┤
   ─┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──▶
    1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
          ▲                                                  ▲
          └── min = 3                              max = 20 ─┘

          ├───────────────────── 3 to 20? ───────────────────┤
                      ▲
                      └─ but 6-9 aren't fresh!

That gives me an overall range covering all ingredients, but what it doesn’t tell me about is areas of spoiled ingredients within it that weren’t covered by any individual ranges.

There’s something in that idea though, if I sort on the start of each range, I can iterate through and track the end of the range until there there is a break where the start value is outside the current range.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

  unsorted           sorted
  ─────────          ───────────────
   3-5                  3-5   
   10-14                10-14  ─┐
   16-20                12-18   ├─ these three overlap!
   12-18                16-20  ─┘

          3     5
          ├─────┤
                               10         14
                               ├───────────┤
                                     12               18
                                     ├─────────────────┤
                                                 16         20
                                                 ├───────────┤
   ─┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──▶
    1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
                               ▲                             ▲
                               └─ max_end = 14... 18... 20 ──┘

I could then eliminate anything that has both a start and end value less than that maximum as it’s automatically consumed by it too.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

  iteration 1:  (10, 14)   start=10, end=14
                max_end = 14
                           ├────────┤

  iteration 2:  (12, 18)   start 12 <= max_end 14? YES ─▶ overlaps!
                           end 18 > max_end 14? YES ─▶ extend max_end to 18
                           ├─────────────────┤

  iteration 3:  (16, 20)   start 16 <= max_end 18? YES ─▶ overlaps!
                           end 20 > max_end 18? YES ─▶ extend max_end to 20
                           ├─────────────────────────┤

  result: three ranges (10-14, 12-18, 16-20) merged into one: (10, 20)

  final merged ranges
  ───────────────────
     3-5   ─▶  (3, 5)    = 3 items
    10-20  ─▶  (10, 20)  = 11 items
                         ─────────
                    total: 14 fresh

That leaves me with another start point which follows the same process until all ranges are consumed. I think that’ll do it - now how to actually write that in python.

python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def part2(input_data: str) -> int:
    fresh, _ = load_stock(input_data)
    fresh.sort()

    ranges = []
    min_start, max_end = fresh[0]
    for start, end in fresh[1:]:
        if start <= max_end:
            if end >= max_end:
                max_end = end
            continue
        ranges.append((min_start, max_end))
        min_start, max_end = start, end
    ranges.append((min_start, max_end))

    return sum(
        end - start + 1
        for start, end in ranges
    )

It’s probably not pythonic, and I don’t love it (having to “flush” the last range after the loop seems a little awkward to me) - it works though.

Hopefully the cafeteria can get back on track now - I think the dining hall might be next.

More Pythonic?

The question I ask myself once again - how do I make this more python? I don’t think it’s too bad actually; using built in sort functions, slices, a generator to sum the result.

I think the best I can do is clean up a few bits that I didn’t like, I could actually append each new range immediately, and reference it directly in subsequent iterations with [-1] and replacing it, meaning that I don’t need to flush it at the end because it’s already in the list.

python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def part2(input_data: str) -> int:
    fresh, _ = load_stock(input_data)
    fresh.sort()

    ranges = [fresh[0]]
    for start, end in fresh[1:]:
        min_start, max_end = ranges[-1]
        if start <= max_end:
            ranges[-1] = (min_start, max(max_end, end))
        else:
            ranges.append((start, end))

    return sum(
        end - start + 1 
        for start, end in ranges
    )

Also, there’s a built-in max function I wasn’t using before which is much the same as what I’ve used in Rust, it compares two values returning the largest - perfect for tweaking the end of the range.

As always, full code is available at github.com/lordmoocow/aoc25.

This is where it starts to get interesting. Naive solutions will not do anymore; it’s easy to see the problem and reason about a solution to the example only to find that the real input is designed to be near impossible to process. It really makes you think about necessary computation to achieve the goal. Just 7 days to go now.