En Python

Ç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