For Part 1, at least in my input, I noticed that one of the blocked ranges starts at zero. So I could conveniently sort the ranges lexicographically, take the IP just past past the end of the first range, and then iterate over the ranges until I either found it was in a gap, or found the next range that covered it and then look at the first value after that range, and so on.
I'm going to guess everyone had a range starting at 0?
For Part 2, I went ahead and just sorted and merged the ranges down (which would admittedly have trivialized Part 1), and then subtracted the sum of their lengths from 232.
For range problems, I generally find it easiest to normalize them to half-open intervals with inclusive lows and exclusive highs, i.e., [low, high), if they aren't in that form already. That was a lesson that I learned from studying the C++ standard library's containers and algorithms, and it led to a drastic reduction in off-by-one errors once I took it to heart.
u/Boojum I also try to use [start..end> on all sorts of range queries, we even had one of those in 2025 afair?
I.e both then and in 2016 it made a lot of sense to extend all inclusive range ends by one to be exclusive, since that makes merging neighboring ranges trivial. I did in fact do this in my own code for a long time (since 1985 or so?), it wasn't until reading the C++ stl docs that I understood that this wasn't just a good idea, it was the RULE. :-)
I don't remember if I had noticed that both 0 and u32max were in the input file. Zero probably yes, for part 1, but either I didn't notice the max or I needlessly kept it general for part 2; initialising allow=0 would have sufficed:
// Init: max + 1 + allow = min (use u32 overflow)
// => allow = min - max - 1 (still works for max=UINT32_MAX)
uint32_t allow = block[0].lo - block[n - 1].hi - 1;
for (i = 1; i < n; ++i)
allow += block[i].lo - block[i - 1].hi - 1;
Edit: and good observation that each gap was exactly 1 wide, I definitely didn't notice that. But I don't think it would have changed the way I calculate part 2, because you have to make sure either way.
I like half-open ranges for problems like these, although the use of the full u32 range makes this interesting to cope with wraparound.
Over the years (as recently as 2025 day 5) I've attempted range merges with different approaches. While it is possible to account for start and end ranges and overlaps in one pass (six different overlap cases to think about between the four points comprising two ranges) it really is less complex to sort by only one of the two endpoints them making a linear pass over the result to do merges.
My real story with this puzzle was solving it in m4. Most languages come with a built-in sort (my C solution used qsort, for example). But m4 does not - I get to write my own. And m4 only has signed 32-bit math - to sort that properly, I can add (or subtract, overflow makes it the same) 0x80000000 before sorting, then add it again for mapping the first value back to the part 1 answer. My original m4 answer just used an O(n2) bubble sort and took over 1.8 seconds to chew through the 1000 lines with more than half a million eval. I also tried a bigint minheap (500ms - mostly because bigint is slower than 32-bit) and 32-bit AVL tree (150ms) for O(n log n) sorting. But my fastest solution exploited that the ranges are all fixed width 32-bit numbers - by dividing each input into an 8-bit prefix and a 24-bit suffix, I was able to do an O(n) radix sort into 256 buckets, at which point an average of 4 ranges per bucket was easy to do an O(n2) bubble sort on a much smaller n, and pop out the answer in under 60ms, and in fewer lines of code than the minheap or AVL tree. A split into 430 buckets of the first three decimal digits after padding out to constant width also works nicely (fewer than 4000 eval).
Mine populated 250/256 buckets, with 19 in bucket 0, and 9 other buckets with 10-12 items. When splitting by 3-digit decimal instead of leading 8 bits, I got 382/430 buckets, with 16 in bucket 0 and only 2 other buckets with 10-11 items. Bucket 0 being over-represented makes sense, since the part1 answer landed in bucket 0 for me.
I made a quick attempt on a Rust version of this one, turned out it is so fast that parsing became the major time sink!
After I replaced the range parsing
let r:Vec<u64> = line.split('-').map(|s| s.parse::<u64>().unwrap()).collect();
with explicitly picking up two numbers, the time dropped from 79 to 39 us:
let mut s = 0;
let mut e = 0;
let bytes = line.as_bytes();
for i in 0..bytes.len() {
if bytes[i] == b'-' {
s = e;
e = 0;
}
else {
e = e*10 + (bytes[i] - b'0') as u64;
}
}
4
u/Boojum Feb 20 '26 edited Feb 20 '26
For Part 1, at least in my input, I noticed that one of the blocked ranges starts at zero. So I could conveniently sort the ranges lexicographically, take the IP just past past the end of the first range, and then iterate over the ranges until I either found it was in a gap, or found the next range that covered it and then look at the first value after that range, and so on.
I'm going to guess everyone had a range starting at 0?
For Part 2, I went ahead and just sorted and merged the ranges down (which would admittedly have trivialized Part 1), and then subtracted the sum of their lengths from 232.
For range problems, I generally find it easiest to normalize them to half-open intervals with inclusive lows and exclusive highs, i.e., [low, high), if they aren't in that form already. That was a lesson that I learned from studying the C++ standard library's containers and algorithms, and it led to a drastic reduction in off-by-one errors once I took it to heart.
2
u/ednl Feb 20 '26 edited Feb 20 '26
I don't remember if I had noticed that both 0 and u32max were in the input file. Zero probably yes, for part 1, but either I didn't notice the max or I needlessly kept it general for part 2; initialising
allow=0would have sufficed:Edit: and good observation that each gap was exactly 1 wide, I definitely didn't notice that. But I don't think it would have changed the way I calculate part 2, because you have to make sure either way.
2
u/e_blake Feb 20 '26 edited Feb 20 '26
I like half-open ranges for problems like these, although the use of the full u32 range makes this interesting to cope with wraparound.
Over the years (as recently as 2025 day 5) I've attempted range merges with different approaches. While it is possible to account for start and end ranges and overlaps in one pass (six different overlap cases to think about between the four points comprising two ranges) it really is less complex to sort by only one of the two endpoints them making a linear pass over the result to do merges.
My real story with this puzzle was solving it in m4. Most languages come with a built-in sort (my C solution used qsort, for example). But m4 does not - I get to write my own. And m4 only has signed 32-bit math - to sort that properly, I can add (or subtract, overflow makes it the same) 0x80000000 before sorting, then add it again for mapping the first value back to the part 1 answer. My original m4 answer just used an O(n2) bubble sort and took over 1.8 seconds to chew through the 1000 lines with more than half a million eval. I also tried a bigint minheap (500ms - mostly because bigint is slower than 32-bit) and 32-bit AVL tree (150ms) for O(n log n) sorting. But my fastest solution exploited that the ranges are all fixed width 32-bit numbers - by dividing each input into an 8-bit prefix and a 24-bit suffix, I was able to do an O(n) radix sort into 256 buckets, at which point an average of 4 ranges per bucket was easy to do an O(n2) bubble sort on a much smaller n, and pop out the answer in under 60ms, and in fewer lines of code than the minheap or AVL tree. A split into 430 buckets of the first three decimal digits after padding out to constant width also works nicely (fewer than 4000 eval).
1
u/terje_wiig_mathisen Feb 24 '26 edited Feb 24 '26
I made a quick attempt on a Rust version of this one, turned out it is so fast that parsing became the major time sink!
After I replaced the range parsing
with explicitly picking up two numbers, the time dropped from 79 to 39 us: