Public
Edited
Dec 14, 2022
Paused
1 fork
15 stars
Slope ChartQatar Population PyramidSequence LogosCanvas PlotFacet exclusion transformScatterplot matrixThe ARPANET in December 1969Experimental Plot BeeswarmEdit data with PlotPlot: regressionObservable Plot in a Web WorkerSkies PlotPlot early birdPlot: Difference chartConvex hull mark (#154)Plot: Animate a bar chart (OBSOLETE)Topological subsamplingPlot.stereoHistogramRough PlotHello, olliPlot: Voronoi labelsDistance Angle VoronoiFlight PathsHello, @thi.ng/grid-iteratorsSpotify Pop ArtistsPlot: Radial transformTernary plot
AoC 12: shortest path under constraints
// part 2
bestA = d3.least(
Array.from(state.costs, (cost, i) => ({ cost, i })),
({ cost, i }) => (V[i] === 0 ? cost : Infinity)
)
state.costs
state.time
state.perf // performance.now
state.costs[terrain[backwards ? "start" : "end"]]
w = input.split("\n")[0].length
h = input.split("\n").length
terrain = {
let start, end;
const V = Array.from(input.replaceAll("\n", ""));
for (let i = 0; i < V.length; ++i) {
if (V[i] === "S") (start = i), (V[i] = "a"); // start S is a
else if (V[i] === "E") (end = i), (V[i] = "z"); // end E is z
V[i] = V[i].charCodeAt(0) - 97;
}
return { V, start, end };
}
V = terrain.V
// Compute these contours once, rather than thousands of rect elements with Plot.cell
contours = d3.contours().size([w, h]).thresholds(25).smooth(false)(V)
state = {
const [S, E] = backwards
? [terrain.end, terrain.start]
: [terrain.start, terrain.end];
// The tree is just here to draw on the map, but not needed for the computation.
function walk(tree, active) {
let node = d3.least(active, (d) =>
Math.hypot((d % w) - (E % w), ((d / w) | 0) - ((E / w) | 0))
);
const path = [node];
while (tree.has(node)) path.push((node = tree.get(node)));
return path;
}
const tree = new Map();
// Tested with a priority queue and A* in https://observablehq.com/@fil/advent-of-code-12@506;
// and it doesn't help
const active = new Set([S]);
const costs = new Array(V.length).fill(Infinity);
costs[S] = 0;
let t = 0;
const t0 = performance.now();
do {
const node = active.values().next().value; // get first
active.delete(node);
const x = node % w;
const y = (node / w) | 0;
for (const nei of [
x > 0 && node - 1,
x < w - 1 && node + 1,
y > 0 && node - w,
y < h - 1 && node + w
]) {
// ignore neighbor outside the map
if (nei === false) continue;
// acceptable neighbor: max 1 step _up_
if ((backwards ? -1 : 1) * (V[nei] - V[node]) <= 1) {
const c = costs[node] + 1;
if (c < costs[nei]) {
costs[nei] = c;
active.add(nei);
tree.set(nei, node);
}
}
}
if (++t % steps === 0) {
yield { costs, active, tree, time: t, walk: walk(tree, active) };
}
} while (active.size);
const perf = performance.now() - t0;
yield { costs, active, tree, time: t, walk: walk(tree, [E]), perf };
}
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.