Developer @Observable
parse = (s) =>
s
.split(/\s*\$\s*/g)
.filter((l) => l.length)
.map((l) => {
let [cmd, ...output] = l.split("\n");
return { cmd: cmd.split(" "), output: output.map((d) => d.split(" ")) };
})
buildTree = (input) => {
const makeDir = (parent) => ({
parent,
type: "dir",
totalSize: 0,
children: {}
});
const makeFile = (size) => ({ type: "file", size });
let root = makeDir(null);
let pwd = [];
const getPwd = () => {
let dir = root;
for (const seg of pwd) dir = dir.children[seg];
return dir;
};
const addChild = (name, entry) => {
let dir = getPwd();
dir.children[name] = entry;
if (entry.type === "file") {
while (dir) {
dir.totalSize += entry.size;
dir = dir.parent;
}
}
};
for (const { cmd, output } of input) {
if (cmd[0] === "cd") {
if (cmd[1] === "/") pwd = [];
else if (cmd[1] === "..") pwd.pop();
else pwd.push(cmd[1]);
} else if (cmd[0] === "ls") {
for (let [a, b] of output) {
if (a === "dir") addChild(b, makeDir(getPwd()));
else addChild(b, makeFile(+a));
}
}
}
return root;
}
function* filterTree(tree, predicate) {
let queue = [tree];
let matches = [];
while (queue.length) {
let next = queue.shift();
if (next.type === "dir") {
if (predicate(next)) yield next;
for (const ch of Object.values(next.children)) queue.push(ch);
}
}
}
function part1(input) {
let tree = buildTree(input);
return d3.sum(
filterTree(tree, (d) => d.totalSize <= 100_000),
(d) => d.totalSize
);
}
function part2(input) {
let tree = buildTree(input);
let total = 70000000;
let needed = 30000000;
let toDelete = needed - (total - tree.totalSize);
return d3.min(
filterTree(tree, (d) => d.totalSize >= toDelete),
(d) => d.totalSize
);
}
meta = aoc.meta({
day: 7,
parse,
inputs,
parts: [part1, part2],
expected: { test: [95437, 24933642], real: [1886043, 3842121] },
href: "https://observablehq.com/d/079c111225d0b6f3?collection=@mythmon/advent-of-code-2022"
})
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.
