Advent of Code 2022 - Day 7: No Space Left On Device Solution
Recursive traversalPart 1
Transform the data into this hierarchy
1{2 "b.txt": 14848514,3 "c.dat": 8504156,4 "a": {5 "f": 29116,6 "g": 2557,7 "h.lst": 62596,8 "e": {9 "i": 58410 }11 },12 "d": {13 "j": 4060174,14 "d.log": 8033020,15 "d.ext": 5626152,16 "k": 721429617 }18}
Flatten into format of path-with-size
1{2 "./a/e": 584,3 "./a": 94853,4 "./d": 24933642,5 ".": 483811656}
Grab the sizes that less or equal than
100000
Implementation
1const fs = require("fs")23const readData = () => {4 const setPath = (path, value, obj) => {5 let iter = obj6 for (const folder of path.slice(0, -1)) {7 if (!iter[folder]) {8 iter[folder] = {}9 }10 iter = iter[folder]11 }12 iter[path.slice(-1)[0]] = value13 }1415 const data = fs.readFileSync("./input", "utf-8").split(/\r?\n/)1617 const treeData = {}18 let i = 019 let currentPath = []2021 while (data[i]) {22 const tokens = data[i].split(" ")2324 if (tokens[0] === "$") {25 if (tokens[1] === "cd") {26 if (tokens[2] === "/") {27 currentPath = []28 } else if (tokens[2] === "..") {29 currentPath.pop()30 } else {31 currentPath.push(tokens[2])32 }33 }34 } else if (tokens[0] === "dir") {35 // do nothing36 } else {37 setPath([...currentPath, tokens[1]], Number(tokens[0]), treeData)38 }3940 i++41 }4243 // uncomment for viewing tree44 // console.log(JSON.stringify(treeData, null, 2))4546 return treeData47}4849const main = () => {50 const AT_MOST = 10000051 const treeData = readData()52 const folderSizes = {}5354 const calculateSize = (obj, currentPath = ["."]) => {55 let size = 05657 for (const [key, value] of Object.entries(obj)) {58 size +=59 typeof value === "object"60 ? calculateSize(value, [...currentPath, key])61 : value62 }6364 folderSizes[currentPath.join("/")] = size6566 return size67 }6869 calculateSize(treeData)7071 const res = Object.values(folderSizes)72 .filter(size => size <= AT_MOST)73 .reduce((acc, el) => acc + el, 0)7475 console.log(res)76}7778main()
Part 2
Calculate
minimumRequiredSpace
The result is the first size that is greater than
minimumRequiredSpace
, in the ascending-sorted sizesImplementation
1const fs = require("fs")23const readData = () => {4 const setPath = (path, value, obj) => {5 let iter = obj6 for (const folder of path.slice(0, -1)) {7 if (!iter[folder]) {8 iter[folder] = {}9 }10 iter = iter[folder]11 }12 iter[path.slice(-1)[0]] = value13 }1415 const data = fs.readFileSync("./input", "utf-8").split(/\r?\n/)1617 const treeData = {}18 let i = 019 let currentPath = []2021 while (data[i]) {22 const tokens = data[i].split(" ")2324 if (tokens[0] === "$") {25 if (tokens[1] === "cd") {26 if (tokens[2] === "/") {27 currentPath = []28 } else if (tokens[2] === "..") {29 currentPath.pop()30 } else {31 currentPath.push(tokens[2])32 }33 }34 } else if (tokens[0] === "dir") {35 // do nothing36 } else {37 setPath([...currentPath, tokens[1]], Number(tokens[0]), treeData)38 }3940 i++41 }4243 // uncomment for viewing tree44 // console.log(JSON.stringify(treeData, null, 2))4546 return treeData47}4849const main = () => {50 const treeData = readData()51 const folderSizes = {}5253 const calculateSize = (obj, currentPath = ["."]) => {54 let size = 05556 for (const [key, value] of Object.entries(obj)) {57 size +=58 typeof value === "object"59 ? calculateSize(value, [...currentPath, key])60 : value61 }6263 folderSizes[currentPath.join("/")] = size6465 return size66 }6768 calculateSize(treeData)6970 const minimumRequiredSpace = 30000000 - (70000000 - folderSizes["."])7172 const res = Object.values(folderSizes)73 .sort((a, b) => a - b)74 .filter(size => size >= minimumRequiredSpace)[0]7576 console.log(res)77}7879main()
References
Comments
Loading comments...
Tags
adventofcode
recursion
Apply and earn a $2,500 bonus once you're hired on your first job!
Clients from the Fortune 500 to Silicon Valley startups
Choose your own rate, get paid on time
From hourly, part-time, to full-time positions
Flexible remote working environment
A lot of open JavaScript jobs!!
Fact corner: Referred talent are 5x more likely to pass the Toptal screening process than the average applicant.
Still hesitate? Read HoningJS author's guide on dealing with Toptal interview process.