function parse(input) {
const terrain = { dem: input.split("\n").map((row) => row.split("")) };
terrain.nRows = terrain.dem.length;
terrain.nCols = terrain.dem[0].length;
for (let row = 0; row < terrain.nRows; row++) {
for (let col = 0; col < terrain.nCols; col++) {
if (terrain.dem[row][col] === "S") {
terrain.start = [row, col];
terrain.dem[row][col] = 0;
} else if (terrain.dem[row][col] === "E") {
terrain.end = [row, col];
terrain.dem[row][col] = 26;
} else {
terrain.dem[row][col] =
terrain.dem[row][col].charCodeAt(0) - "a".charCodeAt(0);
}
}
}
return terrain;
}
function canVisit(r, c, terrain) {
const ns = [];
const z = terrain.dem[r][c];
if (r > 0 && terrain.dem[r - 1][c] - z >= -1) {
ns.push([r - 1, c]);
}
if (c > 0 && terrain.dem[r][c - 1] - z >= -1) {
ns.push([r, c - 1]);
}
if (r < terrain.nRows - 1 && terrain.dem[r + 1][c] - z >= -1) {
ns.push([r + 1, c]);
}
if (c < terrain.nCols - 1 && terrain.dem[r][c + 1] - z >= -1) {
ns.push([r, c + 1]);
}
return ns;
}
dMax = 9999 // Some large distance value we can use to signal we have not visited a cell yet.
function distToEnd(terrain, endFn) {
const dists = AOC.gInit(terrain.nRows, terrain.nCols, dMax);
const [rEnd, cEnd] = terrain.end;
dists[rEnd][cEnd] = 0;
const todo = [[...terrain.end, 0]];
const traverse = (todo) => {
while (todo.length > 0) {
const [r0, c0, dist] = todo.shift();
if (endFn(r0, c0, terrain)) {
// We've come to the end of the search, so report the last distance found.
return dists[r0][c0];
}
canVisit(r0, c0, terrain).forEach(([r, c]) => {
if (dists[r][c] === dMax) {
dists[r][c] = dist + 1;
todo.push([r, c, dist + 1]);
}
});
}
};
return traverse(todo);
}
function part1(input) {
return distToEnd(
parse(input),
(r, c, terrain) => r == terrain.start[0] && c == terrain.start[1]
);
}
function part2(input) {
return distToEnd(parse(input), (r, c, terrain) => terrain.dem[r][c] === 0);
}
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.
