-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathday07.py
More file actions
150 lines (123 loc) · 3.37 KB
/
day07.py
File metadata and controls
150 lines (123 loc) · 3.37 KB
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
# https://adventofcode.com/2022/day/7
from __future__ import annotations
import re
from dataclasses import dataclass, field
from typing import Optional
import pytest
SAMPLE = """\
$ cd /
$ ls
dir a
14848514 b.txt
8504156 c.dat
dir d
$ cd a
$ ls
dir e
29116 f
2557 g
62596 h.lst
$ cd e
$ ls
584 i
$ cd ..
$ cd ..
$ cd d
$ ls
4060174 j
8033020 d.log
5626152 d.ext
7214296 k
""".splitlines()
@dataclass
class Dir:
parent: Optional[Dir]
name: str
dirs: dict[str, Dir] = field(default_factory=dict)
files: dict[int] = field(default_factory=dict)
def total_size(self):
return sum(self.files.values()) + sum(d.total_size() for d in self.dirs.values())
def __getitem__(self, name):
here, _, more = name.partition("/")
d = self.dirs[here]
if more:
d = d[more]
return d
def print(self, indent=""):
print(f"{indent}- {self.name}")
for d in self.dirs.values():
d.print(indent + " ")
for name, size in self.files.items():
print(f"{indent} - {name}: {size}")
def walk_dirs(self):
for name, subdir in self.dirs.items():
yield name, subdir
for sname, ssubdir in subdir.walk_dirs():
yield f"{name}/{sname}", ssubdir
class RegexMatcher:
def __init__(self, text):
self.text = text
self.m = None
def __eq__(self, pattern):
self.m = re.fullmatch(pattern, self.text)
return bool(self.m)
def __getitem__(self, num):
return self.m[num]
def read_terminal_output(lines):
root = Dir(parent=None, name="")
cwd = root
for line in lines:
match m := RegexMatcher(line):
case r"\$ cd \.\.":
cwd = cwd.parent
case r"\$ cd /":
cwd = root
case r"\$ cd (\w+)":
cwd = cwd.dirs[m[1]]
case r"\$ ls":
pass
case r"dir (\w+)":
cwd.dirs[m[1]] = Dir(cwd, m[1])
case r"(\d+) ([.\w]+)":
cwd.files[m[2]] = int(m[1])
case _:
raise ValueError(f"Don't understand {line=}")
return root
@pytest.mark.parametrize("name, size", [
("a/e", 584),
("a", 94853),
("d", 24933642),
])
def test_sizes(name, size):
filesys = read_terminal_output(SAMPLE)
assert filesys[name].total_size() == size
def part1(lines):
filesys = read_terminal_output(lines)
big_sum = 0
for _, subdir in filesys.walk_dirs():
size = subdir.total_size()
if size <= 100_000:
big_sum += size
return big_sum
def test_part1():
assert part1(SAMPLE) == 95437
if __name__ == "__main__":
lines = open("day07_input.txt").read().splitlines()
print(f"Part 1: {part1(lines)}")
def find_dir_to_delete(filesys, total=70000000, need=30000000):
used = filesys.total_size()
unused = total - used
need_to_find = need - unused
candidates = []
for _, subdir in filesys.walk_dirs():
sub_total = subdir.total_size()
if sub_total > need_to_find:
candidates.append(sub_total)
return min(candidates)
def part2(lines):
return find_dir_to_delete(read_terminal_output(lines))
def test_part2():
assert part2(SAMPLE) == 24933642
if __name__ == "__main__":
lines = open("day07_input.txt").read().splitlines()
print(f"Part 2: {part2(lines)}")