advent of code 2025 in ts and nix
dunkirk.sh
1const file = await Bun.file("../../shared/10/input.txt").text();
2
3interface Machine {
4 target: boolean[];
5 buttons: number[][];
6 joltages: number[];
7}
8
9// Test with examples first
10const testInput = `[.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}
11[...#.] (0,2,3,4) (2,3) (0,4) (0,1,2) (1,2,3,4) {7,5,12,7,2}
12[.###.#] (0,1,2,3,4) (0,3,4) (0,1,2,4,5) (1,2) {10,11,11,5,10,5}`;
13
14function parseMachines(input: string): Machine[] {
15 return input
16 .trim()
17 .split("\n")
18 .map((line) => {
19 const lightsMatch = line.match(/\[([.#]+)\]/);
20 const target = lightsMatch![1].split("").map((c) => c === "#");
21
22 const buttonsMatch = line.matchAll(/\(([0-9,]+)\)/g);
23 const buttons: number[][] = [];
24 for (const match of buttonsMatch) {
25 const indices = match[1].split(",").map(Number);
26 buttons.push(indices);
27 }
28
29 const joltagesMatch = line.match(/\{([0-9,]+)\}/);
30 const joltages = joltagesMatch
31 ? joltagesMatch[1].split(",").map(Number)
32 : [];
33
34 return { target, buttons, joltages };
35 });
36}
37
38function solveMachine(machine: Machine): number {
39 const n = machine.target.length;
40 const m = machine.buttons.length;
41
42 // Build augmented matrix [A | b]
43 const matrix: number[][] = [];
44 for (let i = 0; i < n; i++) {
45 const row: number[] = [];
46 for (let j = 0; j < m; j++) {
47 row.push(machine.buttons[j].includes(i) ? 1 : 0);
48 }
49 row.push(machine.target[i] ? 1 : 0);
50 matrix.push(row);
51 }
52
53 // Gaussian elimination
54 const pivotCols: number[] = [];
55
56 for (let col = 0; col < m; col++) {
57 let pivotRow = -1;
58 for (let row = pivotCols.length; row < n; row++) {
59 if (matrix[row][col] === 1) {
60 pivotRow = row;
61 break;
62 }
63 }
64
65 if (pivotRow === -1) continue;
66
67 const targetRow = pivotCols.length;
68 if (pivotRow !== targetRow) {
69 [matrix[pivotRow], matrix[targetRow]] = [
70 matrix[targetRow],
71 matrix[pivotRow],
72 ];
73 }
74
75 pivotCols.push(col);
76
77 for (let row = 0; row < n; row++) {
78 if (row !== targetRow && matrix[row][col] === 1) {
79 for (let c = 0; c <= m; c++) {
80 matrix[row][c] ^= matrix[targetRow][c];
81 }
82 }
83 }
84 }
85
86 // Check for inconsistency
87 for (let row = pivotCols.length; row < n; row++) {
88 if (matrix[row][m] === 1) {
89 return Infinity;
90 }
91 }
92
93 // Identify free variables
94 const isPivot = new Array(m).fill(false);
95 pivotCols.forEach((col) => (isPivot[col] = true));
96 const freeVars: number[] = [];
97 for (let j = 0; j < m; j++) {
98 if (!isPivot[j]) freeVars.push(j);
99 }
100
101 // Try all combinations of free variables to find minimum
102 let minPresses = Infinity;
103 let bestSolution: number[] = [];
104
105 const numCombinations = 1 << freeVars.length;
106 for (let combo = 0; combo < numCombinations; combo++) {
107 const solution: number[] = new Array(m).fill(0);
108
109 // Set free variables according to combo
110 for (let i = 0; i < freeVars.length; i++) {
111 solution[freeVars[i]] = (combo >> i) & 1;
112 }
113
114 // Back-substitution for pivot variables
115 for (let i = pivotCols.length - 1; i >= 0; i--) {
116 const col = pivotCols[i];
117 solution[col] = matrix[i][m];
118
119 for (let j = col + 1; j < m; j++) {
120 if (matrix[i][j] === 1) {
121 solution[col] ^= solution[j];
122 }
123 }
124 }
125
126 const presses = solution.reduce((sum, x) => sum + x, 0);
127 if (presses < minPresses) {
128 minPresses = presses;
129 bestSolution = solution;
130 }
131 }
132
133 return minPresses;
134}
135
136// Test with examples
137const testMachines = parseMachines(testInput);
138let testTotal = 0;
139testMachines.forEach((machine, idx) => {
140 const presses = solveMachine(machine);
141 testTotal += presses;
142});
143console.log("Part 1 test total:", testTotal, "(expected: 7)");
144
145// Now solve actual input
146const machines = parseMachines(file);
147let totalPresses = 0;
148machines.forEach((machine, idx) => {
149 const presses = solveMachine(machine);
150 if (presses === Infinity) {
151 console.log(`Machine ${idx} has no solution!`);
152 }
153 totalPresses += presses;
154});
155
156console.log("\npart 1:", totalPresses);
157
158// Part 2: Joltage configuration
159
160function solveMachinePart2(machine: Machine): number {
161 const n = machine.joltages.length;
162 const m = machine.buttons.length;
163 const target = machine.joltages;
164
165 // Build coefficient matrix A where A[i][j] = 1 if button j affects counter i
166 const A: number[][] = [];
167 for (let i = 0; i < n; i++) {
168 const row: number[] = [];
169 for (let j = 0; j < m; j++) {
170 row.push(machine.buttons[j].includes(i) ? 1 : 0);
171 }
172 A.push(row);
173 } const solution = new Array(m).fill(0);
174 const current = new Array(n).fill(0);
175
176 // Simple greedy: for each counter that needs more, press any button that affects it
177 // Better approach: try to find the exact solution using integer linear programming
178
179 // For small cases, we can use Gaussian elimination to find one solution,
180 // then check if it's all non-negative integers
181 // Otherwise, use a more sophisticated approach
182
183 // Build augmented matrix [A | b]
184 const matrix: number[][] = [];
185 for (let i = 0; i < n; i++) {
186 matrix.push([...A[i], target[i]]);
187 }
188
189 // Gaussian elimination
190 const pivotCols: number[] = [];
191 for (let col = 0; col < m; col++) {
192 let pivotRow = -1;
193 for (let row = pivotCols.length; row < n; row++) {
194 if (matrix[row][col] !== 0) {
195 pivotRow = row;
196 break;
197 }
198 }
199
200 if (pivotRow === -1) continue;
201
202 const targetRow = pivotCols.length;
203 if (pivotRow !== targetRow) {
204 [matrix[pivotRow], matrix[targetRow]] = [
205 matrix[targetRow],
206 matrix[pivotRow],
207 ];
208 }
209
210 pivotCols.push(col);
211
212 // Scale row so pivot is 1
213 const pivot = matrix[targetRow][col];
214 for (let c = 0; c <= m; c++) {
215 matrix[targetRow][c] /= pivot;
216 }
217
218 // Eliminate column in other rows
219 for (let row = 0; row < n; row++) {
220 if (row !== targetRow && matrix[row][col] !== 0) {
221 const factor = matrix[row][col];
222 for (let c = 0; c <= m; c++) {
223 matrix[row][c] -= factor * matrix[targetRow][c];
224 }
225 }
226 }
227 }
228
229 // Check for inconsistency
230 for (let row = pivotCols.length; row < n; row++) {
231 if (Math.abs(matrix[row][m]) > 1e-9) {
232 return Infinity;
233 }
234 }
235
236 // Identify free variables
237 const isPivot = new Array(m).fill(false);
238 pivotCols.forEach((col) => (isPivot[col] = true));
239 const freeVars: number[] = [];
240 for (let j = 0; j < m; j++) {
241 if (!isPivot[j]) freeVars.push(j);
242 }
243
244 // Search all combinations of free variables to find minimum
245 if (freeVars.length > 15) {
246 return Infinity;
247 return Infinity;
248 }
249
250 let minPresses = Infinity;
251 let bestSolution: number[] = [];
252
253 // Estimate upper bound for free variables based on target values
254 const maxTarget = Math.max(...target);
255 const maxFreeValue = Math.min(maxTarget * 2, 200);
256
257 function searchFreeVars(idx: number, currentSol: number[]) {
258 if (idx === freeVars.length) {
259 // Back-substitute to get pivot variables
260 const sol = [...currentSol];
261 let valid = true;
262 for (let i = pivotCols.length - 1; i >= 0; i--) {
263 const col = pivotCols[i];
264 let val = matrix[i][m];
265 for (let j = col + 1; j < m; j++) {
266 val -= matrix[i][j] * sol[j];
267 }
268 sol[col] = val;
269
270 // Check if it's a non-negative integer
271 if (val < -1e-9 || Math.abs(val - Math.round(val)) > 1e-9) {
272 valid = false;
273 break;
274 }
275 }
276
277 if (valid) {
278 const intSol = sol.map((x) => Math.round(Math.max(0, x)));
279 const presses = intSol.reduce((sum, x) => sum + x, 0);
280 if (presses < minPresses) {
281 minPresses = presses;
282 bestSolution = intSol;
283 }
284 }
285 return;
286 }
287
288 // Try different values for this free variable
289 for (let val = 0; val <= maxFreeValue; val++) {
290 currentSol[freeVars[idx]] = val;
291 searchFreeVars(idx + 1, currentSol);
292 }
293 }
294
295 searchFreeVars(0, new Array(m).fill(0));
296
297 return minPresses;
298}
299
300// Test Part 2 examples
301const testInput2 = `[.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}
302[...#.] (0,2,3,4) (2,3) (0,4) (0,1,2) (1,2,3,4) {7,5,12,7,2}
303[.###.#] (0,1,2,3,4) (0,3,4) (0,1,2,4,5) (1,2) {10,11,11,5,10,5}`;
304
305const testMachines2 = parseMachines(testInput2);
306let testTotal2 = 0;
307testMachines2.forEach((machine, idx) => {
308 const presses = solveMachinePart2(machine);
309 testTotal2 += presses;
310});
311console.log("Part 2 test total:", testTotal2, "(expected: 33)");
312
313// Solve Part 2 for actual input
314let totalPresses2 = 0;
315machines.forEach((machine, idx) => {
316 const presses = solveMachinePart2(machine);
317 if (presses === Infinity) {
318 console.log(`Machine ${idx} has no solution!`);
319 }
320 totalPresses2 += presses;
321});
322
323console.log("\npart 2:", totalPresses2);