Advent of Code 2025 - Day 5: Cafeteria

multicolored illustration

niels jaspers • december 5, 2025

This is part five of an ongoing series of posts about my experiences solving the Advent of Code 2025 puzzles. This year, I'm doing a showdown with my good friend Levi. Since AoC is twelve days long this year, we'll be solving the puzzles in twelve different languages.

Day 5 of Advent of Code 2025 was supposed to be straightforward. Check if some IDs fall within some ranges. Count them. Simple, right?

Then Levi sent me his runtime: 0.4 milliseconds. Mine was 8ms. Twenty times slower. His only hint: "less is more."

The Problem

We're given a database of "fresh ingredient ID ranges" and a list of ingredient IDs to check.

Part 1: Count how many IDs fall within any range.

Part 2: Merge overlapping ranges and count the total number of fresh IDs.

Input looks like this: 

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

1
5
8
11
17
32

The ranges are inclusive and can overlap. ID 17 is fresh because it falls in both 16-20 and 12-18. Simple enough.

The "Smart" Solution (8ms)

My first instinct was to be clever. I built:

The time complexity looked good on paper. O(n log n) for sorting, O(log k) per lookup after merging. This should fly.

8 milliseconds.

Levi was doing the same problem in 0.4ms. What was I missing?

The "Less is More" Revelation

After banging my head against optimization ideas (memory-mapped files? Custom parsers? Interval trees?), I tried something stupid: what if I just... didn't do any of the clever stuff? 

long[] starts = new long[numRanges];
long[] ends = new long[numRanges];

for (long id : ids) {
    for (int i = 0; i < numRanges; i++) {
        if (id >= starts[i] && id <= ends[i]) {
            total++;
            break;
        }
    }
}

No sorting. No merging. No binary search. Just primitive arrays and a nested loop.

The math looks worse on paper: 188 ranges times 1000 IDs = 188,000 comparisons versus ~7,500 with binary search.

But here's what the math doesn't capture.

Why the "dumb" solution wins

My "smart" solution had hidden costs:

Every access to ranges.get(mid).get(0) involves 5 pointer dereferences:

  1. Look up the outer ArrayList's internal array
  2. Get the inner ArrayList object reference
  3. Look up that ArrayList's internal array
  4. Get the Long object reference
  5. Unbox the Long to get the actual long value

Plus: cache misses everywhere (objects scattered in heap memory), method call overhead (.get(), .compareTo()), and branch misprediction (binary search jumps around randomly).

The "dumb" solution has none of that:

Modern CPUs can blast through primitive array accesses at billions per second. The overhead of my "clever" abstractions was killing performance.

Result: ~5ms.

Better. But still 10x slower than Levi.

The File I/O Wall

I stripped everything out. No calculations, no range checking. Just read the file and time it: 

BufferedReader reader = new BufferedReader(new FileReader("data/day5/day5.txt"));
String line;
while ((line = reader.readLine()) != null) {
    // do nothing
}

2 milliseconds.

Just reading the file took 2ms. How could Levi possibly solve the entire problem in 0.4ms if reading the file alone takes 5x longer?

I tried FileChannel with memory-mapped buffers. Slower. I tried Files.readAllBytes(). About the same.

The JVM Warmup Trick

I finally asked Levi how he was measuring. His answer: run it 1000 times and take the average time.

Something like this: 

for (int i = 0; i < 1000; i++) {
    long start = System.nanoTime();
    solve();
    long end = System.nanoTime();
    long duration = (end - start) / 1000000; // Convert to milliseconds
    total += duration;
}
long average = total / 1000;

I added the warmup loop.

0.2 milliseconds.

I was now faster than Levi. The solution that took 8ms cold was 0.2ms warmed up.

What the hell, Java?

Here's what's happening on that first cold run:

  1. Class loading: JVM loads and verifies bytecode
  2. Interpretation: Code runs in the interpreter first (slow)
  3. JIT compilation: JVM profiles \"hot\" code paths, then compiles them to native machine code while your program is running
  4. File caching: First read hits disk; subsequent reads come from OS memory cache

After warmup, your code is native machine instructions, all data is in OS cache, and the JIT has applied optimizations like inlining, escape analysis, and loop unrolling.

This is why Java dominates server applications (warmup cost becomes irrelevant over hours of runtime) but feels sluggish for CLI tools and AoC-style puzzles where you run once and exit.

Part 2: Merging Intervals

Part 2 asks: how many total IDs are considered fresh across all ranges? Now we need to merge overlapping ranges to avoid double-counting.

The test data has ranges [3-5, 10-14, 16-20, 12-18]. Notice that 10-14, 12-18, and 16-20 all overlap or touch. We need to merge them into a single range 10-20 before counting.

The Algorithm

Step 1: Sort ranges by start value (with end as tiebreaker).

Unsorted: [3-5, 10-14, 16-20, 12-18]

Sorted: [3-5, 10-14, 12-18, 16-20]

Why sort? The merge algorithm assumes we process ranges left-to-right. If ranges are out of order, we might \"close\" a merged range too early and miss an overlap that comes later.

Step 2: Single-pass merge.

We maintain a \"current\" merged range [curStart, curEnd] and process each range in order:

Step 3: Sum the lengths.

For each merged range, add (end - start + 1) to the total.

Worked Example

Let's trace through the sorted ranges [3-5, 10-14, 12-18, 16-20]:

Initialize with the first range:

curStart = 3, curEnd = 5

Process 10-14:

Is 10 <= 5 + 1? No, 10 > 6.

Current range [3-5] is complete. Save it.

Start new range: curStart = 10, curEnd = 14

Process 12-18:

Is 12 <= 14 + 1? Yes, 12 <= 15.

They overlap! Extend: curEnd = max(14, 18) = 18

Current range is now [10-18]

Process 16-20:

Is 16 <= 18 + 1? Yes, 16 <= 19.

They overlap! Extend: curEnd = max(18, 20) = 20

Current range is now [10-20]

End of input: Save the final range [10-20].

Result: Two merged ranges: [3-5] and [10-20]

Count: (5-3+1) + (20-10+1) = 3 + 11 = 14 fresh IDs.

The Code

// Sort by start, then end
Arrays.sort(idx, (a, b) -> {
    int cmp = Long.compare(rangeStarts[a], rangeStarts[b]);
    return (cmp != 0) ? cmp : Long.compare(rangeEnds[a], rangeEnds[b]);
});

// Apply sorted order to arrays
long[] sortedStarts = new long[numRanges];
long[] sortedEnds = new long[numRanges];
for (int k = 0; k < numRanges; k++) {
    sortedStarts[k] = rangeStarts[idx[k]];
    sortedEnds[k] = rangeEnds[idx[k]];
}
rangeStarts = sortedStarts;
rangeEnds = sortedEnds;

// Merge pass
int write = 0;
long curStart = rangeStarts[0];
long curEnd = rangeEnds[0];

for (int i = 1; i < numRanges; i++) {
    long s = rangeStarts[i];
    long e = rangeEnds[i];
    
    if (s <= curEnd + 1) {
        // Overlapping or adjacent - extend current range
        curEnd = Math.max(curEnd, e);
    } else {
        // Gap - save current range and start new one
        rangeStarts[write] = curStart;
        rangeEnds[write] = curEnd;
        write++;
        curStart = s;
        curEnd = e;
    }
}

// Don't forget the last range!
rangeStarts[write] = curStart;
rangeEnds[write] = curEnd;
write++;

// Sum the lengths
long total = 0;
for (int k = 0; k < write; k++) {
    total += (rangeEnds[k] - rangeStarts[k] + 1);
}

Why "curEnd + 1"?

The condition s <= curEnd + 1 (not just s <= curEnd) handles adjacent ranges. If one range ends at 5 and the next starts at 6, there's no gap between them, so they should merge into one continuous range. If we used s <= curEnd, ranges [3-5] and [6-10] would stay separate even though they represent consecutive IDs.

Time Complexity

Sorting: O(n log n). Merge pass: O(n). Sum pass: O(k) where k is the number of merged ranges. Total: O(n log n), dominated by the sort.

Lessons Learned

The best algorithm isn't always the fastest code. O(n × m) with primitive arrays beat O(n log n + n log k) with object overhead. Constant factors matter, especially when your \"constant\" involves five pointer dereferences.

Know your runtime. Java's JIT compilation means cold starts are slow and warm runs are fast. If you're benchmarking Java without warmup, you're measuring the JIT compiler, not your code.

Cache locality beats big-O. Sequential memory access through primitive arrays is incredibly fast on modern CPUs. Random access through object references is slow, even if you're doing \"fewer\" operations.

Sorting is non-negotiable for interval merging. The merge algorithm assumes left-to-right processing. Skip the sort and you'll get wrong answers on any input where ranges aren't already ordered.

On to Day 6.