Public
Edited
Dec 7, 2022
1 fork
1 star
Insert cell
Insert cell
Insert cell
testCommands = parseTerminal(test)
Insert cell
function parseTerminal(input) {
const commands = [];
for (const command of input.trim().slice(2).split(/^|\n\$ /)) {
commands.push(parseCommand(command));
}
return commands;
}
Insert cell
function parseCommand(input) {
const match = /^(?<name>\w+)(?: (?<param>\S+))?$/m.exec(input);
if (!match) throw new Error(`invalid command: ${input}`);
const {groups: {name, param}} = match;
switch (name) {
case "cd": return {name: "cd", path: param};
case "ls": return {name: "ls", output: input.split("\n").slice(1).map(parseLsEntry)};
default: throw new Error(`unexpected command: ${name}`);
}
}
Insert cell
function parseLsEntry(input) {
return input.split(/\s+/);
}
Insert cell
Insert cell
testTree = buildTree(testCommands)
Insert cell
function buildTree(commands) {
const root = {type: "dir", children: {}};
let node = root;
for (const command of commands) {
switch (command.name) {
case "cd":
node = (node.children[command.path] ??= {type: "dir", children: {[".."]: node}});
break;
case "ls":
for (const [size, name] of command.output) {
node.children[name] = size === "dir" ? {type: "dir", children: {[".."]: node}} : {type: "file", size: +size};
}
break;
}
}
return root;
}
Insert cell
visualizeTree(testTree, {width, height: 140})
Insert cell
visualizeTree(tree, {width, height: 3600})
Insert cell
function visualizeTree(tree, {inset = 10, insetLeft = 10, insetRight = 160, ...options} = {}) {
const nodes = [];

(function recurse(node, names) {
for (const name in node.children) {
if (name === "..") continue;
const child = node.children[name];
if (child.type === "dir") recurse(child, names.concat(name));
nodes.push({
name: name,
path: names.concat(name).join("/"),
size: child.type === "dir" ? sumTree(child) : child.size
});
}
})(tree, []);

return Plot.plot({
axis: null,
inset,
insetLeft,
insetRight,
...options,
marks: [
Plot.tree(nodes, {
path: "path",
text: d => `${d.name} ${d.size.toLocaleString("en")}`
})
]
});
}
Insert cell
sumTree(testTree)
Insert cell
limitedSumTree(testTree)
Insert cell
function limitedSumTree(tree) {
let sum = 0;
visitTree(tree, (node) => {
if (node.type === "dir") {
const nodeSum = sumTree(node);
if (nodeSum <= 100000) {
sum += nodeSum;
}
}
});
return sum;
}
Insert cell
function sumTree(tree) {
let sum = 0;
visitTree(tree, (node) => {
if (node.type === "file") {
sum += node.size;
}
});
return sum;
}
Insert cell
function visitTree(tree, visit) {
(function recurse(node) {
for (const name in node.children) {
if (name === "..") continue;
const child = node.children[name];
if (child.type === "dir") recurse(child);
visit(child);
}
})(tree);
}
Insert cell
input = FileAttachment("input.txt").text()
Insert cell
commands = parseTerminal(input)
Insert cell
tree = buildTree(commands)
Insert cell
limitedSumTree(tree)
Insert cell
Insert cell
findSmallestLargeNode(testTree, 8381165)
Insert cell
findSmallestLargeNode(tree, 358913)
Insert cell
30000000 - (70000000 - sumTree(testTree))
Insert cell
30000000 - (70000000 - sumTree(tree))
Insert cell
function findSmallestLargeNode(tree, minSize) {
let best;
let bestSize = Infinity;
visitTree(tree, (node) => {
if (node.type === "dir") {
const nodeSize = sumTree(node);
if (nodeSize < bestSize && nodeSize >= minSize) {
best = node;
bestSize = nodeSize;
}
}
});
return [best, bestSize];
}
Insert cell

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.
Learn more