1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
|
# -*- coding: utf-8 -*-
from abc import ABC
from dataclasses import dataclass, field
from enum import Enum
from typing import Set, List, Optional, Tuple, Dict, Iterator, Any
from aoc import BaseAssignment
class Action(Enum):
ls = "ls"
cd = "cd"
@dataclass(kw_only=True)
class Command:
action: Tuple[Action, List[str]]
output: Optional[List[str]]
@classmethod
def from_input(cls, input: str) -> "Command":
action, *args = input[2:].split(" ")
return Command(action=(Action(action), args), output=[])
@dataclass(kw_only=True)
class Inode(ABC):
name: str
parent: "Folder" = None
size: int = NotImplemented
@dataclass(kw_only=True)
class Folder(Inode):
children: Dict[str, Inode] = field(default_factory=dict)
@property
def size(self) -> int:
return sum([inode.size for inode in self.children.values()])
@size.setter
def size(self, value: int):
pass
def __iter__(self):
yield self
for inode in self.children.values():
if isinstance(inode, Folder):
for item in iter(inode):
yield item
else:
yield inode
@dataclass(kw_only=True)
class File(Inode):
pass
@dataclass
class FileSystem:
current: Folder = None
root: Folder = field(default_factory=lambda: Folder(name="/"))
capacity = 70000000
@classmethod
def from_commands(cls, commands: List[Command]) -> "FileSystem":
file_system = cls()
for command in commands:
file_system.parse_command(command)
return file_system
def __post_init__(self):
self.current = self.root
def parse_command(self, command: Command):
match command.action:
case [Action.ls, _]:
self.create_inodes(command.output or [])
case [Action.cd, arguments]:
self.change_directory(*arguments)
def create_inodes(self, inodes: List[str]):
for item in inodes:
size, name = item.split(" ")
inode = (
Folder(name=name, parent=self.current)
if size == "dir"
else File(name=name, parent=self.current, size=int(size))
)
if name in self.current.children:
raise Exception(f"File/Folder already exists {name}")
self.current.children[name] = inode
def change_directory(self, name: str):
match name:
case "..":
new_dir = self.current.parent
case "/":
new_dir = self.root
case name:
new_dir = self.current.children.get(name)
if new_dir is None or isinstance(new_dir, File):
raise Exception(f"No such folder {name}")
self.current = new_dir
def __iter__(self):
return iter(self.root)
@property
def free_space(self):
return self.capacity - self.root.size
class Assignment(BaseAssignment, ABC):
@staticmethod
def parse_terminal_output(output: Iterator[str]) -> List[Command]:
commands = []
command = None
for item in output:
if item.startswith("$"):
if command is not None:
commands.append(command)
command = Command.from_input(item)
else:
command.output.append(item)
if command is not None:
commands.append(command)
return commands
class AssignmentOne(Assignment):
example_result = 95437
def run(self, input: Iterator) -> Any:
commands = self.parse_terminal_output(input)
file_system = FileSystem.from_commands(commands)
items = [
inode.size
for inode in file_system
if isinstance(inode, Folder) and inode.name != "/" and inode.size <= 100000
]
return sum(items)
class AssignmentTwo(Assignment):
example_result = 24933642
def run(self, input: Iterator) -> Any:
commands = self.parse_terminal_output(input)
file_system = FileSystem.from_commands(commands)
update_size = 30000000
space_to_free = update_size - file_system.free_space
eligible_for_deletion = sorted(
[
inode
for inode in file_system
if isinstance(inode, Folder) and inode.size >= space_to_free
],
key=lambda node: node.size,
)
return eligible_for_deletion[0].size
|
