🚲 Tanguy Ortolo a écrit 12252 commentaires

Je n'ai pas encore commencé, mais vu l'énoncé de la première partie, je dirais que l'incrément de hauteur doit se répéter au bout du PPCM du nombre de formes et du nombre de d'instructions de direction du vent.

Avec la première série de tant de blocs qui doit monter un petit peu plus haut puisqu'elle est posée sur un sol plat et non sur une tour qui sommet irrégulier.

Bon, alors effectivement, mon titre était un peu trompeur : ce n'est pas le démarcheur lui-même que je cherche à piéger, mais son commanditaire en fait.

La boîte de rénovation qui me fait appeler a bien une existence en France, et si je peux contribuer à les mettre en difficulté, ce sera toujours une bonne action de faite, au profit de leurs concurrents plus honnêtes. Pareil pour les boîtes de formation professionnelle.

En fait, quand on se montre intéressé, on nous passe rapidement quelqu'un qui n'est plus un démarcheur mais un conseiller de la boîte malhonnête.

En tout cas, des boulots dans des secteurs qui recrutent, ça n'est pas difficile à trouver : employé dans la restauration, aide-soignante, infirmière, conducteur d'autobus ou de train…

Certains demandent de la formation, mais la pénurie de main d'œuvre est telle que les employeurs peuvent aller jusqu'à la prendre en charge.

Ce sont des métiers contraignants, mais aujourd'hui, pour travailler à faire des trucs pénibles, nuisibles et illicites à longueur de journée, il faut le vouloir.

Pour tous ces logiciels, c'est assez paradoxal, mais le meilleur moyen de les faire fonctionner dans qu'ils détectent que votre téléphone utilise un système non Android, c'est de le rooter avec Magisk, d'activer Zygisk, d'installer Universal SafetuNet Fix et de les ajouter à la liste d'exclusion.

Avec un peu d'explication :
- Magisk, c'est un /bin/su et des possibilités techniques de changer des tas de trucs à ce que vient les logiciels qu'on lance ;
- Zygisk, c'est une option de Magisk, plus liée à l'intérieur des processus applicatifs eux-mêmes si j'ai bien compris, et c'est nécessaire pour…
- Universal SafetyNet Fix (USF), in module Magisk qui permet de passer la validation SafetyNet malgré un système non Android et rooté ;
- la liste d'exclusion, c'est un réglage de Magisk, qui indique à quels logiciels la présence de /bin/su doit être masquée, et qui est aussi utilisée par USF.

Bilan tout de même, grâce à ces contraintes de « sécurité », pour utiliser ces logiciels, on passe d'un système normal mais juste pas Android, à un système rooté et bidouillé pour mentir à gogo… On n'arrête pas le progrès.

Un peu désolé, ou pas en fait. Des boulots de merde, il y en a d'autres aussi, qui ont l'avantage de ne pas considérer à commettre des infractions en série.

À un moment il faut donner un numéro de téléphone, mais ça ne change rien si c'est celui de quelqu'un d'autre.

Tiens, je n'avais pas pensé à Pypy. Pour info, ma solution termine la seconde partie – ligne par ligne, avec calcul d'unions d'intervalles – en 2,7 s sous Pypy.

J'y ai réfléchi cette nuit, on peut faire encore mieux. Premièrement parce qu'il n'est pas vraiment nécessaire de considérer les intersections de droites, mais seulement celles des segments qui délimitent les zones de chaque capteur (enfin, les segments juste un point plus loin en fait).

Mais surtout parce que le point cherché est soit :

• dans un coin du terrain et sur un segment ;
• sur un bord du terrain et à l'intersection de deux segments ;
• n'importe où ailleurs, mais à l'intersection de quatre segments.

Bref, in n'a plus qu'à tester si un coin ne se trouverait pas sur un segment, et sinon, si on construit la liste des intersections, on n'a plus qu'à chercher si on ne trouve pas dedans :

• un point qui serait sur un bord ;
• un point qui s'y trouverait quatre fois.

Je ne réponds pas à un numéro qui n'est pas dans mon annuaire perso (même si c'est un livreur, un commerçant ou un artisan qui m'appelle pour un truc important, figurez-vous qu'il va me laisser un mot sur le répondeur !!! dingue non ?)

Quand on a une messagerie vocale, oui. J'ai volontairement désactivé la mienne, et les fournisseurs divers risqueraient de moyennement apprécier le fait que je leur demande de laisser un SMS sans possibilité de laisser un message vocal…

Ça, c'est bien quand on supporte les messages vocaux. Personnellement, je déteste ça, et après des années d'hésitation, j'ai finalement désactivé ma messagerie vocale. J'ai juste un message d'absence qui invite à laisser un SMS. Le genre de truc qu'un démarcheur ne fera jamais depuis son poste fixe d'ailleurs.

Il me semble que c'est un brin plus nuancé. Je ne suis pas certain qu'il soit illégal d'enregistrer un appel qu'on reçoit dans le consentement de l'interlocuteur. Mais même si ça l'était, s'il ne l'apprend jamais il ne pourra pas s'en plaindre, en attendant c'est bien pratique pour vérifier le nom qu'à donné le démarcheur par exemple.

Rendre public cet enregistrement, ça pourrait peut-être bien être risqué en revanche. Et ça pourrait bien ne pas être recevable comme preuve en effet.

Farpaitement !

Et j'y ai aussi découvert les dataclasses. Très pratique ça, avec en plus l'option congélateur, ça va me simplifier la vie la prochaine fois que j'aurai affaire à des coordonnées.

Euh, ça dépend lesquels. J'ai affaire à une boîte particulièrement coriace, leur nom, en tout cas le nom qu'ils prétendent avoir, est en deux mots, ça commence par Habitat et ça finit par Fermeture. Reçu peut-être une dizaine d'appels, genre un par mois depuis un an. Ils sont ma prochaine cible.

Je viens de tomber sur une solution que je trouve assez géniale : https://github.com/JakubDotPy/aoc2022/blob/master/day15/part2.py

La solution sera forcément à une intersection de frontières de zones couvertes par les capteurs. Bon, pas forcément, elle pourrait être dans un coin, mais c'est plus que douteux. On pourrait quand même tester.

Bref, entre les intersections et les quatre coins de la grille, il n'est pas difficile de vérifier si l'un de ces points ne serait pas par hasard hors de portée de tous les capteurs…

Comment prouver qu'il y eu démarchage abusif ?

Plusieurs possibilités :

• Je suis sur Bloctel. Ce n'était pas un de mes fournisseurs, ni une association, ni un journal. L'appel était donc forcément abusif.
• C'est pour vendre une formation CPF : ce genre de démarchage est interdit tout court, donc forcément abusif.
• C'est pour vendre de la rénovation énergétique : ce genre de démarchage est interdit tout court, donc forcément abusif.

Pour ce qui est de prouver que j'ai été appelé, lorsque je fais un signalement, je laisse mes coordonnées, donc au besoin je peux fournir mon journal d'appels et un enregistrement de la conversation.

Et si la DGCCRF décide de lancer des poursuites, ils demanderont à la police ou à la gendarmerie d'enquêter, et mon opérateur pourra sans problème confirmer que j'ai bien reçu l'appel en question.

C'était quand? On en parlait récemment après un article; et après une recherche rapide, j'ai pu confirmer qu'il y a une loi qui interdit tout démarchage pour une formation CPF, adoptée ce 8 décembre, avec 375 000 euros d'amende pour une personne morale (donc l'organisme de formation, mais aussi le sous-traitant? Ou l'un d'eux paye pour les 2? Ou ils partagent l'amende?).

Peut-être les deux. Mais pour répondre à la question, c'était avant cette loi, dont je ne pouvais pas me prévaloir. Sauf que je suis sur Bloctel, donc sauf quelques domaines bien précis dont la formation professionnelle ne fait pas partie, il est de toute façon interdit de me démarcher pour me vendre des trucs.

Vu la réaction du type que j'avais en face, ils avaient l'air plutôt conscients d'être hors-la-loi, ce qui suggère qu'ils l'étaient bel et bien. D'ailleurs ça me rappelle un peu mieux la fin du dialogue. Je n'avais pas raccroché aussi sec :

• Vous n'étiez pas intéressé par la formation ?
• Non, désolé, j'avais juste besoin d'informations pour le signalement.
• Pour signaler quoi ?
• Eh bien, votre appel illégal.
• Mais ça n'a rien d'illégal Monsieur !
• Dites, vous avez entendu parler de Bloctel ?
• Oui, bien sûr, et nous vérifions les gens que nous appelons.
• Ben non. J'y suis, sur Bloctel justement, donc vous n'aviez pas le droit de m'appeler.
• Mais si notre appel vous dérangeait, vous n'aviez qu'à dire que vous n'étiez pas intéressé. Pourquoi avez-vous fait croire que ça vous intéressait, vous nous avez tendu un piège ?
• C'est ça. Ça vous a plu ?
• Mais c'est dégueulasse ce que vous faites !
• Ah non, moi j'aide à faire respecter la loi. Ce que vous faites en revanche, c'est illégal. Si j'ai besoin d'une formation, je suis assez grand pour aller la chercher tout seul. Allez, bonne journée.

Si ce n'est pas en vigueur, quelle est la base pour dire que c'est illicite? C'est parce que tu es sur Bloctel (le cas "automatiquement illicite" que tu cites)? Parce qu'hormis cela, il faudrait par exemple prouver qu'ils ont eu ton numéro de manière illicite (c'est à dire qu'un organisme leur a donné alors que tu avais explicité refusé, ou simplement rien accepté; mais comment prouver cela?).

Bloctel en effet. Mais pour aller plus loin, lorsqu'on fait l'objet d'un traitement de données, et le démarchage téléphonique inclut évidemment un traitement de données, au minimum les numéros de téléphone, on a le droit d'accéder à ces données, qui doivent inclure leur origine. Une boîte qui refuse de fournir les données qu'elle a sur celui qui le demande, ou qui refuse de préciser d'où ils les tiennent, est déjà en violation de la loi.

Sinon similairement à ǝpɐןƃu∀ nǝıɥʇʇɐW-ǝɹɹǝıԀ plus bas, il y a aussi la question de savoir s'ils auront vraiment une amende. Ils pourraient se retourner en disant qu'ils n'ont jamais appelé (c'est alors une parole contre une autre). Pour vérifier les dires, il faudrait qu'un juge acte pour avoir accès aux appels téléphoniques, mais le feraient-ils sur le signalement d'une personne seulement (je doute malheureusement que beaucoup signalent et au final, chaque organisme a probablement un ou 2 signalements à peine à leur actif)?

Alors pour la preuve, j'ai mon journal d'appel, et au besoin un enregistrement de la conversation. Ah oui, j'oubliais de le préciser, j'enregistre. Sans le dire, sinon ils raccrochent direct, donc c'est un peu limite comme preuve, mais la jurisprudence évolue un peu sur le sujet.

Pour les plaintes à propos de démarchage au CPF, ça peut aussi se faire directement sur cette plate-forme, et je suppose qu'ils en tiennent un peu compte quand même, vu le niveau d'arnaques qu'il y a eu. Mais autrement, c'est vrai, je n'ai aucune certitude que ce sera suivi d'effets. La seule certitude que j'ai, c'est que si personne ne signale les abus, ils ne seront jamais sanctionnés.

J'ai un dernier cas: des fois, on reçoit des appels et quand on répond, il n'y a rien. Personne parle. Ça m'arrive de temps en temps. Mais je ne saurais pas classer cela.

Ça vient de robots d'appels. Le principe, c'est que la boîte de démarchage a un vrai centre d'appel dédié à cela, et un robot qui appelle des gens à un rythme calculé selon la disponibilité des esclaves employés. Lorsque quelqu'un répond, il lui passe le premier troufion disponible, mais parfois il n'y en a pas, et l'appelé se retrouve en attente.

Il va sans dire que je ne suis pas pleinement satisfait de la recherche en semi-force brute pour la deuxième étape, intellectuellement parlant.

Mais bon, la flemme de concevoir et d'implémenter un algorithme d'union de parallélogrammes. Il y a des tas de cas, et autant avec des rectangles ça se fait bien en itérant sur chaque coordonnée, autant avec les parallélogrammes, c'est compliqué.

Voilà, avec une implémentation des unions d'intervalles sécants.

from __future__ import annotations

import re

from collections import namedtuple
from typing import Tuple, Iterable, List, Optional, Type

import aoc


Coords = Tuple[int, int]


class Point(namedtuple('Point', ['x', 'y'])):
    __slots__ = ()

    def __str__(self) -> str:
        return "({},{})".format(self.x, self.y)

    def dist(self, other: Point) -> int:
        return abs(self.x - other.x) + abs(self.y - other.y)


class Interval:
    def __init__(self, start: int, end: int) -> None:
        if start >= end:
            raise ValueError("unsupported empty or negative interval")
        self.start = start
        self.end = end

    def __str__(self) -> str:
        return "[{},{}[".format(self.start, self.end)

    def __len__(self) -> int:
        return self.end - self.start

    def __contains__(self, value: int) -> bool:
        return value >= self.start and value < self.end

    def intersects(self, other: Interval) -> bool:
        return max(self.start, other.start) < min(self.end, other.end)

    def union_update(self, other: Interval) -> bool:
        if not self.intersects(other):
            return False
        self.start = min(self.start, other.start)
        self.end = max(self.end, other.end)
        return True


class Sensor:
    def __init__(self, position: Point, beacon: Point):
        self.position = position
        self.beacon = beacon
        self.range = position.dist(beacon)

    def covers(self, y: int) -> bool:
        dist = abs(y - self.position.y)
        return dist <= self.range

    def coverage(self, y: int) -> Optional[Interval]:
        if not self.covers(y):
            return None
        else:
            dist = abs(y - self.position.y)
            return Interval(self.position.x - self.range + dist,
                            self.position.x + self.range + 1 - dist)

    re_line = re.compile(r'^Sensor at x=(-?\d+), y=(-?\d+): '
                         + r'closest beacon is at x=(-?\d+), y=(-?\d+)\n?$')

    @classmethod
    def import_line(class_, line: str) -> Sensor:
        match = class_.re_line.match(line)
        if match is None:
            raise ValueError("invalid sensor description")
        position = Point(int(match.group(1)), int(match.group(2)))
        beacon = Point(int(match.group(3)), int(match.group(4)))
        return class_(position, beacon)


class SensorArray:
    def __init__(self, sensors: Iterable[Sensor]):
        self.sensors = list(sensors)

    @classmethod
    def import_lines(class_, lines: Iterable[str]) -> SensorArray:
        return class_(Sensor.import_line(line) for line in lines)

    def coverage(self, y: int) -> List[Interval]:
        intervals: List[Interval] = []
        for sensor in self.sensors:
            if not sensor.covers(y):
                continue
            new_interval = sensor.coverage(y)
            if new_interval is None:
                continue
            new_intervals: List[Interval] = []
            for interval in intervals:
                if not new_interval.union_update(interval):
                    # new_interval did not absorb interval
                    new_intervals.append(interval)
            new_intervals.append(new_interval)
            intervals = new_intervals
        return intervals


def solve1(lines: Iterable[str]) -> int:
    """Solve part 1 of today's puzzle"""
    array = SensorArray.import_lines(lines)
    beacons = {sensor.beacon for sensor in array.sensors}
    y = 2000000
    coverage = array.coverage(y)
    total = 0
    for interval in coverage:
        total += len(interval)
        total -= sum((beacon.y == y and beacon.x in interval)
                     for beacon in beacons)
    return total


def solve2(lines: Iterable[str]) -> int:
    """Solve part 2 of today's puzzle"""
    array = SensorArray.import_lines(lines)
    position: Optional[Point] = None
    for y in range(4000000):
        if y % 100000 == 0:
            print(y)
        coverage = array.coverage(y)
        if len(coverage) < 2:
            continue
        return min(interval.end for interval in coverage) * 4000000 + y
    raise ValueError("no solution found")

Un détail tout de même, ça semble évident mais ça peut demander un peu de concentration pour ne pas l'oublier en court de route : tant que vous n'êtes pas arrivé à vos fins, c'est à dire que vous n'avez pas assez d'informations, il ne faut pas donner le moindre indice qui laisserait soupçonner que vous n'appréciez pas ce démarchage.

Éviter par exemple des phrases comme « Au fait, comment avez-vous eu mon numéro de téléphone ? » Si votre interlocuteur commence à soupçonner que son appel vous dérange, il risque de ne pas vous croire si vous vous prétendez intéressé, et l'appel ne durera pas longtemps. Pas assez longtemps pour obtenir les infos que vous souhaitez en tout cas.

Ces démarcheurs savent très bien que ce qu'ils font est illégal, même s'ils prétendent parfois le contraire. Et sachant qu'ils peuvent être poursuivis, ou avoir diverses emmerdes comme être radiés de la plate-forme CPF, ils commencent à être assez méfiants.

L'autre jour, j'ai oublié ce principe et demandé directement à une démarcheuse où elle travaillait. Elle m'a fait répéter la question, et après avoir compris ma demande, elle a raccroché sans y mettre la moindre forme. Ni refus, ni excuse, ni au-revoir, juste raccroché. Si ce n'est pas de la méfiance, ça…

À titre d'exemple, j'ai pu piéger une entreprise de formation professionnelle qui se livrait au démarchage téléphonique. Sans doute sous-traité, mais ce n'est pas mon problème, les agissements d'un sous-traitant engagent évidemment la responsabilité de son donneur d'ordre.

Je me suis montré intéressé par une formation en langue anglaise, très utile pour mon travail. Le démarcheur m'a alors fait rappeler par un responsable des inscriptions, et je m'attendais au pire, c'est à dire à ce qu'il me demande mon numéro de sécurité sociale et qu'il réinitialise avec mon aide mon mot de passe pour accéder lui-même à mon compte CPF et m'inscrire à sa formation. Ç'aurait été une arnaque selon les règles, mais non, c'était un peu plus honnête, il m'a juste demandé mon adresse électronique, celle inscrite sur le compte CPF, ce qui lui a suffit à me pré-inscrire à des formations.

Vérification faite, les formations apparaissaient bien comme des propositions à valider, avec un organisme de formation tout à fait identifiable, en tout cas par la plate-forme CPF. J'en avais assez, et la fin de la discussion téléphonique a été assez intéressante :

• C'est bon, je vois bien les formations. Je vous remercie, j'ai toutes les informations qu'il me faut.
• Attendez, je peux vous expliquer la façon dont les formations vont se passer.
• Ce ne sera pas nécessaire, vraiment, j'ai tout ce qu'il me faut.
• Non, je ne vous ai pas expliqué…
• Si si, j'en sais assez je vous dit.
• Assez pour quoi ?
• Assez pour signaler votre démarchage illicite.
• Vous n'étiez pas intéressé par la formation ?
• Non, désolé, j'avais juste besoin d'informations pour le signalement.
• Vous nous avez tendu un piège alors ?
• C'est ça. Ça vous a plu ?
• Mais c'est dégueulasse ce que vous faites !
• Ah non, moi j'aide à faire respecter la loi. Ce que vous faites en revanche, c'est illégal. Si j'ai besoin d'une formation, je suis assez grand pour aller la chercher tout seul. Allez, bonne journée.

Avec ladite optimisation :

from __future__ import annotations

import enum
import io
import itertools

from typing import Iterable, Iterator, List, Tuple

import numpy as np
import numpy.typing as npt


Coords = Tuple[int, int]


class Material(enum.Enum):
    AIR = enum.auto()
    ROCK = enum.auto()
    SAND = enum.auto()


class Slice:
    def __init__(self, array: npt.ArrayLike, leak: Coords) -> None:
        self.matrix: npt.NDArray = np.array(array)
        self.leak = leak

    def pour(self) -> Iterator[bool]:
        """Inject a unit of sand.

        Yields False if it was blocked, True if it fell into the void.
        Stops when the leak is clogged up by a mountain of sand."""
        # List of coordinates to pour sand from
        sources: List[Coords] = []
        # Start at the original leak
        y, x = self.leak
        while True:
            # Our unit of sand is injected at current coordinates (y, x)
            while y < self.matrix.shape[0] - 1:
                y_ = y + 1
                for x_ in (x, x - 1, x + 1):
                    if self.matrix[y_, x_] is Material.AIR:
                        # Sand can flow down:
                        # * current coordinate is a good place to pour next
                        #   sand unit from;
                        sources.append((y, x))
                        # * current sand unit falls down one level.
                        y = y_
                        x = x_
                        break
                else:
                    # Ways down exhausted, sand is blocked
                    self.matrix[y, x] = Material.SAND
                    # Get out of the descent loop
                    break
            else:
                # Descent ended, sand fell all the way down
                yield True
                continue
            # Descent did not end, sand got blocked
            yield False
            if not sources:
                # Nowhere to pour sand from, even the leak is clogged up
                break
            # Pour next sand unit from last good place
            y, x = sources.pop()

    def __str__(self) -> str:
        result = io.StringIO()
        for line in self.matrix:
            for point in line:
                if point is Material.AIR:
                    result.write(' ')
                elif point is Material.ROCK:
                    result.write('█')
                elif point is Material.SAND:
                    result.write('░')
                else:
                    assert False  # we covered all cases
            result.write('\n')
        return result.getvalue()

    def add_segment(self, start: Coords, end: Coords) -> None:
        y1, x1 = start
        y2, x2 = end
        if y1 == y2:
            x1, x2 = min(x1, x2), max(x1, x2)
            ys = (y1 for _ in range(x1, x2 + 1))
            xs = (x for x in range(x1, x2 + 1))
        elif x1 == x2:
            y1, y2 = min(y1, y2), max(y1, y2)
            ys = (y for y in range(y1, y2 + 1))
            xs = (x1 for _ in range(y1, y2 + 1))
        for y, x in zip(ys, xs):
            self.matrix[y, x] = Material.ROCK


def import_segments(
        lines: Iterable[str]
        ) -> Tuple[List[Coords], List[Tuple[Coords, Coords]]]:
    points: List[Coords] = []
    segments: List[Tuple[Coords, Coords]] = []

    def coords(word: str) -> Coords:
        parts = word.split(',')
        if len(parts) != 2:
            raise ValueError("unexpected number of coordinates")
        return int(parts[1]), int(parts[0])

    for line in lines:
        words = line.rstrip().split(' -> ')
        segment_points = [coords(word) for word in words]
        points.extend(segment_points)
        segments.extend(itertools.pairwise(segment_points))
    return points, segments


def import_slice1(lines: Iterable[str]) -> Slice:
    points, segments = import_segments(lines)
    y_leak, x_leak = 0, 500
    points.append((y_leak, x_leak))
    xmin = min(x for _, x in points) - 1
    xmax = max(x for _, x in points) + 1
    ymin = min(y for y, _ in points)
    ymax = max(y for y, _ in points)
    if ymin < 0:
        raise ValueError("unexpected negative coordinate")
    xshift = xmin
    matrix = np.full(((ymax + 1), xmax - xshift + 1), Material.AIR)
    result = Slice(matrix, (0, 500 - xshift))
    for (y1, x1), (y2, x2) in segments:
        result.add_segment((y1, x1 - xshift), (y2, x2 - xshift))
    return result


def import_slice2(lines: Iterable[str]) -> Slice:
    points, segments = import_segments(lines)
    y_leak, x_leak = 0, 500
    points.append((y_leak, x_leak))
    xmin = min(x for _, x in points)
    xmax = max(x for _, x in points)
    ymin = min(y for y, _ in points)
    ymax = max(y for y, _ in points) + 2  # including the floor
    # Update xmin and xmax to accomodate a pyramid of sand
    xmin = min(xmin, x_leak - (ymax - y_leak))
    xmax = max(xmax, x_leak + (ymax - y_leak))
    if ymin < 0:
        raise ValueError("unexpected negative coordinate")
    xshift = xmin
    matrix = np.full(((ymax + 1), xmax - xshift + 1), Material.AIR)
    result = Slice(matrix, (0, 500 - xshift))
    for (y1, x1), (y2, x2) in segments:
        result.add_segment((y1, x1 - xshift), (y2, x2 - xshift))
    result.add_segment((ymax, xmin - xshift), (ymax, xmax - xshift))
    return result


def solve1(lines: Iterable[str]) -> int:
    """Solve part 1 of today's puzzle"""
    slice_ = import_slice1(lines)
    for i, fallen in enumerate(slice_.pour()):
        if fallen:
            return i
    raise ValueError("Simulation ended with unexpected sand leak clogged")


def solve2(lines: Iterable[str]) -> int:
    """Solve part 2 of today's puzzle"""
    slice_ = import_slice2(lines)
    for i, fallen in enumerate(slice_.pour()):
        if fallen:
            raise ValueError("Simulation ended with unexpected sand under the floor")
    return i + 1

Bravo pour l'implémentation de mon idée !

Visiblement, il y a une optimisation possible : une si un grain de sable, lâché du point de départ, tombe à un endroit, on peut lâcher ce grain et les suivants de cet endroit, jusqu'à ce qu'il soit ensablé…

Je me demande s'il ne serait pas possible de résoudre la partie 2 bien plus vite, en calculant l'aire des zones protégées par des rochers.

En effet, le nombre d'unités de sables tombées, c'est l'aire d'une triangle plein, moins celle des rochers qu'il contient, moins l'aire des zones protégées par ces derniers.

Ceci dit, déterminer la zone protégée par l'ensemble des rochers, c'est loin d'être évident. La zone protégée par un segment horizontal, c'est facile, c'est un triangle dessous. La zone protégée par un segment vertical, c'est facile, c'est rien du tout. Mais quand on commence à avoir des segments horizontaux et verticaux qui se touchent, ça devient compliqué.

Allez, une autre piste, sans doute pas beaucoup plus simple. On dirait qu'on peut déterminer la zone protégée par des rochers, non pas seulement par calcul, mais aussi par une simulation bizarre : faire couler de l'air depuis le bas vers le haut et regarder où il s'accumule. Mais ça pose le problème d'introduire cet air : il faut qu'il s'accumule et qu'il traverse en même temps les segments…

from __future__ import annotations

import enum
import io
import itertools

from typing import Iterable, List, Tuple

import numpy as np
import numpy.typing as npt


Coords = Tuple[int, int]


class Material(enum.Enum):
    AIR = enum.auto()
    ROCK = enum.auto()
    SAND = enum.auto()


class Slice:
    def __init__(self, array: npt.ArrayLike, leak: Coords) -> None:
        self.matrix: npt.NDArray = np.array(array)
        self.leak = leak

    def pour(self) -> bool:
        """Inject a unit of sand.

        Return False if it was blocked, True if it fell into the void."""
        y, x = self.leak
        while y < self.matrix.shape[0] - 1:
            y_ = y + 1
            for x_ in (x, x - 1, x + 1):
                if self.matrix[y_, x_] is Material.AIR:
                    # Sand can flow down
                    y = y_
                    x = x_
                    break
            else:
                # Blocked
                self.matrix[y, x] = Material.SAND
                return False
        # Sand fell all the way down into the void
        return True

    def __str__(self) -> str:
        result = io.StringIO()
        for line in self.matrix:
            for point in line:
                if point is Material.AIR:
                    result.write(' ')
                elif point is Material.ROCK:
                    result.write('█')
                elif point is Material.SAND:
                    result.write('░')
                else:
                    assert False  # we covered all cases
            result.write('\n')
        return result.getvalue()

    def add_segment(self, start: Coords, end: Coords) -> None:
        y1, x1 = start
        y2, x2 = end
        if y1 == y2:
            x1, x2 = min(x1, x2), max(x1, x2)
            ys = (y1 for _ in range(x1, x2 + 1))
            xs = (x for x in range(x1, x2 + 1))
        elif x1 == x2:
            y1, y2 = min(y1, y2), max(y1, y2)
            ys = (y for y in range(y1, y2 + 1))
            xs = (x1 for _ in range(y1, y2 + 1))
        for y, x in zip(ys, xs):
            self.matrix[y, x] = Material.ROCK


def import_segments(
        lines: Iterable[str]
        ) -> Tuple[List[Coords], List[Tuple[Coords, Coords]]]:
    points: List[Coords] = []
    segments: List[Tuple[Coords, Coords]] = []

    def coords(word: str) -> Coords:
        parts = word.split(',')
        if len(parts) != 2:
            raise ValueError("unexpected number of coordinates")
        return int(parts[1]), int(parts[0])

    for line in lines:
        words = line.rstrip().split(' -> ')
        segment_points = [coords(word) for word in words]
        points.extend(segment_points)
        segments.extend(itertools.pairwise(segment_points))
    return points, segments


def import_slice1(lines: Iterable[str]) -> Slice:
    points, segments = import_segments(lines)
    y_leak, x_leak = 0, 500
    points.append((y_leak, x_leak))
    xmin = min(x for _, x in points) - 1
    xmax = max(x for _, x in points) + 1
    ymin = min(y for y, _ in points)
    ymax = max(y for y, _ in points)
    if ymin < 0:
        raise ValueError("unexpected negative coordinate")
    xshift = xmin
    matrix = np.full(((ymax + 1), xmax - xshift + 1), Material.AIR)
    result = Slice(matrix, (0, 500 - xshift))
    for (y1, x1), (y2, x2) in segments:
        result.add_segment((y1, x1 - xshift), (y2, x2 - xshift))
    return result


def import_slice2(lines: Iterable[str]) -> Slice:
    points, segments = import_segments(lines)
    y_leak, x_leak = 0, 500
    points.append((y_leak, x_leak))
    xmin = min(x for _, x in points)
    xmax = max(x for _, x in points)
    ymin = min(y for y, _ in points)
    ymax = max(y for y, _ in points) + 2  # including the floor
    # Update xmin and xmax to accomodate a pyramid of sand
    xmin = min(xmin, x_leak - (ymax - y_leak))
    xmax = max(xmax, x_leak + (ymax - y_leak))
    if ymin < 0:
        raise ValueError("unexpected negative coordinate")
    xshift = xmin
    matrix = np.full(((ymax + 1), xmax - xshift + 1), Material.AIR)
    result = Slice(matrix, (0, 500 - xshift))
    for (y1, x1), (y2, x2) in segments:
        result.add_segment((y1, x1 - xshift), (y2, x2 - xshift))
    result.add_segment((ymax, xmin - xshift), (ymax, xmax - xshift))
    return result


def solve1(lines: Iterable[str]) -> int:
    """Solve part 1 of today's puzzle"""
    slice_ = import_slice1(lines)
    for i in range(10000):
        if slice_.pour():
            return i
    raise ValueError("Simulantion did not end within expected limit")


def solve2(lines: Iterable[str]) -> int:
    """Solve part 2 of today's puzzle"""
    slice_ = import_slice2(lines)
    for i in range(100000):
        _ = slice_.pour()
        if slice_.matrix[slice_.leak] is Material.SAND:
            return i + 1
    raise ValueError("Simulantion did not end within expected limit")