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
|
from __future__ import annotations
from dataclasses import dataclass
@dataclass
class File:
size: int
@dataclass
class Directory:
up: Directory
entries: dict[str, File|Directory]
def __init__(self, up=None):
self.up = up if up else self
self.entries = dict()
def __getitem__(self, key):
match key:
case '..':
return self.up
case '.':
return self
case d:
return self.entries[d]
def __setitem__(self, key, value):
self.entries[key] = value
def get(self, key, default=None):
try:
return self[key]
except KeyError:
return default
with open('7.in.test') as f:
inp = [tuple(line.rstrip().split()) for line in f]
root = Directory()
pwd = root
for line in inp:
match line:
case ['$', 'cd', d]:
match d:
case '/': pwd = root
case d:
pwd = pwd[d]
assert(isinstance(pwd, Directory))
case ['$', 'ls']:
continue
case ['dir', name]:
pwd[name] = Directory(pwd)
case [size, name]:
pwd[name] = File(int(size))
dirsizes = dict()
def getsize(d: Directory, path=tuple()) -> int:
if path in dirsizes:
return dirsizes[path]
size = 0
for k, e in d.entries.items():
match e:
case File(s):
size += s
case Directory(_, _) as d:
size += getsize(d, path + (k,))
dirsizes[size] = size
return size
def part1(root):
answer = 0
def solve(d, path=tuple()):
nonlocal answer
for k, e in d.entries.items():
if isinstance(e, Directory):
solve(e, path + (k,))
size = getsize(d, path)
if size <= 100000:
answer += size
solve(root)
return answer
def part2(root):
used = getsize(root)
unused = 70000000 - used
need = 30000000 - unused
smallest = used
def solve(d, path=tuple()):
nonlocal smallest
for k, e in d.entries.items():
if isinstance(e, Directory):
solve(e, path + (k,))
size = getsize(d, path)
if size >= need and size < smallest:
smallest = size
solve(root)
return smallest
print(part1(root))
print(part2(root))
|
