🚲 Tanguy Ortolo a écrit 12197 commentaires

Ç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

Exact, mais sans intérêt. Ce qui est intéressant, c'est de comprendre de quoi on parle : un système régi par la loi et des assurances qui en sont l'implémentation, sous la forme d'une sorte d'oligopole légal assez unique en son genre.

L'utilisation de termes aussi vague que « la sécu » me semble donner l'impression qu'il s'agirait d'une administration d'État, avec laquelle les citoyens auraient la même relation qu'avec le fisc ou la préfecture du coin. Ça en fait un organisme puissant et distant de ses clients.

Alors que c'est bien plus clair en parlant simplement d'assurance : il n'est pas question de citoyens mais d'adhérents (voire de clients), et la relation est la même que celle qu'on peut avoir avec son assureur habitation ou automobile (d'ailleurs c'est obligatoire aussi, seulement pour celles-là, on a le choix de l'assureur).

Sauf que ce n'est pas du tout offert, c'est payé par les cotisation des employés. À moins qu'ils n'y ait des preuves, ou au moins de soupçons que l'employeur paie discrètement un supplément de cotisation sans le déclarer justement.

Sinon, ça ce compte-là, on pourrait aussi dire que le remboursement de l’ostéopathie est « offerte » puisqu'il n'y a pas de surcoût. C'est idiot, ça fait partie du contrat, en échange de la cotisation.

Avantage en nature non déclaré ‽ Avantage en nature, d'accord, mais non déclaré, c'est n'importe quoi, la cotisation apparaît sur la fiche de paie !

Je comprendrais que des célibataires se sentent lésés par le fait de cotiser ce qu'il faut pour couvrir les conjoints des autres, mais ce n'est pas du tout un problème de déclaration de l'avantage en question.

j'ai le cas: mutuelle imposée par la boite de mon épouse. On a voulu stopper ça et… Cest possible uniquement si la seconde mutuelle est dite familiale, donc couvre toute la famille par défaut sans surcout.

Pas tout ça fait, c'est pire que ça. L'assurance complémentaire peut exigée une preuve que tu es couvert obligatoirement par celle de ton conjoint. Si c'est facultatif, même sans surcoût, ils peuvent refuser.

Ça fait partie des idées de lois dont je dois parler à mon député. Dans le même sens que la liberté de choisir son assurance emprunteur, ce serait bien d'avoir la liberté de choisir son assurance complémentaire santé. L'obligation pour l'employeur d'en fournir une pourrait être maintenue, avec la possibilité de cesser d'y cotiser sur preuve qu'on a déjà une complémentaire santé, sans plus de contrainte.

Oui. On a le droit de ne pas adhérer à la mutuelle assurance complémentaire santé (cf. infra) obligatoirement proposée par son employeur, à condition de prouver qu'on est obligatoirement couvert par celle de son conjoint.

C'est très subtil, parce que si par exemple, l'assurance de ton conjoint te couvre de façon optionnelle, mais sans surcoût, ça ne te donne pas le droit de ne pas adhérer à la tienne.

(Bon, après, la seule différence entre un certificat comme quoi on est couvert sans surcoût, et un certificat comme quoi on est obligatoirement couvert sans surcoût, c'est un seul mot, donc rien d'insurmontable, si vous voyez ce que je veux dire. o:-) )

Je vais te parler de ma mutuelle santé/prévoyance

Non. Tu nous parles de ton assurance santé et prévoyance. Une mutuelle, c'est une forme d'entreprise, assez répandue dans le domaine de l'assurance et de la banque, mais ce n'est sans doute pas le cas de la tienne. C'est très facile à vérifier : est-ce que tu es invité à voter pour élire les dirigeants de cette société d'assurance ? Sinon, ce n'est pas une mutuelle.

Je ne sais pas d'où sort cette utilisation du terme de « mutuelle » pour désigner de façon générique une assurance santé, mais il faut vraiment arrêter ça.

C'est comme l'utilisation du terme de « sécurité sociale » pour désigner un organisme imaginaire, je trouve que cela nuit à la compréhension de la réalité. La sécurité sociale, c'est un système, pas une entreprise. Ce système est essentiellement composé de multiples compagnies d'assurance, la plus grosse d'entre elles étant la Caisse primaire d'assurance maladie. On ne cotise pas à « la sécu », on est adhérent d'un assureur particulier, en l'occurrence la CPAM pour les salariés du privé, mais il y en a d'autres.

Ça n'optimise rien du tout, si ?

Je veux dire, nous avons tous deux la ligne entière en mémoire, mais là où j'en prends à chaque fois une tranche pour la convertir en ensemble et regarder sa longueur, tu enfonces un par un chacun de ses caractères dans une file à taille limitée, que tu convertis en ensemble pour regarder sa longueur.

Quoique, ça évite une copie de chaîne à chaque étape, c'est ça ? La file à taille limitée étant persistante et ne copiant qu'un caractère à chaque fois.

from typing import Iterable


def solve1(lines: Iterable[str]) -> int:
    """Solve part 1 of today's puzzle"""
    for line in lines:
        # There is actually only one line :-)
        for i in range(4, len(line) - 1):  # ignore final '\n'
            if len(set(line[i-4:i])) >= 4:
                return i
    return 0


def solve2(lines: Iterable[str]) -> int:
    """Solve part 2 of today's puzzle"""
    for line in lines:
        # There is actually only one line :-)
        for i in range(14, len(line) - 1):  # ignore final '\n'
            if len(set(line[i-14:i])) >= 14:
                return i
    return 0

Le fait que mes fonctions mangent un itérable de chaînes vient des fonctions utilitaires que j'ai codées pour intégrer ça facilement. Ici, ça donne quelque chose d'un peu artificiel puisqu'il n'y a qu'une ligne à lire.

Je ne suis pas du tout satisfait par le fait de transformer à chaque fois un bout glissant de la chaîne d'entrée en un ensemble. J'aimerais bien faire quelque chose d'un peu mieux optimisé, mais je n'ai rien de probant en tête.

Au fait, avez-vous remarqué ce qu'on trouve dans la boutique de l'Avent du Code cette année ? On dirait qu'on va bientôt changer de moyen de transport.

Vous vous souvenez sans doute encore d'une petite phrase de l'intro :

To supply enough magical energy, the expedition needs to retrieve a minimum of fifty stars by December 25th. Although the Elves assure you that the grove has plenty of fruit, you decide to grab any fruit you see along the way, just in case.

Juste au cas où, bien sûr… Cette précaution commence à prendre du sens, vu que les lutins ont visiblement besoin d'être babysittés en permanence ! Quelle surprise, à se demander comment ils arrivaient à ramener ce qu'il faut les Noëls précédents. Heureusement qu'on a pris de l'avance en collectant des fruits en étoile au fur et à mesure !

Bref, j'ai l'impression qu'on arrive au bout de l'installation et qu'on va pouvoir partir en expédition dans la jungle. Et quelque chose me dit que ça ne va pas tout à fait se passer comme prévu.

Vous imaginez quoi pour demain ? Je verrais bien quelque chose à base de carte de zones plus ou moins dangereuses et de détermination de parcours optimisé…

C'est tout à fait ça. Mais à vrai dire, dès que le problème que je cherche à résoudre n'est pas un truc jetable, en particulier lorsqu'il s'agira de le montrer à d'autres ou de revenir dessus, j'utilise de moins en moins Awk.

Je trouve en effet que, sauf quand c'est vraiment très simple, ça donne quelque chose de très peu compréhensible à la lecture ou à la relecture.

Ce qui est assez casse-pied dans ce problème, c'est que les données d'entrées sont dans un ordre qui est optimisé pour la lecture par un lutin grutier ou en l'occurrence une lutine grutière.

Bref, voici le code :

import re

from collections import deque
from io import StringIO
from typing import Dict, List, Iterable, Iterator, MutableSequence, Sequence
from typing_extensions import Protocol


class Crane(Protocol):
    def load(self, stacks: Sequence[MutableSequence[str]],
             labels: Iterable[str]) -> None:
        ...

    def move(self, orig: str, dest: str, n: int) -> None:
        ...

    def top(self) -> str:
        ...


class CrateMover:
    def __init__(self) -> None:
        self.stacks = {}  # type: Dict[str, MutableSequence[str]]
        self.labels = []  # type: List[str]

    def load(self, stacks: Sequence[MutableSequence[str]],
             labels: Iterable[str]) -> None:
        for stack, label in zip(stacks, labels):
            self.stacks[label] = stack
        for label in labels:
            self.labels.append(label)

    def top(self) -> str:
        result = StringIO()
        for label in self.labels:
            result.write(self.stacks[label][-1])
        return result.getvalue()


class CrateMover9000(CrateMover):
    def __init__(self, *args, **kwargs) -> None:
        super().__init__()

    def move(self, orig: str, dest: str, n: int) -> None:
        orig_stack = self.stacks[orig]
        dest_stack = self.stacks[dest]
        for _ in range(n):
            dest_stack.append(orig_stack.pop())


class CrateMover9001(CrateMover):
    def __init__(self, *args, **kwargs) -> None:
        super().__init__()

    def move(self, orig: str, dest: str, n: int) -> None:
        orig_stack = self.stacks[orig]
        dest_stack = self.stacks[dest]
        temp_stack = deque()  # type: deque[str]
        for _ in range(n):
            temp_stack.appendleft(orig_stack.pop())
        dest_stack.extend(temp_stack)


def solve(lines: Iterator[str], crane: Crane) -> str:
    re_crates = re.compile(r'^\s*\[')
    stacks = []   # type: List[deque[str]]
    # First lines are crate stack descriptions
    for line in lines:
        if re_crates.match(line):
            # This line describes stacked crates
            for i, label in enumerate(line[1:len(line):4]):
                if i >= len(stacks):
                    stacks.append(deque())
                stack = stacks[i]
                if label != ' ':
                    stack.appendleft(label)
        else:
            # This line provides the labels of crate stacks
            break
    # Current line provides the labels of crate stacks
    labels = line[1:len(line):4]
    # We have enough data to load the crane with crate stacks
    crane.load(stacks, labels)
    # Next line is a blank one
    s = next(lines)
    # Next lines are crate moving instructions
    re_instruction = re.compile(r'^move (\d+) from (.) to (.)$')
    for line in lines:
        m = re_instruction.match(line)
        if m is None:
            raise ValueError("unrecognized input line")
        n = int(m.group(1))
        orig = m.group(2)
        dest = m.group(3)
        crane.move(orig, dest, n)
    return crane.top()


def part1(data: Iterable[str]) -> str:
    crane = CrateMover9000()
    return solve(iter(data), crane)


def part2(data: Iterable[str]) -> str:
    crane = CrateMover9001()
    return solve(iter(data), crane)

En Python, en utilisant une classe dédiée (je trouve que ça se lit mieux ainsi) :

from typing import Iterable, Tuple

import aoc


class Interval:
    """An interval of integers"""
    def __init__(self, start: int, end: int):
        """Create a new interval of integers, from start to end included"""
        self.start = start
        self.end = end

    def includes(self, other):
        """Does this interval include the other one?"""
        return self.start <= other.start and self.end >= other.end

    def overlaps(self, other):
        """Does this interval overlap the other one?"""
        return self.end >= other.start and self.start <= other.end


def import_interval(s: str) -> Interval:
    """Import an interval from a string such as "2-4" """
    part1, part2 = s.split('-')
    return Interval(int(part1), int(part2))


def import_pairs(lines: Iterable[str]) -> Iterable[Tuple[Interval, Interval]]:
    """Import a pair of intervals from a line such as "2-4,5-8\\n" """
    for line in lines:
        part1, part2 = line.rstrip().split(',')
        yield import_interval(part1), import_interval(part2)


def solve_both(lines: Iterable[str]) -> Tuple[int, int]:
    """Solve both parts of today's puzzle"""
    inclusions = 0
    overlaps = 0
    for a1, a2 in import_pairs(lines):
        if a1.includes(a2) or a2.includes(a1):
            inclusions += 1
        if a1.overlaps(a2):
            overlaps += 1
    return inclusions, overlaps

C'était en effet parfaitement taillé pour Awk !

#! /usr/bin/python3

# Advent of Code 2022, day 2

from typing import Iterable, Optional, TypeVar

# '@' is not a valid item type, but it does no harm, and having it makes the
# value of each item type equal to its index in this string. :-)
letters = "@abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
priorities = {letter: value for (value, letter) in enumerate(letters)}


class Rucksack:
    def __init__(self, left: str, right: str):
        self.left = left
        self.right = right

    def anomaly(self) -> str:
        for letter in self.left:
            if letter in self.right:
                return letter
        raise ValueError("no anomaly in this rucksack")

    def __contains__(self, letter: str) -> bool:
        return letter in self.left or letter in self.right


def import_sack(line):
    n = len(line) - 1  # do not count final '\n'
    left = line[0:n//2]
    right = line[n//2:n]
    return Rucksack(left, right)


T = TypeVar('T')


def group(iterable: Iterable[T], n: int) -> Iterable[list[T]]:
    result = []  # type: list[T]
    for item in iterable:
        result.append(item)
        if len(result) >= n:
            yield result
            result = []
    yield result


def part1(lines: Iterable[str]) -> int:
    total = 0
    for line in lines:
        sack = import_sack(line)
        total += priorities[sack.anomaly()]
    return total


def part2(lines: Iterable[str]) -> int:
    total = 0
    for line_group in group(lines, 3):
        sacks = [import_sack(line) for line in line_group]
        for letter in letters:
            if all(letter in sack for sack in sacks):
                total += priorities[letter]
                break
    return total

Le ministère demande des choses mais que propose-t-il ? Existe-t-il des solutions alternatives qui seraient fournies par l'éducation nationale ?

Oui : étudier sans informatique, sauf lorsqu'il s'agit d'apprendre la bureautique et l'informatique.

Sérieusement, les connaissances de compétences de base que l'école est censée transmettre n'ont pas changé depuis cinquante ans, c'est toujours lire, compter, calculer, réfléchir, puis pour aller plus loin, étudier des textes littéraires, résumer, raisonner, avec des bases en diverses sciences. Que des trucs qui se faisaient très bien sans informatique, et qui peuvent toujours très bien se faire sans informatique.

Je soupçonne même que ces trucs se feraient sans doute mieux sans informatique.

L'informatique est indispensable lorsqu'il s'agit d'apprendre la bureautique. Ça se fait sans problème sous Google ni Microsoft. L'informatique est, en revanche, secondaire lorsqu'il s'agit d'apprendre la programmation, c'est important à rappeler. L'algorithmique et toute ça théorique, ça se fait sans ordinateur, en tout cas sans coder, donc sans problème avec un tableau noir et du papier.

Toujours en Python, mais aujourd'hui, point de modélisation objet, c'est du concis, plus en mode calcul :

from typing import Iterable, Tuple

def solve_both(lines: Iterable[str]) -> Tuple[int, int]:
    # Symbol -> value for part 1
    values1 = {'A': 1, 'B': 2, 'C': 3, 'X': 1, 'Y': 2, 'Z': 3}
    # Symbol -> value for part 2
    values2 = {'A': 1, 'B': 2, 'C': 3, 'X': -1, 'Y': 0, 'Z': 1}
    score1 = 0  # for part 1
    score2 = 0  # for part 2
    for line in lines:
        char1, char2 = line.split()
        # Values for part 1
        value1_1, value1_2 = values1[char1], values1[char2]
        outcome1 = ((value1_2 - value1_1 + 1) % 3) * 3
        # Values for part 2
        value2_1, result2 = values2[char1], values2[char2]
        value2_2 = (value2_1 + result2 - 1) % 3 + 1
        outcome2 = ((result2 + 1) % 3) * 3
        # We are player 2!
        score1 += value1_2 + outcome1
        score2 += value2_2 + outcome2
    return score1, score2

(Oui, j'aime bien modéliser avec des classes, même quand ça n'a aucun intérêt pratique.)

Du code commun aux deux parties, essentiellement pour modéliser et importer les données :

import collections
import itertools

from collections.abc import Iterable, Sequence

import aoc


class Pack:
    """An elf backpack, containing a list of food items"""
    def __init__(self, items: Sequence[int]) -> None:
        """Create an elf backpack containing the providing items (an item is
        actually an amount of energy, in calories)"""
        self.items = items

    def total(self) -> int:
        """Return the total energy corresponding to the items in a
        backpack"""
        return sum(self.items)


def import_packs(lines: Iterable[str]) -> Iterable[Pack]:
    """Read input lines and return an iterator, yielding one elf backpack at a
    time"""
    items = [] # type: list[int]
    for line in lines:
        if line == '\n':
            # A newline separates the description of one backpack from the next
            # one. Therefore, a pack has been entirely listed and can be
            # yielded.
            yield Pack(items)
            items = []
            continue
        items.append(int(line))
    # The last pack has been entirely listed and we have to yield it too.
    yield Pack(items)

Première partie, on veut le total de l'énergie du sac qui en contient le plus :

def part1(lines: Iterable[str]) -> int:
    """Solve puzzle part 1: determine the backpack containing most energy, and
    return the amount of energy it contains"""
    packs = import_packs(lines)
    return max(pack.total() for pack in packs)

Deuxième partie, on veut le total de l'énergie des trois sacs qui en contiennent le plus :

def part2(lines: Iterable[str]) -> int:
    """Solve puzzle part 2: determine the three backpacks containing most
    energy, and return the amount of energy they contain"""
    packs = import_packs(lines)
    totals = (pack.total() for pack in packs)
    # Sort the energy totals so the greatest are at the end, and sum the three
    # last ones
    return sum(sorted(totals)[-3:])

Je ne suis pas très satisfait par le fait de trier les totaux, j'aurais bien aimé faire ça en parcourant simplement les sacs, mais je n'ai pas trouvé de façon élégante de le faire.

Et voilà, cette année, le Père Noël a été invité par ses lutins à participer à leur récolte annuel de fruits étoilés destinés à nourrir les rennes et leur apporter l'énergie magique nécessaire à la tournée de Noël.

We wish you a merry Christmas and a happy hacking!

Flash, mais après avoir hésité. Mon avis :

• Flash a le tort de s'être vraiment imposé, devenant incontournable et donc une plaie dont on pouvait difficilement se passer.
• Silverlight a au contraire l'avantage de n'avoir jamais vraiment percé, et la difficulté ou la réticence à l'installer n'a jamais eu un coût élevé ;
• Shockwave : c'était un avatar de Flash non ?
• Pour les applets on parle de Java, j'imagine. L'avantage, c'est que c'était plus ou moins libre. Pourri à mes yeux, mais sans trop de réticence ou de difficultés à installer.
• Java Web Start : si je me souviens bien, ce n'est pas vraiment du web dynamique, ça, juste un mode de distribution de logiciels jetables. Même impression qu'avec Java.
• VBScript : ça a existé ce truc ?
• HTML5 et compagnie : c'est ouvert, implémentations libres disponibles, bref un vrai progrès à mes yeux.

Même constat pour le côté vidéo et audio. Personnellement, je déteste ça, quand on me passe un enregistrement d'une conférence, je cherche tout de suite à savoir s'il n'y en a pas une transcription.

Mais en revanche, je maintiens que j'ai toujours l'impression de subvocaliser quand je lis. Comme quand je pense d'ailleurs.

Malheureusement, beaucoup de personnes ont tendance à "subvocaliser" et donc à lire à haute voix dans leur tête.

C’est une perte de temps terrible qui rend la lecture fastidieuse et ne permet pas d’utiliser la mémoire court-terme pleinement et qui rend quasi-impossible la lecture de textes longs et complexes avec une compréhension profonde.

C'est très curieux, personnellement j'ai bien l'impression de prononcer dans ma tête, mais beaucoup plus vite que si je lisais à voix haute. D'ailleurs, j'ai une vitesse de lecture plutôt rapide, comparée à celle des gens avec qui j'ai pu comparer. Et ça me permet de lire des textes longs et complexes en les comprenant bien.

Mais à côté de ça, j'ai entendu parler de lecture rapide, une technique de lecture sans prononcer dans sa tête, qui serait bien plus rapide. J'ai essayé un peu, mais je n'ai pas accroché, sans doute pas assez pour bien me rendre compte. Pour le peu que j'ai fait, ça m'a justement donné l'impression de survoler un texte sans bien rentrer dedans, c'est très curieux.

Non rien.