Visualization toolmaker. Founder @observablehq. Creator @d3. Former @nytgraphics. Pronounced BOSS-tock.
test = `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
`
testSensors = parseSensors(test)
function parseSensors(input) {
return input.trim().split("\n").map(parseSensor);
}
function parseSensor(input) {
let {groups: {sx, sy, bx, by}} = /^Sensor at x=(?<sx>-?\d+), y=(?<sy>-?\d+): closest beacon is at x=(?<bx>-?\d+), y=(?<by>-?\d+)$/.exec(input);
sx = Number(sx);
sy = Number(sy);
bx = Number(bx);
by = Number(by);
return {sx, sy, bx, by, r: distance(sx, sy, bx, by)};
}
visualizeSensors(testSensors, 10)
function visualizeSensors(sensors, y) {
return Plot.plot({
grid: true,
inset: 10,
x: {axis: "top", tickFormat: "s"},
y: {tickFormat: "s", reverse: true},
marks: [
Plot.geo(sensors, {geometry: computeExclusionZone, fill: "red", fillOpacity: 0.1, stroke: "red"}),
Plot.ruleY([y], {stroke: "blue"}),
Plot.text(sensors, {text: () => "S", x: "sx", y: "sy"}),
Plot.text(sensors, {text: () => "B", x: "bx", y: "by"}),
]
});
}
function computeExclusionZone(sensor) {
return {
type: "Polygon",
coordinates: [
[
[sensor.sx - sensor.r, sensor.sy],
[sensor.sx, sensor.sy - sensor.r],
[sensor.sx + sensor.r, sensor.sy],
[sensor.sx, sensor.sy + sensor.r],
[sensor.sx - sensor.r, sensor.sy]
]
]
};
}
function findClosestSensor(sensors, x, y) {
return d3.least(sensors, ({sx, sy}) => Math.hypot(sx - x, sy - y));
}
findClosestSensor(testSensors, 5, 7)
function distance(x1, y1, x2, y2) {
return Math.abs(x2 - x1) + Math.abs(y2 - y1);
}
countExclusions(testSensors, 10)
function countExclusions(sensors, y) {
const positions = sensors.flatMap((s) => [[s.sx, s.sy], [s.bx, s.by]]);
const [x1, x2] = d3.extent(positions, ([x]) => x);
const r = d3.max(sensors, (s) => distance(s.sx, s.sy, s.bx, s.by));
return d3.sum(d3.range(x1 - r, x2 + r), (x) => {
for (const {sx, sy, bx, by} of sensors) {
if (distance(bx, by, x, y) === 0) return 0; // coincident with beacon
const sr = distance(sx, sy, bx, by);
const sd = distance(sx, sy, x, y);
if (sr >= sd) return 1; // excluded by sensor
}
return 0;
});
}
findDistressBeacon(testSensors, 20, 20)
computeTuningFrequency(14, 11)
findDistressBeacon(sensors, 4000000, 4000000)
computeTuningFrequency(3299359, 3355220)
function computeTuningFrequency(x, y) {
return x * 4000000 + y;
}
function* findDistressBeacon(sensors, xMax, yMax) {
let i = 0;
for (let y = 0; y < yMax; ++y) {
search: for (let x = 0; x < xMax; ++x) {
if (++i % 100000 === 0) yield [x, y];
for (const {sx, sy, bx, by, r} of sensors) {
if (r >= distance(sx, sy, x, y)) {
x = sx + r - Math.abs(sy - y);
continue search; // excluded by sensor
}
}
yield [x, y];
return;
}
}
}
input = FileAttachment("input.txt").text()
sensors = parseSensors(input)
visualizeSensors(sensors, 2000000)
countExclusions(sensors, 2000000)
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.
