Advent of Code 2022 - Day 7: No Space Left On Device Solution

Part 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": 584
10    }
11  },
12  "d": {
13    "j": 4060174,
14    "d.log": 8033020,
15    "d.ext": 5626152,
16    "k": 7214296
17  }
18}

Flatten into format of path-with-size

1{
2  "./a/e": 584,
3  "./a": 94853,
4  "./d": 24933642,
5  ".": 48381165
6}

Grab the sizes that less or equal than 100000

Implementation

1const fs = require("fs")
2
3const readData = () => {
4  const setPath = (path, value, obj) => {
5    let iter = obj
6    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]] = value
13  }
14
15  const data = fs.readFileSync("./input", "utf-8").split(/\r?\n/)
16
17  const treeData = {}
18  let i = 0
19  let currentPath = []
20
21  while (data[i]) {
22    const tokens = data[i].split(" ")
23
24    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 nothing
36    } else {
37      setPath([...currentPath, tokens[1]], Number(tokens[0]), treeData)
38    }
39
40    i++
41  }
42
43  // uncomment for viewing tree
44  // console.log(JSON.stringify(treeData, null, 2))
45
46  return treeData
47}
48
49const main = () => {
50  const AT_MOST = 100000
51  const treeData = readData()
52  const folderSizes = {}
53
54  const calculateSize = (obj, currentPath = ["."]) => {
55    let size = 0
56
57    for (const [key, value] of Object.entries(obj)) {
58      size +=
59        typeof value === "object"
60          ? calculateSize(value, [...currentPath, key])
61          : value
62    }
63
64    folderSizes[currentPath.join("/")] = size
65
66    return size
67  }
68
69  calculateSize(treeData)
70
71  const res = Object.values(folderSizes)
72    .filter(size => size <= AT_MOST)
73    .reduce((acc, el) => acc + el, 0)
74
75  console.log(res)
76}
77
78main()

Part 2

Calculate minimumRequiredSpace

The result is the first size that is greater than minimumRequiredSpace, in the ascending-sorted sizes

Implementation

1const fs = require("fs")
2
3const readData = () => {
4  const setPath = (path, value, obj) => {
5    let iter = obj
6    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]] = value
13  }
14
15  const data = fs.readFileSync("./input", "utf-8").split(/\r?\n/)
16
17  const treeData = {}
18  let i = 0
19  let currentPath = []
20
21  while (data[i]) {
22    const tokens = data[i].split(" ")
23
24    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 nothing
36    } else {
37      setPath([...currentPath, tokens[1]], Number(tokens[0]), treeData)
38    }
39
40    i++
41  }
42
43  // uncomment for viewing tree
44  // console.log(JSON.stringify(treeData, null, 2))
45
46  return treeData
47}
48
49const main = () => {
50  const treeData = readData()
51  const folderSizes = {}
52
53  const calculateSize = (obj, currentPath = ["."]) => {
54    let size = 0
55
56    for (const [key, value] of Object.entries(obj)) {
57      size +=
58        typeof value === "object"
59          ? calculateSize(value, [...currentPath, key])
60          : value
61    }
62
63    folderSizes[currentPath.join("/")] = size
64
65    return size
66  }
67
68  calculateSize(treeData)
69
70  const minimumRequiredSpace = 30000000 - (70000000 - folderSizes["."])
71
72  const res = Object.values(folderSizes)
73    .sort((a, b) => a - b)
74    .filter(size => size >= minimumRequiredSpace)[0]
75
76  console.log(res)
77}
78
79main()

References

Original problem