days 1-7

1 files changed, 93 insertions, 0 deletions

diff --git a/7.py b/7.py
new file mode 100644
index 0000000..22150f0
--- /dev/null
+++ b/7.py
@@ -0,0 +1,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))