Forum Programmation.autre Avent du Code, jour 7

Posté par  (site web personnel) . Licence CC By‑SA.
Étiquettes :
4
7
déc.
2022

Avent du Code, jour 7.

Personne ne nous a rien demandé, mais parce que personne ne résiste à une bonne vieille mise à jour système, il faut absolument mettre à jour le transmetteur défectueux que les lutins nous ont refilé. Seulement, pour ça, il faut faire un peu de place dans son système de fichiers.

  • # En Python

    Posté par  (site web personnel) . Évalué à 5.

    Ça commence à devenir un tout petit peu sérieux. Aucune vraie difficulté à comprendre ou à implémenter le problème, mais on commence à sortir des trucs un peu récursifs.

    En bon unixien, je considère bien sûr qu'un répertoire est un type particulier de fichier, qu'il contient toujours une vraie entrée .., et que le nom d'un fichier n'est pas une propriété intrinsèque mais simplement un nom qu'il porte dans une entrée de répertoire.

    # Advent of Code 2022, day 7

from __future__ import annotations

import re

from enum import Enum
from typing import Dict, Iterable, Iterator, Optional, Tuple


class File:
    def __init__(self, size: int):
        self.size = size


class RegularFile(File):
    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)


class Directory(File):
    def __init__(self, parent: Optional[Directory] = None):
        if parent is None:
            # root directory
            parent = self
        self.files = {'..': parent}  # type: Dict[str, File]
        self._size = None            # type: Optional[int]

    @property
    # https://github.com/python/mypy/issues/4125
    def size(self) -> int:  # type: ignore
        if self._size is None:
            self._size = sum(f.size for name, f in self.files.items()
                             if name != '..')
        # mypy does not realize self._size can no longer be None
        return self._size  # type: ignore

    def add(self, name, f: File) -> None:
        self.files[name] = f

    def dirs(self) -> Iterator[Directory]:
        yield self
        for name, f in self.files.items():
            if isinstance(f, Directory) and name != '..':
                yield from f.dirs()


class State:
    re_cd = re.compile(r'^\$ cd (.*)\n?$')
    re_ls = re.compile(r'^\$ ls\n?$')
    re_reg = re.compile(r'^(\d+) (.*)\n?$')  # regular file
    re_dir = re.compile(r'^dir (.*)\n?$')

    def __init__(self, root: Directory):
        self.root = root
        self.cwd = root
        self.in_ls = False

    def cd(self, name: str) -> None:
        # Only 'cd /' or 'cd subdir'!
        if name == '/':
            self.cwd = self.root
        else:
            target = self.cwd.files[name]
            if isinstance(target, Directory):
                self.cwd = target
            else:
                raise ValueError('cannot cd to a regular file')

    def input(self, line: str) -> None:
        if (m := self.re_cd.match(line)) is not None:
            self.in_ls = False
            self.cd(m.group(1))
        elif (m := self.re_ls.match(line)) is not None:
            self.in_ls = True
        elif self.in_ls and (m := self.re_reg.match(line)) is not None:
            size = int(m.group(1))
            name = m.group(2)
            self.cwd.add(name, RegularFile(size))
        elif self.in_ls and (m := self.re_dir.match(line)) is not None:
            name = m.group(1)
            self.cwd.add(name, Directory(parent=self.cwd))
        else:
            raise ValueError("unexpected line '{}'".format(line.rstrip()))


def import_tree(lines: Iterable[str]) -> Directory:
    root = Directory()
    state = State(root)
    for line in lines:
        state.input(line)
    return root


def solve_both(lines: Iterable[str]) -> Tuple[int, int]:
    """Solve both parts of today's puzzle"""
    root = import_tree(lines)
    result1 = sum(d.size for d in root.dirs() if d.size <= 100000)

    total = 70000000   # total storage space
    needed = 30000000  # storage space needed for system update
    used = root.size   # used storage space
    available = total - used      # currently available storage space
    to_free   = needed - available  # storage space to free
    result2 = min(d.size for d in root.dirs() if d.size >= to_free)

    return result1, result2

    • [^] # Re: En Python

      Posté par  . Évalué à 3.

      En bon unixien

      En bon unixien, un répertoire pèse en lui même 4096 octets, à ajouter à son contenu. Et un fichier est arrondi aux 4Ko supérieurs. Ça changerai sûrement la réponse. 😆

    • [^] # Re: En Python

      Posté par  . Évalué à 2.

      J'ai fait une solution assez similaire, en plus crade (pas d'heritage, de typing etc.).
      Et surtout pas de yield dans la fonction recursive qui aplatit les repertoires (je copie les references dans une nouvelle list). J'avoue que ta solution est plus elegante, et c'est marrant que tu fasses du code presque prod ready (mypy…).
      Perso je commence les problemes quand j'ai du temps dans la soiree, mais une fois que j'ai commence j'essaye de trouver la reponse le plus rapidement possible.

      Excusez l'absence d'accents dans mes commentaires, j'habite en Australie et n'ai pas de clavier francais sous la main.

      • [^] # Re: En Python

        Posté par  (site web personnel) . Évalué à 5.

        Et surtout pas de yield dans la fonction recursive qui aplatit les repertoires (je copie les references dans une nouvelle list). J'avoue que ta solution est plus elegante, et c'est marrant que tu fasses du code presque prod ready (mypy…).

        Je profite en fait de l'AoC pour découvrir les fonctionnalités de typage de Python. Une fois passé l'apprentissage, qui n'est vraiment pas horrible, ça ne fait pas perdre du temps, au contraire, ça permet de détecter certaines erreurs de façon bien plus rapide et de mieux identifier d'où elles viennent.

    • [^] # Re: En Python

      Posté par  (Mastodon) . Évalué à 3.

      Et un peu d'utilisation de fonction magiques chez moi ici :

      class Directory:
    def __getitem__(self, name):
        return self.files[name]

      Et là pour chopper le sous-répertoire "toto" de mon Directory(truc) je fais truc['toto'].
      Je n'ai même pas pensé à inclure le '..' dans mes fichiers, j'ai un cas particulier si on fait cd .., c'était tellement évident de faire ça !

      On pourrait accéder à truc/toto via truc.toto en implémentant __getattr__ comme j'ai fait le __getitem__, mais si "toto" est dans une variable il faut faire getattr(truc, variable_toto), ça ne simplifie pas la lecture, c'est plus simple d'utiliser truc[variable_toto].

      Après on peut implémenter __truediv__ et faire que truc/"toto" retourne Directory(truc/toto).
      Là on a root/"a"/"b"/".."/"c"/".."/".."/"e"/"f" = Directory("/e/f") :)
      Mais les guillemets partout alourdissent la lecture et l'écriture…

      Sinon, côté algo, et même implémentation, c'est pareil rien à signaler, pas de subtilité, j'ai juste utilisé du if line.startswith("$ cd"): cwd = cwd[line[5:]] plutôt qu'une regexp.

      • Yth.

  • # un bout de AWK

    Posté par  . Évalué à 3. Dernière modification le 07 décembre 2022 à 11:12.

    Comme le FS est parcourus "en profondeur d'abord" et dans l'ordre, pas besoin d'une structure de données trop compliquée type arbre, une simple liste suffit.

    partie 1

    BEGIN { LIMIT=100*1000 }
$2 == "ls" || $1 == "dir" { next}
$2 == "cd" && $3 == ".." { # on monte
    if (S[depth]<=LIMIT) {   # <= "at most" !!!!!!!!!
        R+=S[depth]
    }
    S[depth]=0   # ne pas oublier le reset du précédent cousin
    depth -= 1
}
$2 == "cd" && $3 != ".." { depth += 1; P[depth]=$3; }  # on descend
NF == 2 {  # fichier
    for (i=1;i<=depth;i++) {
        S[i]+=$1
    }
}
END { print R }

    J'ai perdu au moins une demie heure sur le fait que j'ai interprété "at most" en "au moins" car j'imaginais chercher des trucs gros (on veut libérer de la place). Alors que c'est "au plus" ; GRRR ; Bien lire l'énoncée sans faire d'hypothèse !

    partie 2

    Pour cette partie où il faut trouver le dossier qui permet de libérer l'espace juste nécessaire pour dl la mise à jour, j'ai utilise un script de debug qui me liste les tailles de tous les répertoires. J'ai calculé à la main l'espace qu'il me faillait, et j'ai regardé dans la liste triée des tailles (| sort -n) celle qui était juste au dessus. Oui on a le droit de bidouiller pour l'AoC si ça permet d'aller plus vite à la solution.

    • [^] # Re: un bout de AWK

      Posté par  (site web personnel) . Évalué à 3.

      Comme le FS est parcourus "en profondeur d'abord" et dans l'ordre, pas besoin d'une structure de données trop compliquée type arbre, une simple liste suffit.

      Bien joué, je n'avais pas remarqué cela. Ceci dit, je n'aime pas trop me baser sur des suppositions qui ne sont absolument pas garanties par l'énoncé.

      • [^] # Re: un bout de AWK

        Posté par  . Évalué à 3.

        En fait vu la structure de l'input où il n'y a que de cd child et cd .. # parent, c'est nécessairement un parcours d'arbre en profondeur d'abord. Il n'y a pas d'autres représentations de la relation parent-enfants, genre cd /chemin/absolu en aléatoire.

        Et puis je préfère faire un code simple, le valider sur l'exemple, voire cramer un essai, avant de compliquer le code.

        • [^] # Re: un bout de AWK

          Posté par  (site web personnel) . Évalué à 3. Dernière modification le 07 décembre 2022 à 15:19.

          En fait vu la structure de l'input où il n'y a que de cd child et cd .. # parent, c'est nécessairement un parcours d'arbre en profondeur d'abord.

          $ cd /
$ ls
4212 aoc.py
dir 2021
dir 2022
$ cd 2021
$ ls
dir 12
$ cd ..
$ cd 2022
$ ls
dir 12
$ cd ..
$ cd 2021
$ cd 12
$ ls
42 01.py
12 02.py
51 03.py
$ cd ..
$ cd ..
$ cd 2022
$ cd 12
$ ls
12 01.py
51 02.py
42 03.py

          C'est idiot, on est d'accord. Mais ce n'est pas un parcours en profondeur d'abord.

          • [^] # Re: un bout de AWK

            Posté par  . Évalué à 2.

            C'est vrai que rien n'empêche de repasser deux fois pas le mm endroit pour pousser l'exploration des répertoires. Mais en effet c'est tordu et je n'avais pas de raison de me protéger "à prirori" de ce cas de figure. Si je n'étais pas parvenu à passer le test et la première partie, j'aurai regardé d'un peu plus près pour voir si des commandes cd child ne se répetent pas.

  • # Procrastination

    Posté par  (site web personnel) . Évalué à 4.

    On dirait que le Père Noël, ou les lutins, ou les deux, ne sont pas si motivés que ça pour aller effectivement courir la jungle pour récolter des caramboles. Ça traîne à faire des inventaires, à monter le camp, à nettoyer le camp, à décharger le bateau, à réorganiser le matériel déchargé, à bidouiller des communicateurs, à mettre à jour ces communicateurs…

    Ça fait six jours qu'on a débarqué, et n'a pas encore bougé du camp ! Vivement que les lutins nous fournissent une carte pour aller quelque part.

    • [^] # Re: Procrastination

      Posté par  . Évalué à 4.

      Vivement que les lutins nous fournissent une carte pour aller quelque part.

      Toi t'as envie de ressortir quelques algos de parcours de graphes :) Dijkstra sort de ce corps!

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.