Advent of Code 2025 - Day 5: Cafeteria

2025-12-05 1009 words 5 minutes

Contents

Day 5 was about checking ingredient freshness using ID ranges. Part 1 was straightforward with a range check. Part 2 required merging overlapping ranges - something I knew how to do conceptually but struggled to implement correctly.

Part 1: Check Individual IDs

Given a list of fresh ingredient ID ranges and a list of ingredient IDs to check, count how many IDs fall within any range.

The Brute Force Trap

My first instinct was to build a complete set of all fresh IDs:

1
2
3
4
5
6


total_range = []
for r in ranges:
    [start, end] = list2int(r.split('-'))
    for number in range(start, end+1):
        if number not in total_range:
            total_range.append(number)

My computer killed the program after a couple of minutes. When ranges span millions of IDs, materializing every single number is a disaster.

The Simple Solution

Instead of building ranges, just check if each ingredient falls within any range:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


def part1():
    score = 0
    lines = loadFile(input_f)
    ranges = []
    fruits = []
    split = False
    
    # Split input into ranges and IDs
    for l in lines:
        if l == '':
            split = True
        elif not split:
            ranges.append(l)
        else:
            fruits.append(l)
    
    # Check each ingredient
    for f in list2int(fruits):
        found = False
        while not found:
            for r in ranges:
                [start, end] = list2int(r.split('-'))
                if start <= f <= end:
                    found = True
                    score += 1
                    break
            break
    
    return score

The key: start <= f <= end is much faster than building massive lists. First try.

Part 2: Merge Overlapping Ranges

Part 2 asks: how many total IDs are considered fresh across all ranges? The ingredient list is now irrelevant - we just need to count unique IDs across potentially overlapping ranges.

The example:

1
2
3
4


3-5     → 3, 4, 5
10-14   → 10, 11, 12, 13, 14
16-20   → 16, 17, 18, 19, 20
12-18   → 12, 13, 14, 15, 16, 17, 18

Ranges 10-14, 16-20, and 12-18 overlap. They should merge into 10-20.

Failed Attempt 1: Materialize Everything

1
2
3
4
5


total_ranges = []
for r in ranges:
    start, end = list2int(r.split('-'))
    total_ranges.append(range(start, end+1))
score = len(set(chain.from_iterable(total_ranges)))

Terminal force quit again. With ranges spanning billions of IDs, this approach is hopeless.

Failed Attempt 2: In-Place Modification

Sort the ranges, then merge overlapping ones by modifying the list as we iterate:

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


total_ranges = sorted(total_ranges)
not_merged = total_ranges[0]
new_range = []

for x in range(0, len(total_ranges)-1):
    c = total_ranges[x]  # current
    n = total_ranges[x+1]  # next
    
    if c[1] >= n[0]:  # Overlap detected
        total_ranges[x+1][0] = c[0]
        total_ranges[x+1][1] = max(c[1], n[1])
        not_merged = total_ranges[x+1]
    else:
        new_range.append(not_merged)

new_range.append(not_merged)

Guess was too high. The problem: modifying total_ranges while iterating made the logic confusing. I was trying to track which range was “not merged” but lost track of the state.

Failed Attempt 3: Merged Flag

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


new_range = []
merged = False

for x in range(0, len(total_ranges)-1):
    c = total_ranges[x]
    n = total_ranges[x+1]
    
    if c[1] >= n[0]:
        total_ranges[x+1][0] = c[0]
        total_ranges[x+1][1] = max(c[1], n[1])
        merged = True
    else:
        new_range.append(total_ranges[x])
        if merged: 
            new_range.append(total_ranges[x+1])
        merged = False

if merged: 
    new_range.append(total_ranges[x+1])

Still too high. The flag tracking got messy.

Failed Attempt 4: Don’t Modify Original

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


new_range = []
for x in range(0, len(total_ranges)-1):
    c = total_ranges[x]
    n = total_ranges[x+1]
    
    if c[1] >= n[0]:
        t = [c[0], max(c[1], n[1])]
    else:
        t = n
        new_range.append(c)

new_range.append(t)

Too low. The bug: I wasn’t reusing the merged range. When ranges A, B, and C all overlap, I needed to merge A+B, then merge that result with C. But I was always comparing against the original ranges from total_ranges.

The Working Solution

The fix: track the “current merged range” and compare each new range against it:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


def part2(): 
    score = 0
    lines = loadFile(input_f)
    ranges = []
    
    for l in lines: 
        if l == '':
            break
        ranges.append(l)
    
    # Parse and sort ranges
    total_ranges = []
    for r in ranges:
        start, end = list2int(r.split('-'))
        total_ranges.append([start, end])
    
    total_ranges = sorted(total_ranges)
    
    # Merge overlapping ranges
    new_range = []
    c = total_ranges[0]  # Start with first range
    
    for x in range(1, len(total_ranges)):
        n = total_ranges[x]  # Next range
        
        if c[1] >= n[0]:  # Overlap: merge
            c = [c[0], max(c[1], n[1])]
        else:  # No overlap: save current, move to next
            new_range.append(c)
            c = n
    
    new_range.append(c)  # Don't forget the last range
    
    # Count total IDs
    for x in new_range:
        score += (x[1] - x[0] + 1)
    
    return score

The key insight: maintain c as the “current range being built.” When the next range overlaps, extend c. When it doesn’t overlap, save c and start fresh with the new range.

Third try in ~1ms.

The Algorithm

Range merging:

Sort ranges by start position - this ensures we process them left-to-right
Initialize current range with the first range
For each subsequent range:
- If it overlaps with current (c[1] >= n[0]), extend current to include it
- If no overlap, save current and start a new current range
Don’t forget to save the final range

Overlap check: ranges [a, b] and [c, d] overlap if b >= c (assuming sorted by start).

Performance

Part 1 brute force (building all IDs): killed after minutes
Part 1 simple check: ~100ms
Part 2 merging ranges: ~1ms

The lesson: think about data structure size. When ranges span billions of values, don’t materialize them. Work with the ranges themselves.

Ten stars total. Part 2 took several attempts to get the merge logic right, but that’s what makes it satisfying.