44 lines
1.2 KiB
Python
44 lines
1.2 KiB
Python
|
#/usr/bin/env python
|
||
|
|
|
||
|
|
from collections import defaultdict
|
||
|
|
import re
|
||
|
|
|
||
|
|
RE_CMD = re.compile(r"^\$ (ls|cd)(.*)$")
|
||
|
|
RE_LS_DIR = re.compile(r"^dir (.*)$")
|
||
|
|
RE_LS_FILE = re.compile(r"^(\d+) (.*)$")
|
||
|
|
|
||
|
|
sizes = defaultdict(int)
|
||
|
|
dir_cur = "/"
|
||
|
|
size_unused = 30000000
|
||
|
|
size_total = 70000000
|
||
|
|
|
||
|
|
with open("input.txt", "r") as f:
|
||
|
|
for line in f:
|
||
|
|
line = line.strip()
|
||
|
|
m = RE_LS_FILE.match(line)
|
||
|
|
if m:
|
||
|
|
sizes[dir_cur] += int(m.group(1))
|
||
|
|
continue
|
||
|
|
m = RE_CMD.match(line)
|
||
|
|
if m and m.group(1) == 'cd':
|
||
|
|
cd_args = m.group(2).strip()
|
||
|
|
if cd_args == '..':
|
||
|
|
dir_cur = "/".join(dir_cur.split("/")[:-2])+"/"
|
||
|
|
elif cd_args == "/":
|
||
|
|
dir_cur = "/"
|
||
|
|
else:
|
||
|
|
dir_cur += cd_args + "/"
|
||
|
|
continue
|
||
|
|
|
||
|
|
#not very optimal ;( recursion and tree build will be faster
|
||
|
|
sizes_total = defaultdict(int)
|
||
|
|
for dir in (sorted(sizes.keys(), key=len, reverse=True)):
|
||
|
|
tokens = dir.split("/")[:-1]
|
||
|
|
for i in range(1, len(tokens)+1):
|
||
|
|
x = "/".join(tokens[:i])+"/"
|
||
|
|
sizes_total[x] += sizes[dir]
|
||
|
|
|
||
|
|
|
||
|
|
size_required = size_unused - (size_total - sizes_total["/"])
|
||
|
|
print(min([x for x in sizes_total.values() if x >= size_required]))
|