Problem

Read it here

tl;dr

You have a database with two sections:

1. Fresh ID ranges (e.g., 3-5 means IDs 3, 4, 5 are fresh)
2. Available ingredient IDs to check

Ranges can overlap. An ID is fresh if it falls into any range.

Example input:

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

1
5
8
11
17
32

---

Part 1

Count how many available IDs are fresh.

ID	Fresh?	Reason
1	No	Not in any range
5	Yes	In range 3-5
8	No	Not in any range
11	Yes	In range 10-14
17	Yes	In ranges 16-20 and 12-18
32	No	Not in any range

Answer: 3

Key insight: For each available ID, check if it falls within any range. Could merge overlapping ranges first for efficiency, or just brute force check each ID against all ranges.

---

Part 2

Count the total number of unique fresh IDs across all ranges (ignore the available IDs section).

Range	IDs covered
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

Merged unique IDs: 3, 4, 5, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Answer: 14

Key insight: Classic interval merging — sort ranges by start, greedily merge overlapping/adjacent ones, then sum (end - start + 1) for each merged range.

---

My Solution (Handcrafted)

The Approach: Merge As You Go

My approach was to maintain a sorted list of merged ranges as I process each input range. Instead of collecting all ranges first and then merging, I merge incrementally — each new range either:

1. Slots in as a new non-overlapping range
2. Merges with one or more existing ranges

The Merge Logic

For each incoming range, I check four overlap cases:

// 4 cases when we can merge the new range with the current range
// 1. the new range entirely contains the current range
// 2. the current range entirely contains the new range
// 3. the new range overlaps from the left (covers 2nd half)
// 4. the new range overlaps from the right (covers 1st half)
if (start <= current_range[0] && end >= current_range[1])
    || (start >= current_range[0] && end <= current_range[1])
    || (start >= current_range[0] && start <= current_range[1])
    || (end >= current_range[0] && end <= current_range[1])
{
    Self::merge_ranges(&mut fresh_ingredient_ids, i, start, end);
    inserted = true;
    break;
}

The Cascading Merge Problem

Here’s where it gets tricky. When you merge a new range with an existing one, the result might now overlap with other ranges. My merge_ranges function handles this by scanning both forward and backward:

fn merge_ranges(
    ranges: &mut Vec<[u64; 2]>,
    update_index: usize,
    update_start: u64,
    update_end: u64,
) {
    let mut popping_ranges = Vec::new();

    let mut next_start = min(update_start, ranges[update_index][0]);
    let mut next_end = max(update_end, ranges[update_index][1]);

    // going forward - check if we now overlap with later ranges
    if update_index < ranges.len() - 1 {
        for i in update_index + 1..ranges.len() {
            let next_range = ranges[i];
            if next_range[0] <= update_end {
                popping_ranges.push(i);
                next_end = next_range[1];
            } else {
                break;
            }
        }
    }

    // going backward - check if we now overlap with earlier ranges
    // ... similar logic ...

    // update and remove absorbed ranges
    ranges[update_index] = [next_start, next_end];
    for popping_range in popping_ranges {
        ranges.remove(popping_range as usize);
    }
}

Part 1 & Part 2

Both parts share the same merging logic. The only difference is the final step:

• Part 1: Loop through available IDs, check if each falls within any merged range
• Part 2: Sum up (end - start + 1) for each merged range

// Part 2 final calculation
let mut total_fresh_ingredient_count = 0;
for fresh_ingredient_range in fresh_ingredient_ids.iter() {
    total_fresh_ingredient_count +=
        fresh_ingredient_range[1] - fresh_ingredient_range[0] + 1;
}

---

Gemini’s Solution

Part 1: Brute Force

Gemini went with the simplest possible approach — no merging at all:

pub fn solve_1(filename: &str) -> usize {
    let (ranges, ids) = Self::read_and_parse(filename);
    let mut fresh_count = 0;

    for id in ids {
        // Check if this ID falls into ANY of the ranges
        for &(start, end) in &ranges {
            if id >= start && id <= end {
                fresh_count += 1;
                break; // It's fresh, no need to check other ranges
            }
        }
    }

    fresh_count
}

For each available ID, just loop through all ranges and check. O(IDs × ranges) but perfectly fine for this input size.

Part 2: The Textbook Interval Merge

This is where Gemini’s solution really shines. Instead of my complicated merge-as-you-go approach, it uses the classic interval merging algorithm:

1. Sort all ranges by start
2. Single pass: extend current range or start a new one

pub fn solve_2(filename: &str) -> u64 {
    let (mut ranges, _) = Self::read_and_parse(filename);

    // Sort ranges by start point to enable linear merging
    ranges.sort_by_key(|k| k.0);

    let mut total_fresh_ids = 0;
    let mut current_start = ranges[0].0;
    let mut current_end = ranges[0].1;

    for &(next_start, next_end) in ranges.iter().skip(1) {
        // If the next range starts inside or immediately after, merge
        if next_start <= current_end + 1 {
            current_end = max(current_end, next_end);
        } else {
            // No overlap: finalize current range and start new one
            total_fresh_ids += current_end - current_start + 1;
            current_start = next_start;
            current_end = next_end;
        }
    }

    // Don't forget the final range
    total_fresh_ids += current_end - current_start + 1;
    total_fresh_ids
}

Clean. Simple. 10 lines of actual logic vs my 60+ lines of merge handling.

---

Comparison

Aspect	My Solution	Gemini’s Solution
Part 1	Merge first, then check IDs	Brute force check all ranges
Part 2	Merge-as-you-go (incremental)	Sort first, then single-pass
Complexity	O(n²) worst case for merging	O(n log n) for sort + O(n) merge
Code length	~100 lines with helper function	~30 lines total
Readability	Complex, hard to verify correctness	Textbook algorithm, easy to grok

---

Reflection

I overcomplicated this one.

My approach tried to be clever by maintaining a sorted merged list incrementally. The idea was to avoid a final sort step. But this led to complex merge logic with forward/backward scanning and cascading merges. It works, but it’s harder to reason about and debug.

Gemini’s approach is the textbook solution: sort first, merge second. The sort costs O(n log n), but the merge becomes a trivial single pass. Sometimes the “obvious” algorithm is obvious for a reason — it’s simple, correct, and efficient enough.

Part 1 difference: I pre-merged ranges for Part 1 even though it wasn’t strictly necessary. Gemini just brute-forced it. For the given input size, brute force was fine and required zero extra code. My pre-merging was premature optimization.

The lesson: Don’t try to be clever when the straightforward solution works. Sort-then-merge is a well-known pattern for interval problems. My incremental approach reinvented the wheel — and made it slightly square-shaped.

Time spent: ~25 minutes (mostly debugging the cascade merge logic)