Public
Edited
Dec 14, 2022
Paused
1 fork
15 stars
Liquid flow velocity in pipesTernary plotMerging hexagonsSpotify Pop ArtistsDistance Angle VoronoiVoronoi labelsHello, olliRough PlotCorrelation heatmapUsing d3.blur with PlotJob vacancies in AustraliaWarming stripesAssemblée nationale 2017-2022Minimalist dodge plotPlot.image borderfrom columnar to tidy dataAge/Handgroup, bin and sortPlot.stereoHistogramVariants of SARS-Cov-2 in EuropeVariants du SARS-CoV-2 en FranceTopological subsamplingAnimate a bar chart (OBSOLETE)Metbrewer color schemesHow many books was I reading?Road traffic under COVID restrictions (France)Convex hull mark (#154)Hello, Open MeteoK-means binningMatrix diagramQuasi-random Monte Carlo integrationDifference chartELD ViewerPlot early birdROC curveSkies PlotHappy anniversary, Project Gutenberg!The Sun’s analemmaObservable Plot in a Web WorkerregressionEdit data with PlotConical gradient PlotPlot HyperboloidExperimental Plot BeeswarmThe ARPANET in December 1969Irregular bins histogramLog-scale histogramDatabase Outage Plotcount distinct (#412)Scatterplot matrixIrregular Bar ChartFacet exclusion transformCanvas PlotHow to attach a plot to a DOM elementRenko ChartWaffle ChartQatar Population PyramidSlope ChartSequence LogosStacked bin dots
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 };
}
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.
