🚲 Tanguy Ortolo a écrit 12077 commentaires

Et pour la deuxième partie, résolue grâce à l'idée de Pierre :

class Map:
    def simplify(self) -> None:
        connecteds: npt.NDArray[np.bool_] = np.zeros(self.matrix.shape, dtype=np.bool_)
        currents: set[Coords] = {self.start}
        while len(currents) > 0:
            nexts: set[Coords] = set()
            for current in currents:
                if connecteds[current]:
                    continue
                connecteds[current] = True
                nexts.update(self.neighs(current))
            currents = nexts
        for index, connected in np.ndenumerate(connecteds):
            if not connected:
                self.matrix[index] = Tile(0)

    def area(self) -> int:
        total = 0
        for line in self.matrix:
            inside: bool = False
            for tile in line:
                if inside and tile is Tile(0):
                    total += 1
                if Tile.NORTH in tile:
                    inside = not inside
        return total

Première étape, simplifier la carte en virant tous les tuyaux inutiles. Comme pour la première partie, c'est basé sur un parcours de proche en proche pour identifier les tuyaux connectés au point de départ. Ensuite, on parcours tout, puis on met à zéro les tuiles qui contenaient des tuyaux non connectés.

En fait, on parcours chaque ligne en gardant en mémoire si on est à l'intérieur de la boucle de tuyaux ou non. Seulement, à l'intérieur ou à l'extérieur, c'est ambigu lorsqu'on est justement sur un tuyau qui fait partie du réseau. Donc, pour être plus précis, on s'intéresse au fait que la zone en haut à gauche de chaque tuile est à l'intérieur ou non. Et vous pouvez faire tous les schémas que vous voulez, la seule chose qui fait changer l'état intérieur/extérieur de la zone en haut à gauche de la tuile suivante, c'est la présente d'un tuyau connecté au nord.

Quant à l'aire, les tuiles qui y contribuent sont celles qui sont à l'intérieur et qui sont vides (après élimination de tuyaux inutiles). Voilà !

C'est pour moi l'occasion d'utiliser enum.Flag qui correspond très bien à des trucs qui peuvent avoir une superposition d'états, ici des tuyaux connectés dans différentes directions.

from collections.abc import Iterable, Sequence
from typing import Optional, Self

import enum
import io

import numpy as np
import numpy.typing as npt

import aoc


Coords = tuple[int, int]


class Tile(enum.Flag):
    NORTH = enum.auto()
    SOUTH = enum.auto()
    EAST = enum.auto()
    WEST = enum.auto()

    def __str__(self) -> str:
        if self is self.__class__(0):
            return ' '
        # if self is self.EAST:
        #     return '╶'
        # if self is self.WEST:
        #     return '╴'
        if self.NORTH in self:  # type: ignore
            if self.EAST in self:  # type: ignore
                return '╚'
            if self.WEST in self:  # type: ignore
                return '╝'
            if self.SOUTH in self:  # type: ignore
                return '║'
            # if self is self.NORTH:
            #     return '╵'
        if self.SOUTH in self:  # type: ignore
            if self.EAST in self:  # type: ignore
                return '╔'
            if self.WEST in self:  # type: ignore
                return '╗'
            # if self is self.SOUTH:
            #     return '╷'
        if self.EAST in self:  # type: ignore
            if self.WEST in self:  # type: ignore
                return '═'
        # if self is self.WEST:
        #     return '╴'
        raise ValueError('unexpected value %s' % repr(self))

    def vector(self) -> Coords:
        if self is self.NORTH:
            return (-1, 0)
        if self is self.SOUTH:
            return (1, 0)
        if self is self.EAST:
            return (0, 1)
        if self is self.WEST:
            return (0, -1)
        raise ValueError('cannot convert multiple directions to vector')

    @classmethod
    def import_char(cls, char: str) -> Self:
        if char == '.' or char == ' ':
            return cls(0)
        if char == '|':
            return cls.NORTH | cls.SOUTH  # type: ignore
        if char == '-':
            return cls.EAST | cls.WEST  # type: ignore
        if char == 'L':
            return cls.NORTH | cls.EAST  # type: ignore
        if char == 'J':
            return cls.NORTH | cls.WEST  # type: ignore
        if char == '7':
            return cls.SOUTH | cls.WEST  # type: ignore
        if char == 'F':
            return cls.SOUTH | cls.EAST  # type: ignore
        raise ValueError('unsupported pipe description %s' % char)

Et la carte maintenant :

class Map:
    def __init__(self, array: Sequence[Sequence[Tile]], start: Coords):
        self.matrix: npt.NDArray[np.object_] = np.array(array)
        self.ly, self.lx = self.matrix.shape
        self.start = start

    @classmethod
    def import_lines(cls, lines: Iterable[str]) -> Self:
        start: Optional[Coords] = None

        array: list[list[Tile]] = []
        for y, line in enumerate(lines):
            array.append([])
            for x, char in enumerate(line.rstrip()):
                if char == 'S':
                    start = (y, x)
                    array[-1].append(Tile(0))
                else:
                    array[-1].append(Tile.import_char(char))

        map_ = cls(array, (0, 0))
        if start is not None:
            y, x = start
            connections = Tile(0)
            if y >= 1 and Tile.SOUTH in map_[y - 1, x]:
                connections |= Tile.NORTH
            if y < map_.ly - 1 and Tile.NORTH in map_[y + 1, x]:
                connections |= Tile.SOUTH
            if x >= 1 and Tile.EAST in map_[y, x - 1]:
                connections |= Tile.WEST
            if x < map_.lx - 1 and Tile.WEST in map_[y, x + 1]:
                connections |= Tile.EAST
            map_[y, x] = connections
            map_.start = start
            return map_
        else:
            raise ValueError('start position not found')

    def neighs(self, coords: Coords) -> Iterable[Coords]:
        y, x = coords
        for direction in self[coords]:
            dy, dx = direction.vector()
            y_, x_ = y + dy, x + dx
            if y_ >= 0 and y_ < self.ly and x_ >= 0 and x_ < self.lx:
                yield y_, x_

    def __getitem__(self, coords: Coords) -> Tile:
        return self.matrix[coords]

    def __setitem__(self, coords: Coords, value: Tile):
        self.matrix[coords] = value

    def __str__(self):
        s = io.StringIO()
        for line in self.matrix:
            for tile in line:
                s.write(str(tile))
            s.write('\n')
        return s.getvalue()

    def farthest(self) -> int:
        distances: npt.NDArray[np.int_] = np.full(self.matrix.shape, -1, dtype=np.int_)
        distance = 0
        currents: set[Coords] = {self.start}
        while len(currents) > 0:
            nexts: set[Coords] = set()
            for current in currents:
                if distances[current] >= 0:
                    continue
                distances[current] = distance
                nexts.update(self.neighs(current))
            currents = nexts
            distance += 1
        return distances.max()

La solution est donnée par la méthode Map.farthest(). C'est un parcours itératif de proche en proche :

1. on construit une matrice de distances au point de départ, initialisée avec des -1 partout ;
2. on commence avec une distance courante de zéro et le point de départ comme unique point courant, mais plus tard on en aura plusieurs (en pratique, deux, mais ça pourrait être plus si on avait des tuyaux trifides) ;
3. pour chaque point courant si aucune distance n'a été précédemment relevée, on note la distance courante et on place ses voisins reliés dans l'ensemble des prochains points courants ;
4. on continue, et on ne s'arrête que quand il n'y a plus aucun point courant.

Ah, et une petite précision, les services Google Play, c'est un ensemble de logiciels propriétaires, de démons vraisemblablement, qui implémentent des trucs pas présents dans Android Open Source. Et pas mal de logiciels propriétaires pour Android, et même quelques logiciels libres, dépendend de ses fonctionnalités. :-(

D'où, donc, le besoin, lorsqu'on veut utiliser un système d'exploitation plus ou moins libre genre LineageOS, d'installer soit les services Google Play, soit microG.

Oui alors comme je disais, c'est plus compliqué que ça. microG est là pour remplacer les services Google Play. Attention, j'ai bien dit les services Google Play, ce qui n'est pas Google Play Store.

Bref. Ça implique deux choses :

• ne pas avoir déjà les services Google Play qui tournent : quand on installe LineageOS sans installer en plus les applications Google, on est dans ce cas-là ;
• que microG puisse se faire passer pour les services Google Play.

Et c'est ce dernier point qui complique tout, parce que les logiciels pour Android ont un genre de signature qui prouve leur identité. Je ne connais pas bien le sujet, mais en tout cas, pour que microG puisse se faire passer pour les services Google Play, il faut que le système d'exploitation accepte de faire croire qu'il a la signature de ces derniers. Par conséquent, il faut un système d'exploitation qui prenne en charge la falsification de signature (en fait c'est plutôt une falsification de vérification de signature je pense).

Donc, pour que microG fonctionne, inutile d'essayer simplement de l'installer depuis F-Droid, ça ne marchera pas. Deux possibilités :

• soit installer un système d'exploitation qui prend directement ça en charge, et qui intègre déjà microG tant qu'à faire : c'est le cas de LineageOS for microG, une variante de LineageOS qui ajoute précisément cela ;
• soit être root et installer des trucs qui permettront cette falsification de signature.

C'est un petit peu plus compliqué que ça. microG, c'est une implémentation libre des services Google. Installer des logiciels depuis Google Play sans compte Google ne fait pas partie de ses fonctionnalités.

Installer des logiciels du Google Play Store sans Google Play, ça se fait avec Aurora Store, un logiciel disponible dans F-Droid. Rien à voir avec microG à priori.

Seulement, le problème, c'est que l'Identité Numérique La Poste inclut un piège, à son lancement, qui fait en gros :

1. récupérer le nom du logiciel avec lequel j'ai été installé ;
2. si ce logiciel n'est pas « Google Play » :
   1. afficher « Il faut m'installer avec Google Play, connard. D'accord ? »
   2. se terminer.

Du coup, pour pouvoir l'utiliser, il faut soit l'installer avec Google Play, soit trouver un truc qui ne déclenche pas ce piège. Par exemple, j'ai trouvé qu'en l'installant avec Aurora Store en tant que root, ça empêche L'Identité Numérique La Poste de déterminer comment elle a été installée (ça doit récupérer un truc genre chaîne vide), ce qui suffit à ne pas le déclencher. Seulement pour ça, il faut être root sur son téléphone. Et ça, l'Identité Numérique La Poste n'aime pas non plus, il y a aussi un piège pour ça. Du coup, il faut un moyen de cacher qu'on est root. On atteint des niveaux de bidouille assez hauts.

Autant que je sache, le seul moyen consiste à bidouiller franchement :

https://linuxfr.org/users/elessar/journaux/utiliser-l-identite-numerique-la-poste-sans-google-play

Juste un mot sur la partie 2. En force brute évidemment, ça prendrait des mois. Il y a une astuce évidemment, seulement avec l'énoncé seul, je ne crois pas qu'il y ait moyen de soupçonner de quoi il s'agit.

En fait l'astuce ne vient pas des règles du jeu, mais des données elles-mêmes, qui sont conçues pour que les fantômes tournent en rond. Je ne vous en dit pas plus.

Tu n'es pas seul. Mais ce n'est pas pour ça qu'il existe une solution, hélas.

https://www.libreavous.org/ca-y-est-je-suis-un-fracture-du-numerique
https://www.librealire.org/emission-libre-a-vous-diffusee-mardi-24-octobre-2023-sur-radio-cause-commune
https://grisebouille.net/franceconnect-ou-gafamconnect/

Une énumération n'est pas nativement utilisable dans des ensembles ou en clef de dictionnaire ???

https://blog.yossarian.net/2020/03/02/Totally-ordered-enums-in-python-with-ordered_enum
https://stackoverflow.com/questions/42369749/use-definition-order-of-enum-as-natural-order

Comme j'aime bien modéliser, c'est un sujet où j'utilise naturellement des énumérations. Pour les cartes, comme pour les types de mains.

class Card(Enum):
    ONE   = '1'
    TWO   = '2'
    THREE = '3'
    …
    TEN   = 'T'
    JACK  = 'J'
    QUEEN = 'Q'
    KING  = 'K'

L'avantage en donnant aux cartes la valeur correspondant au caractère qui les représente, c'est que ça permet de les parser très facilement :

card = Card('A')

Le problème, c'est que je veux comparer les cartes. Et des énumérations, eh bien ça ne se compare pas. Pas sans implémenter au moins une fonction de comparaison. Et ça, c'est… pénible.

Je rêve donc d'une solution propre pour définir une classé énumérée dont les membres se comparent, simplement avec leur ordre de définition.

Je découvre cached_property, merci !

Petite subtilité sémantique, les cartes disponibles sont 23456789TJQK, ce qui signifie :

• deux
• trois
• quatre
• …
• neuf
• dix (T pour ten, soit 10)
• valet (J pour jack)
• dame (Q pour queen)
• roi (K pour king)

La raison d'utiliser la lettre T pour le dix vient de la nécessité de l'écrire en un seul caractère. 10, ça fait deux caractères…

Ah, d'accord, je comprends mieux.

Au fait, je vous conseille de garder ce code quelque part. Ça a des chances de resservir. :-)

Je ne comprends pas. On peut bien découper des intervalles à l'avance, si le découpage ne correspond pas exactement à aux intervalles définis pour les conversions, il va falloir redécouper non ?

Je veux dire, on peut bien couper l'intervalle de graines 46 546+34 234 234 en 46 546+999 999, 1 046 546 + 999 999, … 34 046 546 + 234 235, mais ça ne va pas aider si on doit ensuite convertir les graines 25 561 123+3 123 458 en quelque chose d'autre. Sauf si j'ai vraiment une chance monstrueuse, les limites de cet intervalle à convertir ne correspondent pas du tout à celles des intervalles de graines prédécoupés.

Donc on se retrouve de toute façon à faire de la découpe d'intervalles par intersection. Tant qu'à faire, autant le faire à partir des intervalles entiers, le prédécoupage n'a aucun intérêt. Qu'est-ce que j'ai loupé ?

Pour moi, à la lecture de l'énoncé, je n'y ai pas vu un problème d'algorithmique, mais de mathématiques. Une régate avec un temps de charge qui donne la vitesse pour dépasser la distance record en un temps limité, c'est une inéquation polynomiale de second degré.

Un polynôme de second degré

Soit la durée de la course, la distance record et t le temps de charge (notre variable). La vitesse atteinte est d'après l'énoncé égale au temps de charge. Sur la durée de la course, il ne reste plus que pendant lequel le bateau parcourra .

On charge à battre le record, soit :

Cela se normalise en :

La partie gauche est un polynôme de second degré, en forme de cloche vers le haut. Ça tombe bien, si les données sont bien construites il devrait s'annuler en deux points, et être négatif entre les deux. Je sais très bien résoudre ça.

Résolution

Le discriminant de ce polynôme vaut :

Comme je disais, si les données sont bien construites, ça devrait être strictement positif et donner les racines suivantes :

En chargeant notre bateau pendant exactement ou , on égale le record. Entre et , on le dépasse.

Retour à la réalité fiction

Bon, c'est bien joli ça, on peut déterminer des temps minimum et maximum qui sont des réels, mais on nous demande un nombre de durées de charge possible, entières à la milliseconde près, pour dépasser strictement le record.

Si le temps minimum, par exemple, n'est pas entier, c'est facile, il faut charger pendant une durée supérieur ou égale à son arrondi à l'entier supérieur. Mais les cas limites sont importants, qu'en est-il si le temps minimum est entier ? Il faut charger pendant une durée supérieure ou égale à l'entier suivant.

En fait, la borne inférieure à considérer est l'entier inférieur au temps minimum, augmenté d'une unité. Mutatis mutandis pour le temps maximum.

Les bornes incluses de notre intervalle de durées possibles seront donc :

Quand au nombre d'options, c'est par conséquent la longueur de cet intervalle :

Partie 1, partie 2

Ce calcul s'applique aussi bien à la première qu'à la deuxième partie. Et c'est rapide, genre vraiment rapide puisque c'est simplement du calcul. Mieux encore, alors que pour la première partie il faut traiter trois ou quatre régates, pour la seconde il n'y en a plus qu'une seule, donc c'est trois ou quatre fois plus rapide. :-)

En pratique, en Python 3 ça prend dans les 50 millisecondes pour la première comme pour la seconde partie, mais je soupçonne que ce soit essentiellement la compilation et le temps de chargement de la machine virtuelle Python.

On arrive au genre d'exercice où la résolution simple de la première partie devient inapplicable à la seconde partie, parce qu'il lui faudrait plus de mémoire qu'il n'y en a sur Terre ou plus de temps que l'âge de l'univers. Là, on est plutôt dans le second cas, je dirais.

Bref, ce n'est pas la première fois que je me retrouve à couper des intervalles en morceaux, alors c'est cadeau, voici du code pour faire ça. Je réutilise le type range qui correspond plutôt bien au concept.

def intersects(range1: range, range2: range) -> bool:
    """Tell whether or not the two ranges have a part in common."""
    if range1.start >= range1.stop or range2.start >= range2.stop:
        raise ValueError("usupported empty range") 
    if range1.step != 1 or range2.step != 1:
        raise ValueError("unsupported stepped range")
    return range1.stop > range2.start and range2.stop > range1.start

def intersect(range1: range, range2: range) \
        -> tuple[Optional[range], Sequence[range], Sequence[range]]:
    """Given two ranges, returns:
    1. the eventual intersection of both ranges;
    2. parts of the first range that are not part of the second one;
    3. parts of the second range that are not part of the first one.
    """
    if range1.start >= range1.stop or range2.start >= range2.stop:
        raise ValueError("usupported empty range") 
    if range1.step != 1 or range2.step != 1:
        raise ValueError("unsupported stepped range")
    if not intersects(range1, range2):
        # Disjoint ranges
        return None, (range1,), (range2,)
    diff1: list[range] = []
    if range1.start < range2.start:
        diff1.append(range(range1.start, range2.start))
    if range2.stop < range1.stop:
        diff1.append(range(range2.stop, range1.stop))
    diff2: list[range] = []
    if range2.start < range1.start:
        diff2.append(range(range2.start, range1.start))
    if range1.stop < range2.stop:
        diff2.append(range(range1.stop, range2.stop))
    return (range(max(range1.start, range2.start),
                  min(range1.stop, range2.stop)),
            diff1, diff2)

fairphone affiche de très mauvais retours..

Le Fairphone 2, oui. Mais ça commence à dater, comme info, quand même. Depuis, on en est au Fairphone 4, en fait.

Tu n'utilises pas enum.Enum ? Je trouve ça bien pratique pour, eh bien, les cas comme les couleurs, là.

#! /usr/bin/python3

# Advent of Code 2023, day 4

from __future__ import annotations

from collections.abc import Iterable
from typing import Self

import re


class Card:
    def __init__(self, id_: int, win_nums: Iterable[int], got_nums: Iterable[int]):
        self.id = id_
        self.win_nums = set(win_nums)
        self.got_nums = set(got_nums)
        self._matches: Optional[int] = None

    pattern = re.compile(r'^Card +(\d+): ([ \d]+) \| ([ \d]+)\n?$')

    @classmethod
    def import_line(cls, line: str) -> Self:
        if (m := cls.pattern.match(line)) is not None:
            return cls(int(m[1]), (int(word) for word in m[2].split()), (int(word) for word in m[3].split()))
        print(line)
        raise ValueError("invalid card description")

    @property
    def matches(self) -> int:
        if self._matches is None:
            self._matches = len(self.win_nums & self.got_nums)
        assert self._matches is not None
        return self._matches

    @staticmethod
    def _num_to_points(num: int) -> int:
        if num <= 0:
            return 0
        return 2 ** (num - 1)

    def points(self) -> int:
        return self._num_to_points(self.matches)


def solve_both_parts(lines: aoc.Data) -> tuple[int, int]:
    """Solve puzzle parts 1 and 2: determine the sum of all card values and the total number of cards"""
    # Import
    cards: list[int, Card] = []
    for line in lines:
        card = Card.import_line(line)
        cards.append(card)
    # Part 1
    points = sum(card.points() for card in cards)
    # Part 2
    copies = [1 for card in cards]
    for i, card in enumerate(cards):
        for j in range(i + 1, i + 1 + card.matches):
            copies[j] += copies[i]
    return points, sum(copies)

Pour les amateurs, il y a une extension Firefox qui permet d'afficher des courbes et des stats plus détaillées que ce qui est indiqué dans la page Web du leaderbord :
https://addons.mozilla.org/fr/firefox/addon/advent-of-code-charts

Non, l'argent ne s'évapore pas, enfin si mais pas comme ça. Les deux seules choses qui détruisent de l'argent, c'est :

• brûler des billets de banque ou fondre des pièces de monnaie ;
• rembourser des emprunts bancaires.

Acheter une boîte, puis que la cotation boursière de cette dernière chute, ça ne détruit pas d'argent. C'est comme acheter une maison, puis qu'un aéroport soit construit à côté et qu'elle perdre les trois quarts de sa valeur de revente.

C'est tout simple, quand on achète un truc, on ne détruit pas d'argent, on en donne au vendeur en échange de ce qu'on achète. Et si ça perd de sa valeur, tant qu'on ne le revend pas, ça ne change rien. Mais vraiment rien, je veux dire : si j'achète une maison pour y habiter, le fait qu'elle perde la moitié de sa valeur ne change strictement rien : ça ne change pas la façon dont je rembourse mon emprunt, ça ne change pas mes charges, ça ne change pas mes impôts, ça ne change rien, vraiment rien. Et en particulier, ça ne détruit pas d'argent.

La seule chose que ça change se produira le jour où je revendrai ce que j'ai acheté. J'en obtiendrai moins d'argent en échange. Mais ça ne détruira toujours pas d'argent.

Donc, pour en revenir à M. Musk, à moins qu'il ne souhaite revendre Twitter, le fait que le cours de l'action ait dégringolé ne lui change rien. S'il comptait revendre un jour, en revanche, il doit avoir les boules, c'est sûr. S'il comptait empocher des dividendes, c'est plutôt mal barré aussi d'ailleurs, mais c'est un autre sujet, pas directement lié à la valeur de l'action.

Depuis quelque temps un ramdisk,

Non.

c’est-à-dire un système de fichier en RAM

Oui.

Plus précisément, un sous Linux, un tmpfs est un bien un système de fichiers en mémoire. En revanche, ce n'est pas un ramdisque, c'est à dire que ce n'est pas un morceau de mémoire réservé et présenté comme un périphérique bloc, sur lequel on viendrait mettre un système de fichiers. C'est un système de fichiers bien particulier, directement implémenté en mémoire.

Au fait, c'est aussi le cas pour les Google Pixel. Vigilance.