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
https://adventofcode.com/2022/day/7
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:
line = file1.readline().strip()
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:
line = file1.readline().strip()
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.