DoctorLai

Posted on

# Avent of Code - Day 07 - No Space Left On Device

Advent of Code occurs at Dec 01 to 25 where each day, you will need to solve a puzzle. It is Festival and the problem statement is mostly related to Christmas.

## Day 07 - No Space Left On Device

### Q1

``````import sys
from collections import defaultdict, deque

file1 = open(sys.argv[1], "r")

data = defaultdict(int)
path = defaultdict(list)

cur = ['/']
mode = False

while True:
if not line:
break
arr = line.split()
if arr[0] == '\$':
if arr[1] == 'cd':
if arr[2] == '/':
cur = ['/']
elif arr[2] == '..':
cur.pop()
else:
cur.append(arr[2])
mode = False
elif arr[1] == 'ls':
mode = True
elif mode:
size, filename = arr
filepath = ("/".join(cur) + "/" + filename).replace("//", "/")
folder = "/".join(cur).replace("//", "/")
if size != "dir":
data[filepath] = int(size)
path[folder].append(filename)

print(data)
print(path)

N=100000
ans = 0

def dfs(root):
root = root.replace("//", "/")
print(root)
if root not in path:
return 0

cur = data[root]
for i in path[root]:
p = root + "/" + i
if p in data:
cur += data[p]
else:
cur += dfs(p)

global ans, N
if cur <= N:
ans += cur
return cur

dfs("/")
print(ans)
``````

### Q2

``````import sys
from math import inf
from collections import defaultdict, deque
from functools import *

file1 = open(sys.argv[1], "r")

data = defaultdict(int)
path = defaultdict(list)

cur = ['/']
mode = False

while True:
if not line:
break
arr = line.split()
if arr[0] == '\$':
if arr[1] == 'cd':
if arr[2] == '/':
cur = ['/']
elif arr[2] == '..':
cur.pop()
else:
cur.append(arr[2])
mode = False
elif arr[1] == 'ls':
mode = True
elif mode:
size, filename = arr
filepath = ("/".join(cur) + "/" + filename).replace("//", "/")
folder = "/".join(cur).replace("//", "/")
if size != "dir":
data[filepath] = int(size)
path[folder].append(filename)

path[""].append("/")

print(data)
print(path)

total =      70000000
min_unused = 30000000
ans = inf
name = ""
#@lru_cache(None)
def dfs(root):
root = root.replace("//", "/")
if root not in path:
return 0

cur = data[root]
for i in path[root]:
p = root + "/" + i
if p in data:
cur += data[p]
else:
cur += dfs(p)

global unused, min_unused, ans, name
if unused + cur >= min_unused:
if cur < ans:
ans = cur
name = root

return cur

total_size = sum(data.values())
unused = total - total_size
dfs("/")

print(f"total_size = {total_size}")

print(ans, name)
``````

Handling input is not trivial. Need to record the structures and sizes in two different dictionary/hash-maps. And we need to perform Depth First Search Algorithm (Recursion or Iterative) to compute the sizes for a folder.

## π Friends don't let friends browse without dark mode.

Sorry, it's true.