Day 5 felt like running a little data pipeline: we ingest ranges, normalize them, and answer two slightly different queries.
Part 1 – Checking the available IDs
The database lists “fresh” ID ranges followed by a blank line and then the list of available items we need to classify. My approach:
- Parse the ranges and IDs.
- Sort and merge overlapping or adjacent ranges so we end up with disjoint intervals.
- For each ID, run a binary search to see whether it lands inside any merged interval.
Complexity: Merging ranges costs O(R log R) where R is the number of range lines. Each ID lookup is O(log R), so the total runtime is O(R log R + I log R); memory stays O(R) for the merged intervals.
1const fs = require('fs');
2const path = require('path');
3
4const inputPath = process.argv[2] ?? path.join(__dirname, 'input.txt');
5
6function parseInput(filePath) {
7 const raw = fs.readFileSync(filePath, 'utf8');
8 const [rangesSection, idsSection] = raw.split(/\r?\n\r?\n/);
9
10 const ranges = rangesSection
11 .trim()
12 .split(/\r?\n/)
13 .filter((line) => line.trim().length > 0)
14 .map((line) => {
15 const [startStr, endStr] = line.split('-');
16 if (!startStr || !endStr) {
17 throw new Error(`Invalid range line: ${line}`);
18 }
19 const start = Number(startStr);
20 const end = Number(endStr);
21 if (Number.isNaN(start) || Number.isNaN(end)) {
22 throw new Error(`Invalid number in range: ${line}`);
23 }
24 return { start, end };
25 });
26
27 const ids = idsSection
28 .trim()
29 .split(/\r?\n/)
30 .filter((line) => line.trim().length > 0)
31 .map((line) => Number(line.trim()));
32
33 return { ranges, ids };
34}
35
36function countFreshIds(ranges, ids) {
37 const normalized = ranges
38 .map((range) => (range.start <= range.end ? range : { start: range.end, end: range.start }))
39 .sort((a, b) => a.start - b.start);
40
41 let merged = [];
42 for (const range of normalized) {
43 if (merged.length === 0 || range.start > merged[merged.length - 1].end + 1) {
44 merged.push({ ...range });
45 } else {
46 merged[merged.length - 1].end = Math.max(merged[merged.length - 1].end, range.end);
47 }
48 }
49
50 return ids.reduce((count, id) => {
51 if (Number.isNaN(id)) {
52 return count;
53 }
54
55 let left = 0;
56 let right = merged.length - 1;
57 while (left <= right) {
58 const mid = Math.floor((left + right) / 2);
59 const range = merged[mid];
60 if (id < range.start) {
61 right = mid - 1;
62 } else if (id > range.end) {
63 left = mid + 1;
64 } else {
65 return count + 1;
66 }
67 }
68
69 return count;
70 }, 0);
71}
72
73function main() {
74 if (!fs.existsSync(inputPath)) {
75 console.error(`Input file not found: ${inputPath}`);
76 process.exitCode = 1;
77 return;
78 }
79
80 const { ranges, ids } = parseInput(inputPath);
81 if (ranges.length === 0 || ids.length === 0) {
82 console.log('0');
83 return;
84 }
85
86 const result = countFreshIds(ranges, ids);
87 console.log(result.toString());
88}
89
90main();
Part 2 – Counting every fresh ID
Now the available ID list is irrelevant—we just need the size of the union of the ranges themselves. The solution reuses the same merge logic but instead of querying IDs, it sums the inclusive length of each merged interval. Because the range values can be huge, everything runs in BigInt to avoid overflow.
Complexity: Parsing plus merging still costs O(R log R), and summing the merged intervals is O(R) time with O(R) memory.
Why it works well
- Both parts share the same normalized view of the ranges, so the second script is basically “merge once, sum once”.
- Binary search keeps the first part fast even when the list of available IDs is large.
- Using
BigIntin Part 2 future-proofs the code against absurd range sizes.
With the inventory reports reconciled, the kitchen can finally stop bugging me about which ingredients are fresh.
1const fs = require('fs');
2const path = require('path');
3
4const inputPath = process.argv[2] ?? path.join(__dirname, 'input.txt');
5
6function parseRanges(filePath) {
7 const raw = fs.readFileSync(filePath, 'utf8');
8 const [rangesSection] = raw.split(/\r?\n\r?\n/);
9 if (!rangesSection) {
10 return [];
11 }
12
13 return rangesSection
14 .split(/\r?\n/)
15 .map((line) => line.trim())
16 .filter((line) => line.length > 0)
17 .map((line) => {
18 const [startStr, endStr] = line.split('-');
19 if (!startStr || !endStr) {
20 throw new Error(`Invalid range line: ${line}`);
21 }
22 const start = BigInt(startStr);
23 const end = BigInt(endStr);
24 if (start > end) {
25 throw new Error(`Range start greater than end: ${line}`);
26 }
27 return { start, end };
28 });
29}
30
31function mergeRanges(ranges) {
32 if (ranges.length === 0) {
33 return [];
34 }
35 const sorted = ranges
36 .map((range) => (range.start <= range.end ? range : { start: range.end, end: range.start }))
37 .sort((a, b) => (a.start < b.start ? -1 : a.start > b.start ? 1 : 0));
38
39 const merged = [sorted[0]];
40 for (let i = 1; i < sorted.length; i += 1) {
41 const current = sorted[i];
42 const last = merged[merged.length - 1];
43 if (current.start <= last.end + 1n) {
44 last.end = last.end > current.end ? last.end : current.end;
45 } else {
46 merged.push({ ...current });
47 }
48 }
49 return merged;
50}
51
52function countFreshIds(ranges) {
53 const merged = mergeRanges(ranges);
54 return merged.reduce((sum, range) => sum + (range.end - range.start + 1n), 0n);
55}
56
57function main() {
58 if (!fs.existsSync(inputPath)) {
59 console.error(`Input file not found: ${inputPath}`);
60 process.exitCode = 1;
61 return;
62 }
63
64 const ranges = parseRanges(inputPath);
65 if (ranges.length === 0) {
66 console.log('0');
67 return;
68 }
69
70 const result = countFreshIds(ranges);
71 console.log(result.toString());
72}
73
74main();