Public
Edited
Dec 2
Paused
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
function parse(input) {
const lines = input.trim().split("\n");
const sensors = lines.map((line) => {
const [sx, sy, bx, by] = line.match(/-?\d+/g).map(Number);
return [sx, sy, bx, by];
});
return sensors;
}
Insert cell
Insert cell
function dist([x0, y0, x1, y1]) {
return Math.abs(x0 - x1) + Math.abs(y0 - y1);
}
Insert cell
Insert cell
function numEmpty(sensors, row) {
// Find the sensors in range of the given row and store their sorted extents along that row.
const extents = sensors
.filter(([sx, sy, bx, by]) => Math.abs(sy - row) <= dist([sx, sy, bx, by]))
.map(([sx, sy, bx, by]) => {
const halfWidth = dist([sx, sy, bx, by]) - Math.abs(sy - row);
return [sx - halfWidth, sx + halfWidth];
})
.sort((a, b) => a[0] - b[0]);

// Merge overlapping extents
let [left, right, n] = [extents[0][0], extents[0][1], 0];
extents.push([Infinity, Infinity]); // Dummy extent to handle the last set
for (const extent of extents) {
const [start, end] = extent;
if (start <= right) {
right = Math.max(right, end);
} else {
n += right - left + 1;
[left, right] = start === Infinity ? [left, right] : [start, end];
}
}
// Any beacons detected in this row?
const numBeaconsInRow = sensors.reduce(
(beacons, [sx, sy, bx, by]) => (by === row ? beacons.add(bx) : beacons),
new Set()
).size;
return n - numBeaconsInRow;
}
Insert cell
function part1(input) {
return numEmpty(parse(input), 2000000);
}
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
function toOrthogonal(sensors) {
const rotate = (x, y) => [x + y, y - x];
return sensors.map(([sx, sy, bx, by]) => [
...rotate(sx, sy),
dist([sx, sy, bx, by])
]);
}
Insert cell
Insert cell
function fromOrthogonal([xPrime, yPrime]) {
return [(xPrime - yPrime) / 2, (xPrime + yPrime) / 2];
}
Insert cell
Insert cell
Insert cell
Insert cell
function dilate(orthogonalSensors) {
return orthogonalSensors.map(([sx, sy, d]) => [
sx - d - 1,
sy - d - 1,
sx + d + 1,
sy + d + 1
]);
}
Insert cell
Insert cell
Insert cell
function findDistressBeacon(scanners) {
const expandedSquares = dilate(toOrthogonal(scanners));
const [vEdges, hEdges] = [[], []];
const counts = new Map();

// Store vertcial and horizontal edges
for (const [x1, y1, x2, y2] of expandedSquares) {
vEdges.push({ x: x1 });
vEdges.push({ x: x2 });
hEdges.push({ y: y1 });
hEdges.push({ y: y2 });
}

// Find intersections of vertical and horiztonal edges
for (const vEdge of vEdges) {
for (const hEdge of hEdges) {
const point = [vEdge.x, hEdge.y];
const pointStr = point.toString();
counts.set(pointStr, (counts.get(pointStr) || 0) + 1);
}
}

// Find points with at least 4 intersections and check they are interior
const [distressBeacon] = Array.from(counts.entries())
.filter(([_, count]) => count >= 4)
.map(([key]) => key.split(",").map(Number))
.filter(
([x, y]) =>
!expandedSquares.some(
([x1, y1, x2, y2]) => x > x1 && x < x2 && y > y1 && y < y2
) &&
[
[x - 1, y],
[x + 1, y],
[x, y - 1],
[x, y + 1]
].every(([adjX, adjY]) =>
expandedSquares.some(
([x1, y1, x2, y2]) =>
adjX > x1 && adjX < x2 && adjY > y1 && adjY < y2
)
)
);

// Convert back to original coordinate system
const [x, y] = fromOrthogonal(distressBeacon);
return x * 4000000 + y;
}
Insert cell
function part2(input) {
return findDistressBeacon(parse(input));
}
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell

Purpose-built for displays of data

Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
Learn more