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.