advent-of-code

commit 74c942a32d80836b5917cf66516b1c046a1f84f9
parent c328e8173827941e1a485a63076d8e030375bbe9
Author: finwo <finwo@pm.me>
Date:   Sun, 28 Dec 2025 13:46:46 +0100

Completed 2025/09

Diffstat:
A
2025/09/example.txt
 | 
8
++++++++
A
2025/09/index.js
 | 
166
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 174 insertions(+), 0 deletions(-)
diff --git a/2025/09/example.txt b/2025/09/example.txt
@@ -0,0 +1,8 @@
+7,1
+11,1
+11,7
+9,7
+9,5
+2,5
+2,3
+7,3
diff --git a/2025/09/index.js b/2025/09/index.js
@@ -0,0 +1,166 @@
+#!/usr/bin/env node
+
+const fs = require('node:fs');
+
+const input = fs
+  .readFileSync('input', 'utf-8')
+  .split('\r\n').join('\n')
+  .split('\r').join('\n')
+  .split('\n')
+  .filter(e => e)
+  .map(line => line.split(',').map(n => parseInt(n,10)))
+
+let part1largest = -Infinity;
+let part2largest = -Infinity;
+
+let inputminx =  Infinity;
+let inputmaxx = -Infinity;
+let inputminy =  Infinity;
+let inputmaxy = -Infinity;
+
+// Build map of all vertical lines
+const verticals = [];
+for(let i=0; i<input.length; i++) {
+  inputminx = Math.min(inputminx, input[i][0]);
+  inputminy = Math.min(inputminy, input[i][1]);
+  inputmaxx = Math.max(inputmaxx, input[i][0]);
+  inputmaxy = Math.max(inputmaxy, input[i][1]);
+
+  const current = i;
+  const next    = (i+1) % input.length;
+  if (input[current][1] === input[next][1]) continue;
+  verticals.push([
+    input[current][0],
+    input[current][1],
+    input[next][1],
+  ]);
+}
+
+function is_inside(vector) {
+  let inside = false;
+  for (let vidx = 0; vidx < verticals.length; vidx++) {
+    let vcur = verticals[vidx];
+    let vnxt = verticals[(vidx+1)%verticals.length];
+
+    // Handle ON the horizontal line
+    if (
+      (vector[1] === vcur[2] && vector[0] <= vcur[0] && vector[0] >= vnxt[0]) ||
+      (vector[1] === vcur[2] && vector[0] <= vnxt[0] && vector[0] >= vcur[0])
+    ) {
+      return true;
+    }
+
+    if (vector[0] > vcur[0]) continue;
+    if (vector[1] > vcur[1] && vector[1] > vcur[2]) continue;
+    if (vector[1] < vcur[1] && vector[1] < vcur[2]) continue;
+
+    // Handle ON the vertical line
+    if (vector[0] === vcur[0]) {
+      return true;
+    }
+
+    // Handle double-hit going same direction = inside
+    if (
+      vector[1] === vcur[2] &&
+      vector[0]  <  vnxt[0] &&
+      (
+        ((vcur[1] < vector[1]) && (vector[1] < vnxt[2])) ||
+        ((vcur[1] > vector[1]) && (vector[1] > vnxt[2]))
+      )
+    ) {
+      // Skip, the next will catch it for being inside
+      continue;
+    }
+
+    // Here = hit vertical
+    inside = !inside;
+  }
+
+  return inside;;
+}
+
+for(const src of input) {
+  next: for(const dst of input) {
+    // console.log(`Checking ${src} -- ${dst}`);
+    const width  = Math.abs(src[0] - dst[0]) + 1;
+    const height = Math.abs(src[1] - dst[1]) + 1;
+    const area   = width * height;
+    part1largest = Math.max(part1largest, area);
+
+    // Skip checking if area < current largest
+    if (area <= part2largest) continue;
+
+    // Short check
+    const src_flipped = [ src[0], dst[1] ];
+    const dst_flipped = [ dst[0], src[1] ];
+    if (!is_inside(src_flipped)) {
+      continue next;
+    }
+    if (!is_inside(dst_flipped)) {
+      continue next;
+    }
+
+    const _src = [ Math.min(src[0], dst[0]), Math.min(src[1], dst[1]) ];
+    const _dst = [ Math.max(src[0], dst[0]), Math.max(src[1], dst[1]) ];
+
+    // Having a marked tile solidly within the square => implies gap within
+    for(const test of input) {
+      if (test[0] <= _src[0]) continue;
+      if (test[0] >= _dst[0]) continue;
+      if (test[1] <= _src[1]) continue;
+      if (test[1] >= _dst[1]) continue;
+      // Here = marked tile within square
+      continue next;
+    }
+
+    // Only along edges, check every tile
+    let covered = true;
+
+    for(let y = _src[1] ; y <= _dst[1] ; y++) {
+      if (!(
+        is_inside([_src[0], y]) &&
+        is_inside([_dst[0], y])
+      )) {
+        covered = false;
+        break;
+      }
+    }
+    // for(let x = _src[0] ; x <= _dst[0] ; x++) {
+    //   if (!(
+    //     is_inside([x, _src[1]]) &&
+    //     is_inside([x, _dst[1]])
+    //   )) {
+    //     covered = false;
+    //     break;
+    //   }
+    // }
+    if (covered) {
+      // Mark found square as if largest
+      part2largest = Math.max(part2largest, area);
+    }
+
+  }
+}
+
+// // Debug display, gives an idea of the shape
+// (async () => {
+//   for(let y = inputminy; y <= inputmaxy ; y+=1024) {
+//     for(let x = inputminx; x <= inputmaxx ; x+=1024) {
+//     //   await new Promise(done => setTimeout(done, 1));
+//       const point = input.find(tile => tile[0] === x && tile[1] === y);
+//       if (point) {
+//         process.stdout.write('#');
+//       } else if (is_inside([x,y])) {
+//         process.stdout.write('.');
+//       } else {
+//         process.stdout.write(' ');
+//       }
+//     }
+//     process.stdout.write('\n');
+//   }
+// })();
+
+const part1 = part1largest;
+const part2 = part2largest;
+process.stdout.write(`------[ Part 1: ${part1} ]------\n`);
+process.stdout.write(`------[ Part 2: ${part2} ]------\n`);