Developer @Observable
parse = (s) =>
Grid.fromText(s, (c) => ({
height: c === "S" ? 0 : c === "E" ? 25 : c.charCodeAt(0) - "a".charCodeAt(),
start: c === "S",
end: c === "E",
neighbors: []
}))
function part1(grid) {
// build graph
for (const { point, x, y } of grid) {
for (const { dx, dy } of dirs) {
let x2 = x + dx;
let y2 = y + dy;
if (grid.at([x2, y2])?.height <= point.height + 1) {
point.neighbors.push([x2, y2]);
}
}
}
// dijkstra's
const visited = new Set();
let tentativeDistances = new Map();
let unvisited = Array.from(grid);
let start = unvisited.find((d) => d.point.start);
let end = unvisited.find((d) => d.point.end);
let endAddress = `${end.x},${end.y}`;
tentativeDistances.set(`${start.x},${start.y}`, 0);
while (unvisited.length && !visited.has(endAddress)) {
let currentIndex = d3.minIndex(
unvisited,
(d) => tentativeDistances.get(`${d.x},${d.y}`) ?? Infinity
);
let [current] = unvisited.splice(currentIndex, 1);
let currentAddress = `${current.x},${current.y}`;
if (currentAddress === endAddress) break;
let currentDist = tentativeDistances.get(currentAddress);
for (const neighbor of current.point.neighbors) {
let ps = neighbor.join(",");
if (visited.has(ps)) continue;
if ((tentativeDistances.get(ps) ?? Infinity) > currentDist + 1) {
tentativeDistances.set(ps, currentDist + 1);
}
}
visited.add(currentAddress);
}
return tentativeDistances.get(endAddress);
}
function part2(grid) {
// build graph
for (const { point, x, y } of grid) {
for (const { dx, dy } of dirs) {
let x2 = x + dx;
let y2 = y + dy;
if (grid.at([x2, y2])?.height >= point.height - 1) {
point.neighbors.push([x2, y2]);
}
}
}
// dijkstra's
const visited = new Set();
let tentativeDistances = new Map();
let unvisited = Array.from(grid);
let end = unvisited.find((d) => d.point.end);
let endAddress = `${end.x},${end.y}`;
tentativeDistances.set(endAddress, 0);
while (unvisited.length) {
let currentIndex = d3.minIndex(
unvisited,
(d) => tentativeDistances.get(`${d.x},${d.y}`) ?? Infinity
);
let [current] = unvisited.splice(currentIndex, 1);
let currentAddress = `${current.x},${current.y}`;
let currentDist = tentativeDistances.get(currentAddress);
for (const neighbor of current.point.neighbors) {
let ps = neighbor.join(",");
if (visited.has(ps)) continue;
if ((tentativeDistances.get(ps) ?? Infinity) > currentDist + 1) {
tentativeDistances.set(ps, currentDist + 1);
}
}
visited.add(currentAddress);
}
let combined = Array.from(
tentativeDistances.entries(),
([address, distance]) => ({
pos: address.split(",").map((d) => +d),
distance
})
)
.map((d) => ({
...d,
height: grid.at(d.pos).height
}))
.filter((d) => d.height === 0);
return d3.min(combined, (d) => d.distance);
}
class Grid {
constructor(points) {
this.points = points;
}
static fromText(s, mapper = aoc.identity) {
return new Grid(
s
.trim()
.split("\n")
.filter((l) => l.length > 0)
.map((l) => l.split("").map(mapper))
);
}
get width() {
return this.points[0].length;
}
get height() {
return this.points.length;
}
at([x, y]) {
return this.points[y]?.[x];
}
*[Symbol.iterator]() {
let w = this.width;
let h = this.height;
for (let y = 0; y < h; y++) {
for (let x = 0; x < w; x++) {
yield { point: this.at([x, y]), x, y, w, h };
}
}
}
}
dirs = [
{ dx: 1, dy: 0 },
{ dx: -1, dy: 0 },
{ dx: 0, dy: 1 },
{ dx: 0, dy: -1 }
]
meta = aoc.meta({
day: 12,
parse,
inputs,
parts: [part1, part2],
expected: { test: [31, 29], real: [330, 321] },
href: "https://observablehq.com/d/80fde408e1efca39?collection=@mythmon/advent-of-code-2022"
})
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.
