Advent of Code 2024 - #1Advent of Code 2023 - #19Advent of Code 2023 - #18Advent of Code 2023 - #16Advent of Code 2023 - #15Advent of Code 2023 - #14Advent of Code 2023 - #13Advent of Code 2023 - #12Advent of Code 2023 - #11Advent of Code 2023 - #10Advent of Code 2023 - #9Advent of Code 2023 - #8Advent of Code 2023 - #7Advent of Code 2023 - #6Advent of Code 2023 - #5Advent of Code 2023 - #4Advent of Code 2023 - #3Advent of Code 2023 - #2Advent of Code 2023 - #1
Advent of Code 2023 - #17
show(tree01)
cost = [...input.replaceAll("\n", "")].map(Number)
W = Math.sqrt(cost.length)
import { shortest_tree } from "@fil/dijkstra"
makeGraph = (cost, min, max) => {
const sources = [];
const targets = [];
const costs = [];
for (let x = 0; x < W; ++x) {
for (let y = 0; y < W; ++y) {
for (let z = 0; z <= 1; ++z) {
for (let dir = -1; dir <= 1; dir += 2) {
let c = 0;
let x0 = x;
let y0 = y;
for (let i = 1; i <= max; ++i) {
if (z) {
y0 += dir;
if (y0 < 0 || y0 >= W) break;
} else {
x0 += dir;
if (x0 < 0 || x0 >= W) break;
}
c += cost[x0 + y0 * W];
if (i >= min) {
sources.push(((x + W * y) << 1) + z);
targets.push(((x0 + W * y0) << 1) + (1 - z));
costs.push(c);
}
}
}
}
}
}
return { sources, targets, costs };
}
graph01 = makeGraph(cost, 0, 3)
tree01 = shortest_tree({ graph: graph01, origins: [0, 1] })
answer01 = d3.min(tree01.cost.slice(-2))
tree02 = shortest_tree({ graph: makeGraph(cost, 4, 10), origins: [0, 1] })
answer02 = d3.min(tree02.cost.slice(-2))
show(tree02)
tree03 = shortest_tree({ graph: makeGraph(cost, min, max), origins: [0, 1] })
function show(tree) {
let node = d3.minIndex(tree.cost.slice(-2)) + ((W ** 2 - 1) << 1);
const path = [node];
while ((node = tree.predecessor[node]) > -1) path.push(node);
return Plot.plot({
inset: 2,
grid: true,
x: { domain: [0, W - 1] },
y: { domain: [W - 1, 0] },
color: { scheme: "blues" },
aspectRatio: 1,
marks: [
Plot.raster(cost, {
x: (_, i) => i % W,
y: (_, i) => Math.floor(i / W),
fill: Plot.identity,
interpolate: "nearest"
}),
Plot.frame(),
Plot.line(path, {
x: (i) => (i >> 1) % W,
y: (i) => Math.floor((i >> 1) / W),
stroke: "orange",
z: null
})
]
});
}
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.
