Day 25: Full of Hot AirDay 24: Blizzard BasinDay 23: Unstable DiffusionDay 22: Monkey MapDay 21: Monkey MathDay 20: Grove Positioning SystemDay 19: Not Enough MineralsDay 18: Boiling BouldersDay 17: Pyroclastic FlowDay 16: Proboscidea VolcaniumDay 15: Beacon Exclusion ZoneDay 14: Regolith ReservoirDay 13: Distress SignalDay 11: Monkey in the MiddleDay 10: Cathode-Ray TubeDay 9: Rope BridgeDay 8: Treetop Tree HouseDay 7: No Space Left On DeviceDay 6: Tuning TroubleDay 5: Supply StacksDay 4: Camp CleanupDay 3: Rucksack ReorganizationDay 2: Rock Paper ScissorsDay 1: Calorie CountingAdvent of Code Leaderboard
Day 12: Hill Climbing Algorithm
path = (paths, start, end) => {
let p = d3.least(paths.keys(), ([x, y]) => Math.hypot(end[0] - x, end[1] - y));
const path = [p];
while (path[0][0] !== start[0] || path[0][1] !== start[1])
path.unshift((p = paths.get(p)));
return path;
}
// part2 = starts
// .map((p) => {
// const result = d3.filter(djikstra(p, end), (d) => d.done)[0];
// return [p, result && result.distances.get(end)];
// })
// .filter((d) => d[1])
// .sort((a, b) => a[1] - b[1])
Plot.plot({
marks: [
Plot.cell(map, {
x: ([[x, y]]) => x,
y: ([[x, y]]) => y,
fill: ([_, c]) => c,
inset: -1
}),
Plot.cell(part2.distances, {
x: ([[x, y]]) => x,
y: ([[x, y]]) => y,
fill: ([_, c]) => c,
inset: -1
}),
Plot.line(path(part2.paths, end, start), { stroke: "white" })
],
width,
aspectRatio: 1,
x: { axis: false },
y: { axis: false }
})
part2.distances.get(starts[0])
part2 = d3.filter(djikstra2(end, start), d => d.done)[0]
function* djikstra2(start, [ex, ey]) {
const seen = new d3.InternSet([], JSON.stringify);
const next = new d3.InternSet([], JSON.stringify);
const distances = new d3.InternMap([[start, 0]], JSON.stringify);
const paths = new d3.InternMap([], JSON.stringify);
let p = start;
while (p && (p[0] !== ex || p[1] !== ey)) {
for (const n of neighbors2(p)) {
if (seen.has(n)) continue;
const d = distances.get(p) + 1;
if (!distances.has(n) || d < distances.get(n)) {
distances.set(n, d);
paths.set(n, p);
}
next.add(n);
}
seen.add(p);
p = d3.least(
d3.filter(next, ([p]) => !seen.has(p)),
(a, b) => distances.get(a) - distances.get(b)
);
next.delete(p);
yield { seen, distances, paths };
}
yield { seen, distances, paths, done: !!p };
}
function* neighbors2([x, y]) {
for (const p of [
[x - 1, y],
[x + 1, y],
[x, y - 1],
[x, y + 1]
])
if (map.has(p) && map.get(p) >= map.get([x, y]) - 1) yield p;
}
starts = d3.filter(map.entries(), ([p, h]) => h === 0).map(([p]) => p)
part1.distances.get(end)
part1 = {
play;
const frame = 100;
for (const step of djikstra(start, end))
if (step.seen.size % frame === 0 || step.done) yield step;
}
function* djikstra(start, [ex, ey]) {
const seen = new d3.InternSet([], JSON.stringify);
const next = new d3.InternSet([], JSON.stringify);
const distances = new d3.InternMap([[start, 0]], JSON.stringify);
const paths = new d3.InternMap([], JSON.stringify);
let p = start;
while (p && (p[0] !== ex || p[1] !== ey)) {
for (const n of neighbors(p)) {
if (seen.has(n)) continue;
const d = distances.get(p) + 1;
if (!distances.has(n) || d < distances.get(n)) {
distances.set(n, d);
paths.set(n, p);
}
next.add(n);
}
seen.add(p);
p = d3.least(
d3.filter(next, ([p]) => !seen.has(p)),
(a, b) => distances.get(a) - distances.get(b)
);
next.delete(p);
yield { seen, distances, paths };
}
yield { seen, distances, paths, done: !!p };
}
function* neighbors([x, y]) {
for (const p of [
[x - 1, y],
[x + 1, y],
[x, y - 1],
[x, y + 1]
])
if (map.has(p) && map.get(p) <= map.get([x, y]) + 1) yield p;
}
map = parsed.map
end = parsed.end
start = parsed.start
parsed = {
let start, end;
const map = new d3.InternMap(
data
.trim()
.split("\n")
.flatMap((l, y) =>
[...l].map((h, x) => {
const p = [x, y];
if (h === "S") start = p;
else if (h === "E") end = p;
return [p, h.charCodeAt(0) - a];
})
),
JSON.stringify
);
map.set(start, 0);
map.set(end, z - a);
return { map, start, end };
}
a = "a".charCodeAt(0)
z = "z".charCodeAt(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.
