Public
Edited
Dec 7, 2022
2 forks
1 star
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
commandList = (source == "Test input" ? input00 : input01)
.split(/\$/) // $ signifies the beginning of a command (we need to escape it b/c $ means eol in regex)
.slice(1) // ^^ creates an empty first element, so remove it
.map((line) => {
// for each command
const cmd = line
.trim() // get rid of beginning/ending whitespace
.split(/[ \n](.*)/s) // split it into two parts by the first whitespace occurrence
.slice(0, -1); // remove the trailing empty last element ^^ creates

return cmd[0] == "cd" // build the commands
? { cmd: "cd", dir: cmd[1] }
: {
cmd: "ls",
output: cmd[1].split("\n").map((ls) => ls.split(" ")) // unmangle the directory entries
};
})
Insert cell
Insert cell
fs = {
const rootNode = { kind: "d", entries: {} }; // start of directory tree
var currNode = rootNode; // current node is the start of the tree

commandList.forEach((cmd) => {
switch (cmd.cmd) {
case "cd": // if cmd is chgdir
currNode = currNode.entries[ // we don't know what crazy "cd" sequence the puzzle input will do
cmd.dir == ".." ? "_PARENTDIR" : cmd.dir // so we only add a directory entry if it doesn't exist
] ??= {
kind: "d",
entries: { ["_PARENTDIR"]: currNode }
};
break;

case "ls":
for (const output of cmd.output) {
const [sizeOrDir, fileOrDirName] = output;
currNode.entries[fileOrDirName] =
sizeOrDir == "dir" // if "ls" output entry is a directory
? { kind: "d", entries: { ["_PARENTDIR"]: currNode } } // create it with a link to parent
: { kind: "f", fsize: +sizeOrDir }; // otherwise add a file with size
}
}
});

return rootNode;
}
Insert cell
Insert cell
function traverse(startNode, ƒ) {
const recurse = (node) => {
for (const name in node.entries) {
if (name == "_PARENTDIR") continue;
const child = node.entries[name];
if (child.kind == "d") recurse(child);
ƒ(child, name);
}
};

recurse(startNode);
}
Insert cell
Insert cell
function subtreeSum(startNode) {
var sum = 0;
traverse(startNode, (node) => {
if (node.kind == "f") sum += node.fsize;
});
return sum;
}
Insert cell
Insert cell
function sumIf(startNode, under = 100000) {
var sum = 0;
traverse(startNode, (node) => {
if (node.kind == "d") {
const nodeSum = subtreeSum(node);
if (nodeSum <= under) sum += nodeSum;
}
});
return sum;
}
Insert cell
Insert cell
function makeList(subTree) {
function recurse(node) {
var ret = "";
for (const name in node.entries) {
if (name == "_PARENTDIR") continue;
const child = node.entries[name];
if (child.kind == "d") {
ret += `<li class="tree"><details open><summary>${`🗂️ ${name} <span class="size">(${d3.format(
","
)(subtreeSum(child))})</span>`}</summary>\n<ul>\n${recurse(
child
)}\n</ul>`;
} else {
ret += `<li class="tree">📄 ${name} <span class="size">(${d3.format(
","
)(child.fsize)})</span></li> `;
}
}
return ret;
}

return `<ul class="tree">${recurse(subTree)}</ul>`;
}
Insert cell
Insert cell
Insert cell
function sizeOfTheSubtreeThatCanBeDeleted(subTree, needToFind) {
var outSize = Number.MAX_VALUE;
traverse(subTree, (node) => {
if (node.kind == "d") {
const currSize = subtreeSum(node);
if (currSize < outSize && currSize >= needToFind) outSize = currSize;
}
});
return outSize;
}
Insert cell
Insert cell
Insert cell
Insert cell
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