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.