advent of code 2025 in ts and nix
dunkirk.sh
1const scriptDir = import.meta.dir;
2const file = await Bun.file(`${scriptDir}/../../shared/09/input.txt`).text();
3
4// Parse tile coordinates
5const tiles = file
6 .trim()
7 .split("\n")
8 .map((line) => {
9 const [x, y] = line.split(",").map(Number);
10 return { x, y };
11 });
12
13// Find grid bounds
14const minX = Math.min(...tiles.map((t) => t.x));
15const maxX = Math.max(...tiles.map((t) => t.x));
16const minY = Math.min(...tiles.map((t) => t.y));
17const maxY = Math.max(...tiles.map((t) => t.y));
18
19// Calculate all possible rectangles and their areas
20// We'll pre-compute key milestones for the animation
21const milestones = [];
22let maxAreaSoFar = 0;
23let totalRectangles = 0;
24
25for (let i = 0; i < tiles.length; i++) {
26 for (let j = i + 1; j < tiles.length; j++) {
27 const t1 = tiles[i];
28 const t2 = tiles[j];
29
30 totalRectangles++;
31
32 // Calculate area (inclusive coordinates)
33 const width = Math.abs(t2.x - t1.x) + 1;
34 const height = Math.abs(t2.y - t1.y) + 1;
35 const area = width * height;
36
37 if (area > maxAreaSoFar) {
38 // Found a new maximum!
39 maxAreaSoFar = area;
40 milestones.push({
41 x1: Math.min(t1.x, t2.x),
42 y1: Math.min(t1.y, t2.y),
43 x2: Math.max(t1.x, t2.x),
44 y2: Math.max(t1.y, t2.y),
45 area,
46 tile1: i,
47 tile2: j,
48 isMax: true,
49 });
50 }
51 }
52}
53
54// Add some non-max rectangles for visualization variety
55// Sample rectangles at regular intervals to show the search process
56const samples = [];
57const sampleInterval = Math.floor(totalRectangles / 100); // Sample ~100 rectangles
58let sampleCounter = 0;
59
60for (let i = 0; i < tiles.length; i++) {
61 for (let j = i + 1; j < tiles.length; j++) {
62 sampleCounter++;
63 if (sampleCounter % sampleInterval === 0) {
64 const t1 = tiles[i];
65 const t2 = tiles[j];
66 const width = Math.abs(t2.x - t1.x) + 1;
67 const height = Math.abs(t2.y - t1.y) + 1;
68 const area = width * height;
69
70 if (area > 0) {
71 samples.push({
72 x1: Math.min(t1.x, t2.x),
73 y1: Math.min(t1.y, t2.y),
74 x2: Math.max(t1.x, t2.x),
75 y2: Math.max(t1.y, t2.y),
76 area,
77 tile1: i,
78 tile2: j,
79 isMax: false,
80 });
81 }
82 }
83 }
84}
85
86// Combine and sort by discovery order (tile1, then tile2)
87const allStages = [...samples, ...milestones].sort((a, b) => {
88 if (a.tile1 !== b.tile1) return a.tile1 - b.tile1;
89 return a.tile2 - b.tile2;
90});
91
92// Rebuild isMax flags after sorting
93let currentMax = 0;
94allStages.forEach((stage) => {
95 if (stage.area > currentMax) {
96 stage.isMax = true;
97 currentMax = stage.area;
98 } else {
99 stage.isMax = false;
100 }
101});
102
103// Part 2: Build compressed grid and flood fill
104function computePart2Data() {
105 const _minX = Math.min(...tiles.map((p) => p.x)) - 1;
106 const _minY = Math.min(...tiles.map((p) => p.y)) - 1;
107 const __points = tiles.map((p) => ({ x: p.x - _minX, y: p.y - _minY }));
108
109 const xs = __points
110 .map((p) => p.x)
111 .toSorted((a, b) => a - b)
112 .filter((_, i) => i % 2 === 0);
113 const ys = __points
114 .map((p) => p.y)
115 .toSorted((a, b) => a - b)
116 .filter((_, i) => i % 2 === 0);
117 const points = __points.map((p) => ({
118 x: 1 + xs.indexOf(p.x) * 2,
119 y: 1 + ys.indexOf(p.y) * 2,
120 }));
121
122 const grid: number[][] = [];
123 const width = Math.max(...points.map((p) => p.x)) + 1;
124 const height = Math.max(...points.map((p) => p.y)) + 1;
125
126 for (let y = 0; y <= height; y++) {
127 grid[y] = [];
128 for (let x = 0; x <= width; x++) {
129 grid[y][x] = 0;
130 }
131 }
132
133 // Mark red tiles and green connecting tiles
134 points.forEach((p, pIndex) => {
135 grid[p.y][p.x] = 1; // Red tile
136 const nextPoint = points[(pIndex + 1) % points.length];
137 const deltaX = Math.sign(nextPoint.x - p.x);
138 const deltaY = Math.sign(nextPoint.y - p.y);
139 if (deltaX !== 0) {
140 let currentX = p.x + deltaX;
141 while (currentX !== nextPoint.x) {
142 if (grid[p.y][currentX] === 0) {
143 grid[p.y][currentX] = 2; // Green tile
144 }
145 currentX += deltaX;
146 }
147 }
148 if (deltaY !== 0) {
149 let currentY = p.y + deltaY;
150 while (currentY !== nextPoint.y) {
151 if (grid[currentY][p.x] === 0) {
152 grid[currentY][p.x] = 2; // Green tile
153 }
154 currentY += deltaY;
155 }
156 }
157 });
158
159 // Flood fill from border
160 let open = [{ x: 0, y: 0 }];
161 const floodFill = (x: number, y: number) => {
162 if (x < 0 || x > width || y < 0 || y > height || grid[y][x] !== 0) {
163 return;
164 }
165 grid[y][x] = -1; // Outside
166 const add = (nx: number, ny: number) => {
167 if (
168 nx >= 0 &&
169 nx <= width &&
170 ny >= 0 &&
171 ny <= height &&
172 grid[ny][nx] === 0
173 ) {
174 open.push({ x: nx, y: ny });
175 }
176 };
177 add(x + 1, y);
178 add(x - 1, y);
179 add(x, y + 1);
180 add(x, y - 1);
181 };
182 while (open.length > 0) {
183 const point = open.pop()!;
184 floodFill(point.x, point.y);
185 }
186
187 const hasOnlyValidPoints = (pointA: any, pointB: any): boolean => {
188 for (
189 let y = Math.min(pointA.y, pointB.y);
190 y <= Math.max(pointA.y, pointB.y);
191 y++
192 ) {
193 for (
194 let x = Math.min(pointA.x, pointB.x);
195 x <= Math.max(pointA.x, pointB.x);
196 x++
197 ) {
198 if (grid[y][x] < 0) {
199 return false;
200 }
201 }
202 }
203 return true;
204 };
205
206 return { points, hasOnlyValidPoints };
207}
208
209const part2Data = computePart2Data();
210
211// Calculate Part 2 rectangles
212const part2Milestones = [];
213let part2MaxArea = 0;
214const part2Samples = [];
215let part2SampleCounter = 0;
216const part2SampleInterval = 100; // Sample less frequently since we check all pairs now
217
218for (let i = 0; i < tiles.length; i++) {
219 for (let j = i + 1; j < tiles.length; j++) {
220 const t1 = tiles[i];
221 const t2 = tiles[j];
222
223 const width = Math.abs(t2.x - t1.x) + 1;
224 const height = Math.abs(t2.y - t1.y) + 1;
225 const area = width * height;
226
227 // Skip if can't beat current max
228 if (area <= part2MaxArea) continue;
229
230 // Check using compressed grid
231 if (part2Data.hasOnlyValidPoints(part2Data.points[i], part2Data.points[j])) {
232 part2SampleCounter++;
233 const minRectX = Math.min(t1.x, t2.x);
234 const maxRectX = Math.max(t1.x, t2.x);
235 const minRectY = Math.min(t1.y, t2.y);
236 const maxRectY = Math.max(t1.y, t2.y);
237
238 if (area > part2MaxArea) {
239 part2MaxArea = area;
240 part2Milestones.push({
241 x1: minRectX,
242 y1: minRectY,
243 x2: maxRectX,
244 y2: maxRectY,
245 area,
246 tile1: i,
247 tile2: j,
248 isMax: true,
249 });
250 } else if (part2SampleCounter % part2SampleInterval === 0) {
251 part2Samples.push({
252 x1: minRectX,
253 y1: minRectY,
254 x2: maxRectX,
255 y2: maxRectY,
256 area,
257 tile1: i,
258 tile2: j,
259 isMax: false,
260 });
261 }
262 }
263 }
264}
265
266console.log(
267 `Part 2: Found ${part2SampleCounter} valid rectangles, ${part2Milestones.length} milestones`,
268);
269
270const part2Stages = [...part2Samples, ...part2Milestones].sort((a, b) => {
271 if (a.tile1 !== b.tile1) return a.tile1 - b.tile1;
272 return a.tile2 - b.tile2;
273});
274
275// Rebuild isMax flags for part2
276let currentMaxPart2 = 0;
277part2Stages.forEach((stage) => {
278 if (stage.area > currentMaxPart2) {
279 stage.isMax = true;
280 currentMaxPart2 = stage.area;
281 } else {
282 stage.isMax = false;
283 }
284});
285
286// For visualization, compute green tiles (boundary tiles)
287const greenTiles: Array<{ x: number; y: number }> = [];
288for (let i = 0; i < tiles.length; i++) {
289 const t1 = tiles[i];
290 const t2 = tiles[(i + 1) % tiles.length];
291
292 if (t1.x === t2.x) {
293 const minY = Math.min(t1.y, t2.y);
294 const maxY = Math.max(t1.y, t2.y);
295 for (let y = minY + 1; y < maxY; y++) {
296 greenTiles.push({ x: t1.x, y });
297 }
298 } else if (t1.y === t2.y) {
299 const minX = Math.min(t1.x, t2.x);
300 const maxX = Math.max(t1.x, t2.x);
301 for (let x = minX + 1; x < maxX; x++) {
302 greenTiles.push({ x, y: t1.y });
303 }
304 }
305}
306
307const tilesData = JSON.stringify(tiles);
308const greenTilesData = JSON.stringify(greenTiles);
309const stagesData = JSON.stringify(allStages);
310const part2StagesData = JSON.stringify(part2Stages);
311
312const html = `<!DOCTYPE html>
313<html lang="en">
314<head>
315 <meta charset="UTF-8">
316 <meta name="viewport" content="width=device-width, initial-scale=1.0">
317 <title>AoC 2025 Day 9 - Movie Theater Floor</title>
318 <style>
319 * {
320 box-sizing: border-box;
321 }
322 body {
323 background: #1e1e2e;
324 color: #cdd6f4;
325 font-family: "Source Code Pro", monospace;
326 font-size: 14pt;
327 font-weight: 300;
328 padding: 20px;
329 display: flex;
330 flex-direction: column;
331 align-items: center;
332 min-height: 100vh;
333 margin: 0;
334 }
335 #canvas {
336 border: 2px solid #313244;
337 image-rendering: pixelated;
338 image-rendering: crisp-edges;
339 max-width: 95vw;
340 max-height: 70vh;
341 margin: 20px 0;
342 }
343 h1 {
344 color: #a6e3a1;
345 text-shadow: 0 0 2px #a6e3a1, 0 0 5px #a6e3a1;
346 margin-bottom: 10px;
347 font-size: 1em;
348 font-weight: normal;
349 }
350 .mode-toggle {
351 display: flex;
352 align-items: center;
353 gap: 0;
354 margin: 10px 0;
355 border: 1px solid #313244;
356 background: #11111b;
357 }
358 .mode-toggle label {
359 cursor: pointer;
360 padding: 8px 16px;
361 font-size: 14px;
362 transition: all 0.2s ease;
363 border-right: 1px solid #313244;
364 }
365 .mode-toggle label:last-child {
366 border-right: none;
367 }
368 .mode-toggle label.active {
369 background: #313244;
370 color: #a6e3a1;
371 }
372 .controls {
373 background: #11111b;
374 border: 1px solid #313244;
375 padding: 15px;
376 margin: 15px 0;
377 max-width: 800px;
378 border-radius: 4px;
379 }
380 .control-row {
381 display: flex;
382 gap: 15px;
383 align-items: center;
384 margin-bottom: 15px;
385 flex-wrap: wrap;
386 justify-content: center;
387 }
388 .control-row:last-child {
389 margin-bottom: 0;
390 }
391 button {
392 background: #11111b;
393 color: #a6e3a1;
394 border: 1px solid #313244;
395 padding: 8px 16px;
396 cursor: pointer;
397 font-family: inherit;
398 font-size: 14px;
399 border-radius: 3px;
400 }
401 button:hover {
402 background: #181825;
403 }
404 button:disabled {
405 opacity: 0.5;
406 cursor: not-allowed;
407 }
408 .stats {
409 background: #11111b;
410 border: 1px solid #313244;
411 padding: 10px 15px;
412 margin: 10px 0;
413 max-width: 800px;
414 border-radius: 4px;
415 text-align: center;
416 font-size: 13px;
417 color: #a6adc8;
418 }
419 .legend {
420 display: flex;
421 gap: 15px;
422 margin-top: 10px;
423 flex-wrap: wrap;
424 justify-content: center;
425 }
426 .legend-item {
427 display: flex;
428 align-items: center;
429 gap: 6px;
430 font-size: 12px;
431 color: #a6adc8;
432 }
433 .legend-box {
434 width: 12px;
435 height: 12px;
436 border-radius: 2px;
437 }
438 .legend-box.red { background: #f38ba8; }
439 .legend-box.green { background: #a6e3a1; }
440 .legend-box.current { background: rgba(137, 180, 250, 0.3); border: 2px solid #89b4fa; }
441 .legend-box.best { background: rgba(166, 227, 161, 0.3); border: 2px solid #a6e3a1; }
442 a {
443 text-decoration: none;
444 color: #a6e3a1;
445 outline: 0;
446 }
447 a:hover, a:focus {
448 text-decoration: underline;
449 }
450 </style>
451</head>
452<body>
453 <h1>AoC 2025 Day 9 - Movie Theater Floor</h1>
454
455 <div class="mode-toggle">
456 <label id="part1Label">Part 1: Any Rectangle</label>
457 <label id="part2Label">Part 2: Red/Green Only</label>
458 </div>
459
460 <div class="controls">
461 <div class="control-row">
462 <button id="prev">← Previous</button>
463 <button id="play">▶ Play</button>
464 <button id="next">Next →</button>
465 <button id="reset">↺ Reset</button>
466 <button id="jumpToEnd">⏭ Jump to End</button>
467 </div>
468 <div class="legend">
469 <div class="legend-item"><div class="legend-box red"></div> Red Tile</div>
470 <div class="legend-item" id="greenLegend" style="display: none;"><div class="legend-box green"></div> Green Tile</div>
471 <div class="legend-item"><div class="legend-box current"></div> Testing (Blue)</div>
472 <div class="legend-item"><div class="legend-box best"></div> Largest Found (Green)</div>
473 </div>
474 </div>
475
476 <canvas id="canvas"></canvas>
477
478 <div class="stats">
479 <div id="statsInfo">Step 0/${allStages.length} | Current: 0 | Largest: 0</div>
480 <div style="margin-top: 5px; font-size: 11px;"><a href="../index.html">[Return to Index]</a></div>
481 </div>
482
483 <script type="module">
484 const tiles = ${tilesData};
485 const greenTiles = ${greenTilesData};
486 const part1Stages = ${stagesData};
487 const part2Stages = ${part2StagesData};
488
489 const minX = ${minX};
490 const maxX = ${maxX};
491 const minY = ${minY};
492 const maxY = ${maxY};
493
494 let isPart2 = false;
495 let stages = part1Stages;
496
497 console.log(\`Loaded \${tiles.length} red tiles, \${greenTiles.length} green tiles\`);
498 console.log(\`Part 1: \${part1Stages.length} stages, Part 2: \${part2Stages.length} stages\`);
499
500 // Canvas setup - auto scale to fit viewport
501 const canvas = document.getElementById('canvas');
502 const ctx = canvas.getContext('2d');
503
504 function resizeCanvas() {
505 // Calculate available space (leave room for controls and stats)
506 const availableWidth = window.innerWidth - 40; // 20px padding on each side
507 const availableHeight = window.innerHeight - 310; // room for controls and stats
508
509 // Calculate grid dimensions
510 const gridWidth = maxX - minX;
511 const gridHeight = maxY - minY;
512
513 // Calculate scale to fit available space while maintaining aspect ratio
514 const scaleX = availableWidth / (gridWidth + 1000);
515 const scaleY = availableHeight / (gridHeight + 1000);
516 const scale = Math.min(scaleX, scaleY);
517
518 // Set canvas size
519 canvas.width = (gridWidth + 1000) * scale;
520 canvas.height = (gridHeight + 1000) * scale;
521
522 return scale;
523 }
524
525 let scale = resizeCanvas();
526 const PADDING = 500; // grid units of padding
527
528 function getTileSize() {
529 return Math.max(1, scale * 100); // Scale tile size with canvas
530 }
531
532 // Recalculate on window resize
533 window.addEventListener('resize', () => {
534 scale = resizeCanvas();
535 updateUI();
536 });
537
538 function toCanvasX(x) {
539 return (x - minX + PADDING) * scale;
540 }
541
542 function toCanvasY(y) {
543 return (y - minY + PADDING) * scale;
544 }
545
546 function drawGrid(currentRect, bestRect) {
547 // Clear canvas
548 ctx.fillStyle = '#1e1e2e';
549 ctx.fillRect(0, 0, canvas.width, canvas.height);
550
551 // Draw best rectangle (green) if it exists and is different from current
552 if (bestRect && (!currentRect || bestRect !== currentRect)) {
553 const x1 = toCanvasX(bestRect.x1);
554 const y1 = toCanvasY(bestRect.y1);
555 const x2 = toCanvasX(bestRect.x2);
556 const y2 = toCanvasY(bestRect.y2);
557
558 // Draw filled rectangle
559 ctx.fillStyle = 'rgba(166, 227, 161, 0.15)';
560 ctx.fillRect(x1, y1, x2 - x1, y2 - y1);
561
562 // Draw border
563 ctx.strokeStyle = '#89b4fa'; // Blue
564 ctx.lineWidth = 1;
565 ctx.strokeRect(x1, y1, x2 - x1, y2 - y1);
566
567 // Highlight corner tiles (green)
568 const tileSize = getTileSize();
569 ctx.fillStyle = '#a6e3a1';
570 ctx.beginPath();
571 ctx.arc(x1, y1, tileSize * 1.5, 0, Math.PI * 2);
572 ctx.fill();
573 ctx.beginPath();
574 ctx.arc(x2, y2, tileSize * 1.5, 0, Math.PI * 2);
575 ctx.fill();
576 }
577
578 // Draw current rectangle being tested (red) on top
579 if (currentRect) {
580 const x1 = toCanvasX(currentRect.x1);
581 const y1 = toCanvasY(currentRect.y1);
582 const x2 = toCanvasX(currentRect.x2);
583 const y2 = toCanvasY(currentRect.y2);
584
585 // Draw filled rectangle
586 ctx.fillStyle = 'rgba(137, 180, 250, 0.15)'; // Blue
587 ctx.fillRect(x1, y1, x2 - x1, y2 - y1);
588
589 // Draw border (blue for current)
590 ctx.strokeStyle = '#89b4fa'; // Blue
591 ctx.lineWidth = 1;
592 ctx.strokeRect(x1, y1, x2 - x1, y2 - y1);
593
594 // Highlight corner tiles (blue)
595 const tileSize = getTileSize();
596 ctx.fillStyle = '#89b4fa'; // Blue
597 ctx.beginPath();
598 ctx.arc(x1, y1, tileSize * 1.5, 0, Math.PI * 2);
599 ctx.fill();
600 ctx.beginPath();
601 ctx.arc(x2, y2, tileSize * 1.5, 0, Math.PI * 2);
602 ctx.fill();
603 }
604
605 // Draw all red tiles on top
606 const tileSize = getTileSize();
607 ctx.fillStyle = '#f38ba8';
608 tiles.forEach(tile => {
609 const x = toCanvasX(tile.x);
610 const y = toCanvasY(tile.y);
611 ctx.beginPath();
612 ctx.arc(x, y, tileSize, 0, Math.PI * 2);
613 ctx.fill();
614 });
615
616 // Draw green tiles if Part 2
617 if (isPart2) {
618 ctx.fillStyle = 'rgba(166, 227, 161, 0.6)';
619 greenTiles.forEach(tile => {
620 const x = toCanvasX(tile.x);
621 const y = toCanvasY(tile.y);
622 ctx.beginPath();
623 ctx.arc(x, y, tileSize * 0.7, 0, Math.PI * 2);
624 ctx.fill();
625 });
626 }
627 }
628
629 // Animation state
630 let currentIndex = 0;
631 let isPlaying = false;
632 let animationSpeed = 100; // ms between frames
633
634 const playBtn = document.getElementById('play');
635 const prevBtn = document.getElementById('prev');
636 const nextBtn = document.getElementById('next');
637 const resetBtn = document.getElementById('reset');
638 const jumpToEndBtn = document.getElementById('jumpToEnd');
639 const statsInfo = document.getElementById('statsInfo');
640 const part1Label = document.getElementById('part1Label');
641 const part2Label = document.getElementById('part2Label');
642 const greenLegend = document.getElementById('greenLegend');
643
644 // Mode toggle
645 function setMode(part2) {
646 isPart2 = part2;
647 stages = isPart2 ? part2Stages : part1Stages;
648 currentIndex = 0;
649 isPlaying = false;
650 playBtn.textContent = '▶ Play';
651
652 if (isPart2) {
653 part1Label.classList.remove('active');
654 part2Label.classList.add('active');
655 greenLegend.style.display = 'flex';
656 } else {
657 part1Label.classList.add('active');
658 part2Label.classList.remove('active');
659 greenLegend.style.display = 'none';
660 }
661
662 updateUI();
663 }
664
665 part1Label.addEventListener('click', () => setMode(false));
666 part2Label.addEventListener('click', () => setMode(true));
667 part1Label.classList.add('active');
668
669 function updateUI() {
670 const currentRect = currentIndex > 0 ? stages[currentIndex - 1] : null;
671
672 // Find the best rectangle up to current index
673 let bestRect = null;
674 let largestSoFar = 0;
675 for (let i = 0; i < currentIndex; i++) {
676 if (stages[i].area > largestSoFar) {
677 largestSoFar = stages[i].area;
678 bestRect = stages[i];
679 }
680 }
681
682 const currentArea = currentRect ? currentRect.area : 0;
683
684 if (currentIndex > 0 && currentIndex <= 5) {
685 console.log(\`Index \${currentIndex}: currentRect=\`, currentRect);
686 }
687
688 statsInfo.textContent = \`Step \${currentIndex}/\${stages.length} | Current: \${currentArea.toLocaleString()} | Largest: \${largestSoFar.toLocaleString()}\`;
689
690 prevBtn.disabled = currentIndex === 0;
691 nextBtn.disabled = currentIndex === stages.length;
692
693 drawGrid(currentRect, bestRect);
694 }
695
696 function goToStage(index) {
697 currentIndex = Math.max(0, Math.min(stages.length, index));
698 updateUI();
699 }
700
701 prevBtn.addEventListener('click', () => goToStage(currentIndex - 1));
702 nextBtn.addEventListener('click', () => goToStage(currentIndex + 1));
703 resetBtn.addEventListener('click', () => goToStage(0));
704 jumpToEndBtn.addEventListener('click', () => goToStage(stages.length));
705
706 playBtn.addEventListener('click', () => {
707 isPlaying = !isPlaying;
708 playBtn.textContent = isPlaying ? '⏸ Pause' : '▶ Play';
709 if (isPlaying && currentIndex === stages.length) {
710 goToStage(0);
711 }
712 if (isPlaying) {
713 animate();
714 }
715 });
716
717 document.addEventListener('keydown', (e) => {
718 if (e.key === 'ArrowLeft') prevBtn.click();
719 if (e.key === 'ArrowRight') nextBtn.click();
720 if (e.key === ' ') {
721 e.preventDefault();
722 playBtn.click();
723 }
724 if (e.key === 'r' || e.key === 'R') resetBtn.click();
725 if (e.key === 'e' || e.key === 'E') jumpToEndBtn.click();
726 });
727
728 function animate() {
729 if (!isPlaying) return;
730
731 if (currentIndex < stages.length) {
732 goToStage(currentIndex + 1);
733 setTimeout(animate, animationSpeed);
734 } else {
735 isPlaying = false;
736 playBtn.textContent = '▶ Play';
737 }
738 }
739
740 // Initialize
741 updateUI();
742 </script>
743</body>
744</html>`;
745
746await Bun.write(`${scriptDir}/index.html`, html);