Coverage for src\aoc2022\days\day7.py: 100%
78 statements
« prev ^ index » next coverage.py v7.0.0, created at 2022-12-23 05:19 +0000
1from __future__ import annotations
3from typing import Dict, Generator, List, Optional
5from src.aoc2022 import utils
8class DirectoryNode:
9 """
10 Class representing a single directory
12 :param dirname: the name of the directory
13 :type dirname: str
15 :param level: the depth of the directory in the tree structure
16 :type level: int
17 """
19 def __init__(self, dirname: str, level: int):
20 self.files: List[FileNode] = []
21 self.children: Dict[str, DirectoryNode] = {}
22 self.dirname: str = dirname
23 self.parent: Optional[DirectoryNode] = None
24 self.level: int = level
25 self.size: int = 0
27 def add_child(self, child: DirectoryNode):
28 """
29 Add a child directory to this directory
31 :param child: child directory to add
32 :type child: DirectoryNode
33 """
34 if child.dirname not in self.children:
35 self.children[child.dirname] = child
36 child.parent = self
38 def get_child(self, dirname: str):
39 """
40 Get a child directory by name
42 :param dirname: name of child directory to retrieve
43 :type dirname: str
44 """
45 return self.children[dirname]
47 def update_size(self, updated_size: int):
48 """
49 Update the size of this directory
51 :param updated_size: number of bytes to add to current size
52 :type updated_size: int
53 """
54 self.size += updated_size
55 if self.parent is not None:
56 self.parent.update_size(updated_size)
58 def add_file(self, file: FileNode):
59 """
60 Add a child file to this directory
62 :param child: child file to add
63 :type child: FileNode
64 """
65 self.files.append(file)
66 self.update_size(file.filesize)
68 def __repr__(self) -> str:
70 num_spaces_per_tab = 4
71 prefix = " " * self.level * num_spaces_per_tab
73 repr_str = f"DIR: {self.dirname} ({self.size})\n"
74 if len(self.children) > 0:
75 repr_str += f"{prefix}subdirs:\n"
76 for k, v in self.children.items():
77 repr_str += f"{prefix}- {v}\n"
78 if len(self.files) > 0:
79 repr_str += f"{prefix}files:\n"
80 for f in self.files:
81 repr_str += f"{prefix}- {f}\n"
82 return repr_str
85class FileNode:
86 """
87 Class representing a single file
89 :param filesize: the size of the file in bytes
90 :type filesize: int
92 :param filename: the name of the file
93 :type filename: str
94 """
96 def __init__(self, filesize: int, filename: str):
97 self.filesize: int = filesize
98 self.filename: str = filename
100 def __repr__(self) -> str:
101 return f"FILE : {self.filename} {self.filesize}"
104def parse_data_to_tree(raw_data: str) -> DirectoryNode:
105 """
106 Parse the raw data into a tree-structure representing the nodes and files
108 :param raw_data: Raw data containing commands
109 :type raw_data: str
111 :return: Root of the directory tree
112 :rtype: DirectoryNode
113 """
114 # get all commands, skip first line for root dir
115 lines = raw_data.split("\n")[1:]
117 root = DirectoryNode("/", 0)
118 current = root
120 # Type ignores since linting tools do not like structural pattern matching
121 for line in lines:
122 match line.split(" "): # noqa
123 case ["$", "cd", ".."]: # noqa: E211
124 current = current.parent # type: ignore
125 case ["$", "cd", "/"]: # noqa: E211
126 current = root
127 case ["$", "cd", dirname]: # noqa: E211
128 current = current.get_child(dirname) # noqa: F821
129 case ["$", "ls"]: # noqa: E211
130 pass
131 case ["dir", str(dirname)]: # noqa: E211
132 level = current.level + 1
133 child_node = DirectoryNode(dirname, level) # noqa: F821
134 current.add_child(child_node) # noqa: F821
135 case [str(num_bytes), str(filename)]: # noqa: E211
136 file_node = FileNode(int(num_bytes), filename) # noqa: F821
137 current.add_file(file_node)
138 return root
141def tree_iterator(node: DirectoryNode) -> Generator[DirectoryNode, None, None]:
142 """
143 Produces a generator for traversing the directory/file tree
145 :param node: node to traverse
146 :type node: DirectoryNode
148 :return: Generator for traversing the directory/file tree
149 :rtype: Generator[DirectoryNode]
150 """
151 yield node
152 for k, v in node.children.items():
153 yield from tree_iterator(v)
156def get_directories_under_size(root: DirectoryNode, max_size: int) -> int:
157 """
158 Calculates the sum of directory sizes for all directories with a max
159 size under the given threshold
161 :param root: root node for the directory/file tree
162 :type root: DirectoryNode
164 :param max_size: maximum allowable size for a directory to be kept
165 :type max_size: int
167 :return: sum of total sizes for directories smaller than max_size
168 :rtype: int
169 """
170 valid_dirs = [d for d in tree_iterator(root) if d.size <= max_size]
171 return sum([d.size for d in valid_dirs])
174def get_smallest_directory_to_delete(
175 root: DirectoryNode, total_space: int, needed_space: int
176) -> int:
177 """
178 Find the smallest directory to delete to free the needed space
180 :param root: root node for the directory/file tree
181 :type root: DirectoryNode
183 :param total_space: total space of the storage device
184 :type total_space: int
186 :param needed_space: amount of free space required
187 :type needed_space: int
189 :return: size of the directory to delete
190 :rtype: int
191 """
192 actual_capacity = total_space - root.size
193 missing_capacity = needed_space - actual_capacity
194 node_iter = tree_iterator(root)
195 delete_candidates = [d for d in node_iter if d.size >= missing_capacity]
196 return min([d.size for d in delete_candidates])
199if __name__ == "__main__": # pragma: no cover
201 data = utils.get_raw_data("./src/aoc2022/data/day7.txt")
203 tree_root = parse_data_to_tree(data)
205 res = get_directories_under_size(tree_root, 100_000)
207 print(f"The total size of directories under 100_000 bytes is {res}")
209 res = get_smallest_directory_to_delete(tree_root, 70_000_000, 30_000_000)
211 print(f"The size of the smallest directory that can be deleted is {res}")