Day 2 was all about spotting playful ID patterns inside huge numerical ranges. Here’s how both parts came together.
Input parsing shared by both parts
The puzzle input is one comma-separated line of inclusive ranges (start-end). I parse everything as BigInt so that the gigantic IDs stay precise. After that, each part does its own math on top of the same parsed data.
Part 1 – Double-half IDs
Condition. An ID is invalid if it is exactly two copies of some digit string (e.g., 64 64). If the repeated block has length h, then the ID equals pattern * 10^h + pattern.
Approach. For every range I loop over all feasible h (up to half the digit count of the range’s end). For each h:
- The pattern must be between
10^{h-1}and10^h - 1. - The ID multiplier is
10^h + 1. Valid patterns are those wherestart <= multiplier * pattern <= end. - Because the multiplier is constant, I can intersect
[start/multiplier, end/multiplier]with the valid pattern bounds and use arithmetic-series sums to add up the corresponding IDs.
The final sum is just the accumulation of all these chunks across every range.
Complexity. Let R be the number of ranges and D the maximum digit count of any upper bound. The number of candidate half-lengths is O(D), and each is processed with O(1) arithmetic. So the runtime is roughly O(R * D) and memory is O(1) besides the parsed data.
1const fs = require('fs');
2const path = require('path');
3
4const inputPath = process.argv[2] ?? path.join(__dirname, 'input.txt');
5
6function readRanges(filePath) {
7 const raw = fs.readFileSync(filePath, 'utf8').trim();
8 if (!raw) {
9 return [];
10 }
11
12 return raw
13 .split(',')
14 .map((chunk) => chunk.trim())
15 .filter((chunk) => chunk.length > 0)
16 .map((range) => {
17 const [startStr, endStr] = range.split('-');
18 if (!startStr || !endStr) {
19 throw new Error(`Invalid range: ${range}`);
20 }
21 const start = BigInt(startStr);
22 const end = BigInt(endStr);
23 if (start > end) {
24 throw new Error(`Range start greater than end: ${range}`);
25 }
26 return { start, end };
27 });
28}
29
30function pow10(exp) {
31 let result = 1n;
32 for (let i = 0; i < exp; i += 1) {
33 result *= 10n;
34 }
35 return result;
36}
37
38function ceilDiv(a, b) {
39 return (a + b - 1n) / b;
40}
41
42function sumRepeatedHalfNumbers(start, end) {
43 let total = 0n;
44 const maxDigits = end.toString().length;
45 const maxHalf = Math.floor(maxDigits / 2);
46
47 for (let halfLen = 1; halfLen <= maxHalf; halfLen += 1) {
48 const minHalf = pow10(halfLen - 1);
49 const maxHalfValue = pow10(halfLen) - 1n;
50 const multiplier = pow10(halfLen) + 1n;
51
52 let first = ceilDiv(start, multiplier);
53 if (first < minHalf) {
54 first = minHalf;
55 }
56
57 let last = end / multiplier;
58 if (last > maxHalfValue) {
59 last = maxHalfValue;
60 }
61
62 if (first > last) {
63 continue;
64 }
65
66 const count = last - first + 1n;
67 const sumHalves = (first + last) * count / 2n;
68 total += sumHalves * multiplier;
69 }
70
71 return total;
72}
73
74function solve(ranges) {
75 return ranges.reduce((acc, range) => acc + sumRepeatedHalfNumbers(range.start, range.end), 0n);
76}
77
78function main() {
79 if (!fs.existsSync(inputPath)) {
80 console.error(`Input file not found: ${inputPath}`);
81 process.exitCode = 1;
82 return;
83 }
84
85 const ranges = readRanges(inputPath);
86 if (ranges.length === 0) {
87 console.log('0');
88 return;
89 }
90
91 const result = solve(ranges);
92 console.log(result.toString());
93}
94
95main();
Part 2 – Any repeated block (length ≥ 1)
Condition. IDs are invalid if they are made of some pattern repeated two or more times (e.g., 123123123). These are numbers of the form pattern * (10^{k*h-1} + ... + 1) where k is the repeat count.
Approach. Instead of checking every ID, I enumerated pattern lengths (h) and repeat counts (k). The multiplier for a given (h, k) is Σ_{i=0}^{k-1} 10^{i*h}. For every range I intersect the pattern bounds with [start/multiplier, end/multiplier] to find all candidate patterns.
However, many IDs are representable with smaller periods, so I apply inclusion–exclusion: for each (h, k) I subtract contributions already accounted for by its proper divisors. Tracking partial sums in a map ensures every ID is counted exactly once.
Complexity. Enumerating base lengths and repeat counts still scales with O(R * D^2) in the worst case because there can be O(D) repeat counts per base length. The inclusion–exclusion bookkeeping adds a constant factor. Memory usage is O(D^2) for the memoized contributions.
1const fs = require('fs');
2const path = require('path');
3
4const inputPath = process.argv[2] ?? path.join(__dirname, 'input.txt');
5
6function readRanges(filePath) {
7 const raw = fs.readFileSync(filePath, 'utf8').trim();
8 if (!raw) {
9 return [];
10 }
11
12 return raw
13 .split(',')
14 .map((chunk) => chunk.trim())
15 .filter((chunk) => chunk.length > 0)
16 .map((range) => {
17 const [startStr, endStr] = range.split('-');
18 if (!startStr || !endStr) {
19 throw new Error(`Invalid range: ${range}`);
20 }
21 const start = BigInt(startStr);
22 const end = BigInt(endStr);
23 if (start > end) {
24 throw new Error(`Range start greater than end: ${range}`);
25 }
26 return { start, end };
27 });
28}
29
30const pow10Cache = new Map([[0, 1n]]);
31
32function pow10(exp) {
33 if (pow10Cache.has(exp)) {
34 return pow10Cache.get(exp);
35 }
36 const value = pow10(exp - 1) * 10n;
37 pow10Cache.set(exp, value);
38 return value;
39}
40
41function ceilDiv(a, b) {
42 if (a >= 0n) {
43 return (a + b - 1n) / b;
44 }
45 return a / b;
46}
47
48function sumArithmetic(first, last) {
49 const count = last - first + 1n;
50 return (first + last) * count / 2n;
51}
52
53function getProperDivisors(n) {
54 const divisors = [];
55 for (let d = 1; d * d <= n; d += 1) {
56 if (n % d !== 0) {
57 continue;
58 }
59 if (d !== n) {
60 divisors.push(d);
61 }
62 const other = n / d;
63 if (other !== d && other !== n) {
64 divisors.push(other);
65 }
66 }
67 return divisors;
68}
69
70function sumInvalidInRange(start, end) {
71 if (start > end) {
72 return 0n;
73 }
74
75 const primitiveMap = new Map();
76 const maxDigits = end.toString().length;
77 const maxBaseLen = Math.floor(maxDigits / 2);
78 let total = 0n;
79
80 for (let baseLen = 1; baseLen <= maxBaseLen; baseLen += 1) {
81 const maxRep = Math.floor(maxDigits / baseLen);
82 if (maxRep < 2) {
83 continue;
84 }
85
86 const minPattern = pow10(baseLen - 1);
87 const maxPattern = pow10(baseLen) - 1n;
88 const powStep = pow10(baseLen);
89
90 const multipliers = new Array(maxRep + 1).fill(0n);
91 let multiplier = 1n;
92 let power = 1n;
93 multipliers[1] = 1n;
94 for (let rep = 2; rep <= maxRep; rep += 1) {
95 power *= powStep;
96 multiplier += power;
97 multipliers[rep] = multiplier;
98 }
99
100 const divisors = getProperDivisors(baseLen);
101
102 for (let repCount = 2; repCount <= maxRep; repCount += 1) {
103 const multi = multipliers[repCount];
104 if (!multi) {
105 primitiveMap.set(`${baseLen}|${repCount}`, 0n);
106 continue;
107 }
108
109 let first = ceilDiv(start, multi);
110 if (first < minPattern) {
111 first = minPattern;
112 }
113
114 let last = end / multi;
115 if (last > maxPattern) {
116 last = maxPattern;
117 }
118
119 if (first > last) {
120 primitiveMap.set(`${baseLen}|${repCount}`, 0n);
121 continue;
122 }
123
124 let sumAll = sumArithmetic(first, last) * multi;
125
126 for (const divisor of divisors) {
127 const factor = baseLen / divisor;
128 if (factor * divisor !== baseLen) {
129 continue;
130 }
131 const relatedRep = repCount * factor;
132 const subtract = primitiveMap.get(`${divisor}|${relatedRep}`) ?? 0n;
133 sumAll -= subtract;
134 }
135
136 primitiveMap.set(`${baseLen}|${repCount}`, sumAll);
137 total += sumAll;
138 }
139 }
140
141 return total;
142}
143
144function solve(ranges) {
145 return ranges.reduce((acc, range) => acc + sumInvalidInRange(range.start, range.end), 0n);
146}
147
148function main() {
149 if (!fs.existsSync(inputPath)) {
150 console.error(`Input file not found: ${inputPath}`);
151 process.exitCode = 1;
152 return;
153 }
154
155 const ranges = readRanges(inputPath);
156 if (ranges.length === 0) {
157 console.log('0');
158 return;
159 }
160
161 const result = solve(ranges);
162 console.log(result.toString());
163}
164
165main();
Takeaways
- Staying in the arithmetic domain (no brute-force per ID) is the only way to handle the enormous ranges.
- BigInt arithmetic makes these formulas safe and keeps the implementation close to the math definitions.
- Inclusion–exclusion is the trick that unlocks Part 2; otherwise numbers with smaller periods would be double-counted.
With both scripts (part1 and part2) ready, it’s easy to run either variant and catch every mischievous pattern the young Elf left behind. On to the next floor!