Avent of Code - Day 07 - No Space Left On Device
Tags: adventofcode, programming, christmas, algorithms
Published: 2022-12-07 21:36:14

[Advent of Code](https://adventofcode.com/) 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

![image.png](https://cdn.steemitimages.com/DQmeUYJEpLbmFtJbweu13JjXehs2DMMTFj3rsJwd9R67sUx/image.png)

### Q1
```python
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
```python
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](https://helloacm.com/teaching-kids-programming-nearest-exit-from-entrance-in-maze-via-depth-first-search-algorithm/) (Recursion or Iterative) to compute the sizes for a folder.

<hr/>

### [Steem](https://steemyy.com) to the Moon!