commit 72f028e2a99a4e8f025d108958983ff24cba8f87
parent c0062bef3c1e6590e98178ed81b22f2853a68ef0
Author: finwo <finwo@pm.me>
Date: Thu, 15 Dec 2022 13:07:29 +0100
2022/15 solution
Diffstat:
3 files changed, 155 insertions(+), 0 deletions(-)
diff --git a/2022/day-15/index.js b/2022/day-15/index.js
@@ -0,0 +1,140 @@
+const fs = require('fs');
+const through = require('through2');
+const line_by_line = require('../common/line-for-line');
+
+String.prototype.startsWith = function(subject) {
+ return this.substr(0, subject.length) === subject;
+};
+
+const rows = [];
+let xmin = Infinity;
+let ymin = Infinity;
+let xmax = -Infinity;
+let ymax = -Infinity;
+
+const scanline = 2000000;
+// const scanline = 10;
+const small = false;
+const sensors = [];
+
+const interestingArea = 4000000;
+// const interestingArea = 20;
+
+fs.createReadStream('input')
+ .pipe(line_by_line())
+
+ // Minor parsing
+ .pipe(through(function(line, enc, cb) {
+ line = line.toString();
+
+ // Parse locations
+ const parts = line.split(':');
+ const sensorTokens = parts[0].split(' ');
+ const beaconTokens = parts[1].split(' ');
+ const sensorPosition = [
+ parseInt(sensorTokens[2].replace(/[^\d\-]/g, '')),
+ parseInt(sensorTokens[3].replace(/[^\d\-]/g, '')),
+ ];
+ const beaconPosition = [
+ parseInt(beaconTokens[5].replace(/[^\d\-]/g, '')),
+ parseInt(beaconTokens[6].replace(/[^\d\-]/g, '')),
+ ];
+
+ // Track in visual representation
+ rows[sensorPosition[1]] = rows[sensorPosition[1]] || [];
+ rows[sensorPosition[1]][sensorPosition[0]] = 'S';
+ rows[beaconPosition[1]] = rows[beaconPosition[1]] || [];
+ rows[beaconPosition[1]][beaconPosition[0]] = 'B';
+
+ // Calculate distance between beacon and sensor
+ const d = Math.abs(sensorPosition[0] - beaconPosition[0]) + Math.abs(sensorPosition[1] - beaconPosition[1]);
+
+ // Store sensor for step 2
+ sensors.push({
+ pos: sensorPosition,
+ d,
+ });
+
+ // Mark locations that can NOT have a beacon (step 1)
+ for(let y=sensorPosition[1]-d; y<=sensorPosition[1]+d; y++) {
+ if (!small && y !== scanline) continue;
+ const X = d - Math.abs(sensorPosition[1] - y);
+ for(let x=sensorPosition[0]-X; x<=sensorPosition[0]+X; x++) {
+ const D = Math.abs(sensorPosition[0] - x) + Math.abs(sensorPosition[1] - y);
+ if (D > d) continue;
+ rows[y] = rows[y] || [];
+ rows[y][x] = rows[y][x] || '#';
+ }
+ }
+
+ xmin = Math.min(xmin, sensorPosition[0]-d, beaconPosition[0]-d);
+ ymin = Math.min(ymin, sensorPosition[1]-d, beaconPosition[1]-d);
+ xmax = Math.max(xmax, sensorPosition[0]+d, beaconPosition[0]+d);
+ ymax = Math.max(ymax, sensorPosition[1]+d, beaconPosition[1]+d);
+
+ // console.log({ sensorTokens, sensorPosition, beaconTokens, beaconPosition, d });
+ cb();
+ }))
+
+ .on('finish', () => {
+ console.log('loaded');
+
+ xmin -= 2;
+ ymin -= 2;
+ xmax += 2;
+ ymax += 2;
+
+ // Debug display for small
+ if (small) {
+ for(let y=ymin; y<=ymax; y++) {
+ if (!rows[y]) {
+ process.stdout.write('.'.repeat(xmax-xmin+1) + '\n');
+ continue;
+ }
+ for(let x=xmin; x<=xmax; x++) {
+ if (rows[y][x]) {
+ process.stdout.write(rows[y][x]);
+ } else {
+ process.stdout.write('.');
+ }
+ }
+ process.stdout.write(` ${y}\n`);
+ }
+ }
+
+ // Step 2
+ for(let y=0; y<=interestingArea; y++) {
+ // console.log(y);
+ for(let x=0; x<=interestingArea; x++) {
+
+ const found = sensors.find(sensor => {
+ const d = Math.abs(sensor.pos[0] - x) + Math.abs(sensor.pos[1] - y);
+ return d <= sensor.d;
+ });
+
+ if (!found) {
+ console.log({ found: [x, y], freq: (x*4000000) + y });
+ process.exit(0);
+ }
+
+ // Skip X beyong the sensor
+ const X = found.d - Math.abs(found.pos[1] - y);
+ x = found.pos[0] + X;
+ }
+ }
+
+ // for(let y=0; y<=interestingArea; y++) {
+ // for(let x=0; x<=interestingArea; x++) {
+ // if (rows[y][x]) continue;
+ // console.log({ found: [x, y], freq: (x*4000000) + y });
+ // }
+ // }
+
+ // console.log({
+ // row: Object.values(rows[scanline])
+ // .map(c => !!~'#S'.indexOf(c||'.') ? 1 : 0)
+ // .reduce((r,a) => r+a, 0)
+ // });
+
+
+ });
diff --git a/2022/day-15/sample b/2022/day-15/sample
@@ -0,0 +1,14 @@
+Sensor at x=2, y=18: closest beacon is at x=-2, y=15
+Sensor at x=9, y=16: closest beacon is at x=10, y=16
+Sensor at x=13, y=2: closest beacon is at x=15, y=3
+Sensor at x=12, y=14: closest beacon is at x=10, y=16
+Sensor at x=10, y=20: closest beacon is at x=10, y=16
+Sensor at x=14, y=17: closest beacon is at x=10, y=16
+Sensor at x=8, y=7: closest beacon is at x=2, y=10
+Sensor at x=2, y=0: closest beacon is at x=2, y=10
+Sensor at x=0, y=11: closest beacon is at x=2, y=10
+Sensor at x=20, y=14: closest beacon is at x=25, y=17
+Sensor at x=17, y=20: closest beacon is at x=21, y=22
+Sensor at x=16, y=7: closest beacon is at x=15, y=3
+Sensor at x=14, y=3: closest beacon is at x=15, y=3
+Sensor at x=20, y=1: closest beacon is at x=15, y=3
diff --git a/2022/day-15/tiny b/2022/day-15/tiny
@@ -0,0 +1 @@
+Sensor at x=0, y=11: closest beacon is at x=2, y=10
