31:T400,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; }32:[{"id":"6f9d97f5aad45adc6d4c33bb4af27123347f3d57d852fb1a1e0a0bfb913b22e7a2c57b6b344d7e6319d1c3d2e206e06675138cc6ecfde1d1f28383346dd8fc21","href":"https://static.observableusercontent.com/files/6f9d97f5aad45adc6d4c33bb4af27123347f3d57d852fb1a1e0a0bfb913b22e7a2c57b6b344d7e6319d1c3d2e206e06675138cc6ecfde1d1f28383346dd8fc21","name":"input00.txt","type":"text/plain","lastModified":1670400964823.965,"size":191},{"id":"82b4f41846daca1ef5fe4f027baaea22a3c6c617747c21c4436697dfd237608b0e6acd2a2a5ce7eb405deed4a69661a29570f2f1369875810538ba15343b391c","href":"https://static.observableusercontent.com/files/82b4f41846daca1ef5fe4f027baaea22a3c6c617747c21c4436697dfd237608b0e6acd2a2a5ce7eb405deed4a69661a29570f2f1369875810538ba15343b391c","name":"input01.txt","type":"text/plain","lastModified":1670400994751.124,"size":11088}] 2f:{"title":"2022 Advent of Code • Day 07 • 💾 No Space Left On Device","cells":[{"id":0,"value":"# 2022 Advent of Code • [Day 07](https://adventofcode.com/2022/day/7) • 💾 No Space Left On Device","pinned":false,"hidden":false,"mode":"md"},{"id":376,"value":"viewof source = Inputs.radio([\"Test input\", \"Puzzle input\"], {\n label: \"Data source\",\n value: \"Test input\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":393,"value":"- Find all of the directories with a total size of at most 100,000. What is the sum of the total sizes of those directories? \n\n **Answer**: `${d3.format(\",\")(sumIf(fs))}`\n","pinned":false,"hidden":false,"mode":"md"},{"id":439,"value":" - Find the smallest directory that, if deleted, would free up enough space on the filesystem to run the update. What is the total size of that directory? \n\n Need to find closest dir to **`${d3.format(\",\")(30_000_000 - (70_000_000 - subtreeSum(fs)))}`** bytes\n \n **Answer**: `${d3.format(\",\")(sizeOfTheSubtreeThatCanBeDeleted(fs, 30_000_000 - (70_000_000 - subtreeSum(fs))))}`","pinned":false,"hidden":false,"mode":"md"},{"id":263,"value":"html`${makeList(fs)}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":472,"value":"Code for ^^ is in [one function below](https://observablehq.com/@hrbrmstr/2022-advent-of-code-day-07-no-space-left-on-device?collection=@hrbrmstr/2022-advent-of-code#makeList) and there's some CSS way at the bottom for the formatting.","pinned":false,"hidden":false,"mode":"md"},{"id":13,"value":"## Part 0","pinned":false,"hidden":false,"mode":"md"},{"id":18,"value":"This sets up both parts since we first, turn the text output into a list of commands\n\nLooks like we need to parse the mini-filesystem DSL, build a tree structure, then recursively inspect the file/dir metadata to get the sizes.\n\nAlso: _never complain about how easy a day's challenge might be, b/c it'll get you something like this the next day._","pinned":false,"hidden":false,"mode":"md"},{"id":20,"value":"commandList = (source == \"Test input\" ? input00 : input01)\n .split(/\\$/) // $ signifies the beginning of a command (we need to escape it b/c $ means eol in regex)\n .slice(1) // ^^ creates an empty first element, so remove it\n .map((line) => {\n // for each command\n const cmd = line\n .trim() // get rid of beginning/ending whitespace\n .split(/[ \\n](.*)/s) // split it into two parts by the first whitespace occurrence\n .slice(0, -1); // remove the trailing empty last element ^^ creates\n\n return cmd[0] == \"cd\" // build the commands\n ? { cmd: \"cd\", dir: cmd[1] }\n : {\n cmd: \"ls\",\n output: cmd[1].split(\"\\n\").map((ls) => ls.split(\" \")) // unmangle the directory entries\n };\n })","pinned":true,"hidden":false,"mode":"ojs"},{"id":178,"value":"Next, we gotta turn that into a proper filesystem. Just like a real filesystem, we need to preserve the parent/child directory relationships with a pointer to the previous directory for each subdir.","pinned":false,"hidden":false,"mode":"md"},{"id":114,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":183,"value":"I have not written an actual tree traversal function in _ages_. This takes a starting node and a lambda function to execute for all leaf nodes.","pinned":false,"hidden":false,"mode":"md"},{"id":163,"value":"function traverse(startNode, ƒ) {\n const recurse = (node) => {\n for (const name in node.entries) {\n if (name == \"_PARENTDIR\") continue;\n const child = node.entries[name];\n if (child.kind == \"d\") recurse(child);\n ƒ(child, name);\n }\n };\n\n recurse(startNode);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":459,"value":"Make a function that'll just give us the whole sum of a given subtree","pinned":false,"hidden":false,"mode":"md"},{"id":168,"value":"function subtreeSum(startNode) {\n var sum = 0;\n traverse(startNode, (node) => {\n if (node.kind == \"f\") sum += node.fsize;\n });\n return sum;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":461,"value":"Now we need another one that uses ^^ but limits the overall sum to just subtrees <= a given `under` specified.","pinned":false,"hidden":false,"mode":"md"},{"id":383,"value":"function sumIf(startNode, under = 100000) {\n var sum = 0;\n traverse(startNode, (node) => {\n if (node.kind == \"d\") {\n const nodeSum = subtreeSum(node);\n if (nodeSum <= under) sum += nodeSum;\n }\n });\n return sum;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":464,"value":"This is just for fun to make the directory listing.","pinned":false,"hidden":false,"mode":"md"},{"id":259,"value":"function makeList(subTree) {\n function recurse(node) {\n var ret = \"\";\n for (const name in node.entries) {\n if (name == \"_PARENTDIR\") continue;\n const child = node.entries[name];\n if (child.kind == \"d\") {\n ret += `

${`🗂️ ${name} (${d3.format(\n \",\"\n )(subtreeSum(child))})`}

\\n

\\n${recurse(\n child\n )}\\n`;\n } else {\n ret += `

📄 ${name} (${d3.format(\n \",\"\n )(child.fsize)})

`;\n }\n }\n return ret;\n }\n\n return `

${recurse(subTree)}`;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":14,"value":"## Part 1","pinned":false,"hidden":false,"mode":"md"},{"id":467,"value":"The second part is just another tree traversal. We're deleting directories, NOT FILES, so we only do the size comparison when we hit a directory and stop accumulating once we hit the target. \n\nWe compute `needToFind` up at the top of the notebook.","pinned":false,"hidden":false,"mode":"md"},{"id":420,"value":"function sizeOfTheSubtreeThatCanBeDeleted(subTree, needToFind) {\n var outSize = Number.MAX_VALUE;\n traverse(subTree, (node) => {\n if (node.kind == \"d\") {\n const currSize = subtreeSum(node);\n if (currSize < outSize && currSize >= needToFind) outSize = currSize;\n }\n });\n return outSize;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":11,"value":"## Inputs","pinned":false,"hidden":false,"mode":"md"},{"id":6,"value":"input00 = FileAttachment(\"input00.txt\").text()","pinned":false,"hidden":false,"mode":"ojs"},{"id":8,"value":"input01 = FileAttachment(\"input01.txt\").text()","pinned":false,"hidden":false,"mode":"ojs"},{"id":351,"value":"","pinned":false,"hidden":false,"mode":"html"}],"files":"$W32","stdlib":"1","titling":"auto"}