Visualization toolmaker. Founder @observablehq. Creator @d3. Former @nytgraphics. Pronounced BOSS-tock.
test = `Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi
`
testGrid = parseGrid(test)
function parseGrid(input) {
const rows = input.trim().split("\n");
const n = rows.length;
const m = rows[0].length;
const values = rows.flatMap((line) => line.split(""));
const startIndex = values.indexOf("S");
const endIndex = values.indexOf("E");
return new Grid(n, m, startIndex, endIndex, values.map(parseHeight));
}
function parseHeight(char) {
return char === "S" ? parseHeight("a")
: char === "E" ? parseHeight("z")
: char.charCodeAt(0) - "a".charCodeAt(0);
}
class Grid {
constructor(n, m, startIndex, endIndex, values) {
this.n = n;
this.m = m;
this.startIndex = startIndex;
this.endIndex = endIndex;
this.values = values;
}
*[Symbol.iterator]() {
for (let y = 0, i = 0; y < this.n; ++y) {
for (let x = 0; x < this.m; ++x, ++i) {
yield [x, y, this.values[i]];
}
}
}
*range() {
for (let i = 0, n = this.n * this.m; i < n; ++i) {
yield i;
}
}
heightAt(i) {
return this.values[i];
}
*outgoingEdgesAt(i) {
const h = this.heightAt(i) + 1;
const [x, y] = this.position(i);
if (0 < y && this.heightAt(i - this.m) <= h) yield i - this.m;
if (y < this.n - 1 && this.heightAt(i + this.m) <= h) yield i + this.m;
if (0 < x && this.heightAt(i - 1) <= h) yield i - 1;
if (x < this.m - 1 && this.heightAt(i + 1) <= h) yield i + 1;
}
*incomingEdgesAt(i) {
const h = this.heightAt(i) - 1;
const [x, y] = this.position(i);
if (0 < y && this.heightAt(i - this.m) >= h) yield i - this.m;
if (y < this.n - 1 && this.heightAt(i + this.m) >= h) yield i + this.m;
if (0 < x && this.heightAt(i - 1) >= h) yield i - 1;
if (x < this.m - 1 && this.heightAt(i + 1) >= h) yield i + 1;
}
index(x, y) {
return this.m * y + x;
}
x(i) {
return i % this.m;
}
y(i) {
return Math.floor(i / this.m);
}
position(i) {
return [this.x(i), this.y(i)];
}
}
visualizeGrid(testGrid)
visualizeGrid(testGrid, testGrid.startIndex)
shortestPaths(testGrid)
function visualizeGrid(grid, startIndex, endIndex = grid.endIndex, paths = shortestPaths(grid, endIndex)) {
return Plot.plot({
padding: 0,
height: grid.n * 24 + 20,
width: grid.m * 24 + 20,
margin: 0,
axis: null,
color: {
scheme: "blues"
},
marks: [
Plot.cell(grid, {
fill: "2",
inset: 0.5
}),
startIndex === undefined
? Plot.arrow(paths, {
filter: (j) => j >= 0,
x1: (j, i) => grid.x(i),
y1: (j, i) => grid.y(i),
x2: (j, i) => grid.x(j),
y2: (j, i) => grid.y(j),
stroke: "red",
inset: 4
})
: Plot.line(shortestPath(grid, startIndex, endIndex, paths), {
stroke: "red",
strokeWidth: 3
}),
Plot.text(grid, {
text: "2"
})
]
});
}
function shortestPaths(grid, endIndex = grid.endIndex) {
const visited = new Uint8Array(grid.n * grid.m);
const distance = new Float64Array(grid.n * grid.m).fill(Infinity);
const next = Int32Array.from({length: grid.n * grid.m}, (_, i) => i);
next.distance = distance;
let currentIndex = endIndex;
distance[currentIndex] = 0;
do {
const currentDistance = distance[currentIndex] + 1;
for (const nextIndex of grid.incomingEdgesAt(currentIndex)) {
if (currentDistance < distance[nextIndex]) {
distance[nextIndex] = currentDistance;
next[nextIndex] = currentIndex;
}
}
visited[currentIndex] = 1;
currentIndex = d3.minIndex(distance, (d, i) => (visited[i] ? NaN : d)); // TODO priority queue?
} while (distance[currentIndex] < Infinity);
return next;
}
function shortestPath(grid, startIndex = grid.startIndex, endIndex = grid.endIndex, paths = shortestPaths(grid, endIndex)) {
const path = [grid.position(startIndex)];
while (startIndex !== endIndex) {
const nextIndex = paths[startIndex];
if (nextIndex === startIndex) break; // path not found
path.push(grid.position(nextIndex));
startIndex = nextIndex;
}
return path;
}
input = FileAttachment("input.txt").text()
grid = parseGrid(input)
visualizeGrid(grid, grid.startIndex)
shortestPath(grid).length - 1
d3.min(shortestPaths(grid).distance, (d, i) => grid.heightAt(i) === 0 ? d : NaN)
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.
