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))