Advent of Code 2025 Day 5

01 · 02 · 03 · 04 · 05 · 06 · 07 · 08 · 09 · 10· 11 · 12

The day 5problem statement and test input are as follows:

[embed]Advent of Code As the forklifts break through the wall, the Elves are delighted to discover that there was a cafeteria on the other…adventofcode.com

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

1
5
8
11
17
32

The input consists of a list of ranges of IDs, and another list of IDs. The goal is to find how many IDs in the second list fall into any of the ranges in the first one. As we can see, the ranges can overlap (for example, IDs 16, 17 and 18 fall into two of the ranges). But we just need to know if an ID falls into some range.

For part one, I knew my solution wouldn’t be optimal, since I didn’t bother to take the overlap into account. I assumed part two would make me to do so anyway so I held off until then. For part one, I simply went over all the ranges for each ID until I found a range that the ID falls into.

bool falls_into_range(vector<pair<long, long>> &ranges, long id) {
  for (pair<long, long> range : ranges) {
    if (id >= range.first && id <= range.second) {
      return true;
    }
  }
  return false;
}

For part two, surely enough, we now have to count all the unique IDs that fall into all the ranges. Thus, I needed to take overlap into account. The initial quick solution, for the test input, could be to make an Boolean array of length 20, iterate over the IDs in each ranges, and set the elements at the corresponding index that matches the ID to true. Finally, count all the elements in the array that are true. However, the real input didn’t have nice small numbers. In fact, it had numbers in the trillions. Not feasible.

So I decided to make a new set of ranges by iterating over the initial ranges, and combining them if there is any overlap. There are a few different scenarios to handle every time I encounter a new range. The new range’s endpoints could:

• not fall anywhere in the existing ranges, thus we need add it as a new range in the set
• fall entirely within a range, thus we can safely ignore it
• have exactly one endpoint fall in an existing range, thus extending that existing range to the new endpoint (this could be on either side)
• have left and right endpoints fall in two different existing ranges, thus combining them both into one range

Using this, I built a new set of ranges with no overlap.

vector<pair<long, long>> new_ranges;
for (pair<long, long> range : initial_ranges) {
  int l = find_existing_range_index(ranges, range.first);
  int r = find_existing_range_index(ranges, range.second);
  // new range
  if (l == -1 && r == -1) {
    new_ranges.push_back({left, right}); // insert into new ranges
  }
  // range entirely contained within another
  else if (l == r) {
    continue; // ignore
  }
  // only right endpoint in an existing range
  else if (l == -1) {
    new_ranges[r] = { left, new_ranges[r].second }; // extend the range to the new left endpoint
  }
  // only left side in an existing range
  else if (r == -1) {
    new_ranges[l] = { new_ranges[l].first, right }; // extend the range to the new right endpoint
  }
  // left and right endpoint are within different ranges
  else {
    // combine the ranges
    new_ranges.push_back({new_ranges[l].first, new_ranges[r].second});
    if (l < r) {
      new_ranges.erase(new_ranges.begin() + r);
      new_ranges.erase(new_ranges.begin() + l);
    } else {
      new_ranges.erase(new_ranges.begin() + l);
      new_ranges.erase(new_ranges.begin() + r);
    }
  }
}

The only gotcha here was that I was going through the ranges top to bottom, and since the input isn’t sorted, I can encounter a range that falls entirely within another range that I haven’t encountered yet. A simple solution for this was to just iterate over the new set of ranges one more time to find any such ranges and remove them.

for (int i = 0; i < ranges.size(); i += 1) {
  pair<long, long> range = ranges[i];
  for (pair<long, long> range2 : ranges) {
    if (range.first > range2.first && range.second < range2.second) {
      ranges.erase(ranges.begin() + i); // yes I modified the array I was iterating over
      i -= 1;
    }
  }
}

The only thing left to do was to iterate over this new, much more concise set of ranges and count how many IDs fit in all of them. And thus, I had the solution.

Source code: https://github.com/kabbagepatch/AdventOfCode2025/tree/main/day05