Advent of code

◂ 7 décembre 2022 ▸

  No Space Left On Device : Arborescence et taille de dossiers à calculer

$ cd /

$ ls

dir gts

68377 jvdqjhr.jvp

dir lwhbw

1. code.py

####################################################################################################
####   Le code n'est pas optimisé: on regarde la taille de tous les dossiers possibles          ####
####      alors qu'on pourrait sauter une bonne partie (sous-dossiers d'un dossier trop petit   ####
####      pour libérer de l'espace, par exemple)                                                ####  
####################################################################################################

from pprint import pprint

RACINE = []  # les chemins sont donnés par un tableau de dossiers


# crée les sous-dossiers au besoin
def getDir(arbo, chemin):
    dossier = arbo
    for nom in chemin:
        if nom not in dossier:
            dossier[nom] = {}
        dossier = dossier[nom]
    return dossier

# renvoie les sous-dossiers récursivement
def getSubsubdirs(dossier):
    chemins = []
    for nom in dossier:
        if type(dossier[nom]) == dict:
            chemins.append([nom])
            chemins.extend([ ([nom] + chemin) for chemin in getSubsubdirs(dossier[nom]) ])
    return chemins

def getSize(dossier):
    taille = 0
    for nom in dossier:
        if type(dossier[nom]) == dict:
            taille += getSize(dossier[nom])
        else:
            taille += dossier[nom]
    return taille

def createArbo(file):
    arbo = {}

    f = open(file, 'r')
    lines = [line[:-1] for line in f.readlines()]

    ici = []    # le chemin du répertoire courant
    for line in lines:
        tokens = line.split()
        if tokens[0] == '$':
            commande = tokens[1]
            if commande == 'cd':
                argument = tokens[2]
                if argument == '/':
                    ici = []
                elif argument == '..':
                    ici.pop()
                else:
                    ici.append(argument)
            elif commande != 'ls':   # être sûr qu'il n'y a que des cd et des ls
                print("ARGH !", line)   # on ne fait rien pour ls
        else:  # Résultat d'une commande ls
            if tokens[0] != 'dir':
                taille = int(tokens[0])
                nom = tokens[1]
                dossier = getDir(arbo, ici)
                dossier[nom] = taille
    return arbo


arbo = createArbo("input.txt")
pprint(arbo)   # voir si on a un truc qui ressemble à quelque chose


# Pour partie 1
LIMITE_TAILLE_PETIT_DOSSIER = 100000
tailleTotalePetitsDossiers = 0

# Pour partie 2
TAILLE_DISQUE = 70000000
ESPACE_DEJA_LIBRE = TAILLE_DISQUE - getSize(arbo)
TAILLE_BESOIN_LIBRE = 30000000
ESPACE_A_LIBERER = TAILLE_BESOIN_LIBRE - ESPACE_DEJA_LIBRE
tailleMinimaleSuffisante = None

for chemin in getSubsubdirs(arbo) + [RACINE]:
    taille = getSize(getDir(arbo, chemin))

    # partie 1
    if taille <= LIMITE_TAILLE_PETIT_DOSSIER:
        tailleTotalePetitsDossiers += taille

    # partie 2
    if taille >= ESPACE_A_LIBERER:
        if tailleMinimaleSuffisante == None or taille < tailleMinimaleSuffisante:
            tailleMinimaleSuffisante = taille

print("Réponse partie 1:", tailleTotalePetitsDossiers)
print("Réponse partie 2:", tailleMinimaleSuffisante)