Avent of Code - Day 07 - No Space Left On DevicesteemCreated with Sketch.

in #adventofcodelast year (edited)

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

image.png

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.


Steem to the Moon!

Coin Marketplace

STEEM 0.36
TRX 0.12
JST 0.039
BTC 69965.85
ETH 3540.49
USDT 1.00
SBD 4.71