106 lines
2 KiB
Python
106 lines
2 KiB
Python
from pathlib import *
|
|
from queue import Queue
|
|
from more_itertools import peekable
|
|
|
|
with open("07.txt") as f:
|
|
data = f.read()
|
|
ex_data = """$ 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"""
|
|
|
|
def build_fs(data):
|
|
fs = dict()
|
|
cur_dir = PosixPath("/")
|
|
it = peekable(data.splitlines())
|
|
|
|
def addfssize(dir, num):
|
|
size, children = fs[dir]
|
|
fs[dir] = (size + num, children)
|
|
|
|
while True:
|
|
try: line = next(it)
|
|
except StopIteration: break
|
|
line = line.strip()
|
|
|
|
if line.startswith("$"):
|
|
line = line.strip("$ ")
|
|
parts = line.split(" ")
|
|
cmd = parts[0]
|
|
|
|
if cmd == "cd":
|
|
path = PosixPath(parts[1])
|
|
if path.is_absolute(): cur_dir = path
|
|
else: cur_dir = cur_dir.joinpath(parts[1]).resolve()
|
|
|
|
if cur_dir not in fs: fs[cur_dir] = (0, dict())
|
|
elif cmd == "ls":
|
|
while True:
|
|
try: outline = it.peek()
|
|
except StopIteration: break
|
|
if outline.startswith("$"): break
|
|
outline = next(it)
|
|
|
|
size, name = outline.split(" ")
|
|
if size == "dir":
|
|
fs[cur_dir][1][name] = None
|
|
else:
|
|
size = int(size)
|
|
fs[cur_dir][1][name] = size
|
|
|
|
dir = cur_dir
|
|
while dir.parent != dir:
|
|
addfssize(dir, size)
|
|
dir = dir.parent
|
|
addfssize(dir, size)
|
|
|
|
return fs
|
|
|
|
def solve1(data):
|
|
fs = build_fs(data)
|
|
|
|
sum = 0
|
|
for dir, (size, children) in fs.items():
|
|
if size <= 100000:
|
|
sum += size
|
|
print(sum)
|
|
|
|
def solve2(data):
|
|
fs = build_fs(data)
|
|
|
|
needed_space = 30000000
|
|
free_space = 70000000 - fs[PosixPath("/")][0]
|
|
remaining_space = needed_space - free_space
|
|
|
|
ans = needed_space + 1
|
|
|
|
for dir, (size, children) in fs.items():
|
|
if size >= remaining_space:
|
|
ans = min(ans, size)
|
|
|
|
print(ans)
|
|
|
|
solve1(ex_data)
|
|
solve1(data)
|
|
|
|
solve2(ex_data)
|
|
solve2(data)
|