🚲 Tanguy Ortolo a écrit 12270 commentaires

À noter que cela permet autre chose d'intéressant, si le concepteur du langage y a pensé : utiliser cette notion de valeur de retour au niveau, non pas seulement de la fonction, mais plus généralement du bloc de code. Vous savez, le bloc, une portion de code entre accolades par exemple. Dans les langages où c'est défini, ça sert entre autres pour la portée des variables, mais ça permet aussi de grouper des instructions et de définir les structures de contrôle comme travaillant sur des blocs.

Bref, en clair, cette idée de valeur de retour peut permettre des trucs comme ça :

n = 3
printf("Il y a %d %s", n, if n <= 1 {
    "vélo"
} else {
    "vélos"
})

Autant que je sache, ça vient d'habitudes de langages de programmation fonctionnelle. J'ai en tête Caml par exemple. Si je me souviens bien, l'idée est qu'il n'est pas normal de faire quoi que ce soit qui retourne une valeur sans faire quelque chose de cette valeur : l'affecter à une variable par exemple.

Du coup, dans la définition d'une fonction, on s'attend à ce qu'aucune ligne ne laisse de valeur implicitement jetée à la poubelle. Et il devient du coup plus ou moins naturel que, lorsqu'une ligne, une seule, la dernière, laisse une valeur, ce soit la valeur de retour de la fonction.

On peut voir les choses autrement. Une fonction est comme l'objet du même type en mathématiques : quelque chose qui prend des valeurs et fournit une valeur. Or en maths, on écrit fort naturellement (ou pas) des choses comme : f: x ↦ x². Et certainement pas f: x ↦ return x².

Sans les ingrédients, j'ai bien peur que ce soit assez ambigu malheureusement.

la possibilité de lire des fichiers dans plusieurs années (je pense à des fichiers Publisher 2.0 que je ne suis plus parvenu à lire par la suite – et non : les versions ultérieures à Publisher 2.0 ne lisent pas ces fichiers.

Ça, c'est un problème réservé aux utilisateurs de logiciels propriétaires. Ça peut éventuellement arriver avec du logiciel libre pour des usages de niche.

Mais pour des trucs comme l'image, la vidéo et le son, dès que tu utilises des formats ouverts un minimum connus, tu peux être certain de pouvoir les relire… tant qu'on aura des ordinateurs et des logiciels.

Avec des formats standardisés, tu as aussi une assez bonne garantie de pouvoir les relire plus tard.

À noter que le fait qu'il y ait une plainte qui aboutisse ne changerait strictement rien pour la suite : chaque cas d'abus nécessite une plainte pour être sanctionné.

Je veux dire, si je suis une entreprise prête à abuser des données personnelles de gens, je sais que je cours un risque en le faisant. Le fait qu'il y ait un précédent juridique ou non ne change rien au risque en question, puisque la loi est écrite d'une façon qui ne laisse aucune ambiguïté : ce que je fais est illégal et, en cas de procès, sera sans aucun doute considéré comme tel.

C'est à dire que les boîtes qui pratiquent ce genre d'abus n'en ont juste rien à torcher de la loi, comptant sur le fait que personne ne se plaindra. À ce compte-là, autant déconner à plein tube, pas la peine de se faire chier à respecter quoi que ce soit du RGPD en fait.

C'est la théorie, mais la pratique c'est que tant qu'il n'y a pas de plainte et de jugement qui explicite que le "consentement" recueilli n'est pas valable tout le monde s'en fiche. C'est ce que les ricains appellent le "court testing".

Une défense d'une entreprise qui se prémunirait d'un consentement recueilli par case pré-cochée ne tiendrait pas une seconde devant un tribunal, tellement le RGPD est clair. Préambule, paragraphe 32 :

Le consentement devrait être donné par un acte positif clair par lequel la personne concernée manifeste de façon libre, spécifique, éclairée et univoque son accord au traitement des données à caractère personnel la concernant, par exemple au moyen d'une déclaration écrite, y compris par voie électronique, ou d'une déclaration orale. Cela pourrait se faire notamment en cochant une case lors de la consultation d'un site internet, en optant pour certains paramètres techniques pour des services de la société de l'information ou au moyen d'une autre déclaration ou d'un autre comportement indiquant clairement dans ce contexte que la personne concernée accepte le traitement proposé de ses données à caractère personnel. Il ne saurait dès lors y avoir de consentement en cas de silence, de cases cochées par défaut ou d'inactivité.

Ce n'est même pas une déduit du texte, c'est écrit dedans de façon on ne peut plus explicite. Le juge est parfois là pour essayer de deviner l'intention du législateur, mais là il n'y a aucune place pour une interprétation quelconque, c'est juste écrit noir sur blanc : il n'y a pas de consentement par cas pré-cochée. Fin de la discussion.

C'est moins craignos en effet, mais quand même illégal. Il s'agit d'un traitement de données personnelles effectué sans consentement.

Ah, au fait, à propos de consentement, il y a un truc important à savoir. Pour qu'un traitement de données personnelles destiné à une prospection commerciale soit légal, il faut un consentement libre, spécifique, éclairé et univoque :

• Libre : le fait de refuser un traitement qui n'est pas nécessaire ne doit pas avoir d'impact sur un service. Par exemple, si un site de vente exige que vous consentiez à recevoir des messages de prospection pour que vous puissiez acheter des produit, eh bien ce consentement n'est pas libre et n'est donc pas valide.
• Spécifique : lorsqu'il y a plusieurs traitements de données on doit pouvoir consentir de façon indépendante à chacun d'entre eux.
• Éclairé : le responsable du traitement doit être précisé, ainsi que le but du traitement, les données collectées, etc.
• Univoque, le plus important : le consentement doit être donné par un acte positif univoque. Genre cocher une case. Le fait de ne pas décocher une case pré-cochée n'est, par définition, pas un acte positif, par conséquent : les cases pré-cochées ne peuvent pas produire un consentement valide.

Donc, en particulier, si vous avez comme moi pris l'habitude de ne jamais cocher les cases de consentement au partage de vos données personnelles, vous pouvez être sûr que tout traitement de vos données personnelles par une entreprise avec laquelle vous n'avez jamais été en rapport est illégal puisque vous n'y avez jamais explicitement consenti. Et si vous avez laissé une case pré-cochée, aucune importance, ces saloperies ne valent pas consentement.

C'est amusant, il m'est arrivé presque la même chose, en France, à peu près au même moment. Merci d'en avoir fait un journal d'ailleurs.

Dans mon cas, c'était une lettre m'annonçant l'ouverture d'un genre de centre commercial multi-marques à Giverny. Un truc donc je n'ai strictement rien à cirer, c'est à une heure de bagnole de chez moi et j'ai mieux à faire de mon temps que de rouler pour aller passer une journée à faire des courses, merci.

Bref, comme c'était du courrier adressé, je les ai aussitôt contactés par courrier électronique pour leur demander l'intégralité des données personnelles qu'ils avaient sur moi et d'où ils les sortaient. À noter que c'est tout ce que je leur demandais, en particulier, je ne leur ai à ce moment-là pas du tout demandé de supprimer quoi que ce soit.

Réponse : ça vient d'un partenaire. Point. Pas plus de détail. Ils n'avaient manifestement pas compris ou pas voulu comprendre ma demande, donc je leur réponds en leur rappelant que je leur demande communication de ces données et que je veux savoir de quel partenaire il s'agit, avec adresse et numéro SIRET ou enregistrement au RCS, merci.

Pas de réponse en quinze jours. Je décide de les dénoncer à la Cnil, et je les en informe au passage. Et là, ils répondent – mais trop tard, la Cnil est déjà au courant qu'ils déconnent – en m'expliquant qu'ils n'ont pas de données sur moi, qu'ils ont juste demandé à Mediapost de faire une campagne de publicité pour leur compte. C'est donc Mediapost qui a des données sur moi, et ils leur transmettent ma demande de suppression. Ma demande de suppression, quelle demande de suppression ‽ Je n'ai jamais rien demandé de tel moi !

Bref. Pour info, c'est comme dans ton cas, parce que Mediapost c'est La Poste française. Qui évidemment ont moyen d'avoir des infos sur à peu près tout le monde. Et n'ont absolument pas le droit de les collecter ou pire, de les utiliser comme ça.

Une autre chose que je remarque presque tout le temps, lorsqu'on écrit à une entreprise pour leur demander les données personnelles relatives à un envoi publicitaire, s'ils répondent, c'est presque tout le temps pour indiquer :

• soit que c'est un partenaire, sans plus de précision, ce qui ne répond pas à la demande ;
• soit pour expliquer qu'ils ont bien pris en compte la demande de suppression, ce qui ne répond pas non plus à la demande.

Et pour le prix au kilo d'un emmental français râpé, on peut se payer un truc nettement plus qualitatif. Peut-être pas du Comté, mais au moins un Truc de Savoie AOP.

Notes d'implémentation :

• On fait pas mal de calculs sur des entiers qu'on finit à un moment ou à un autre par diviser. Le meilleur type de données pour cela, c'est à mon avis une implémentation des rationnels. En Python, c'est fractions.Fraction.
• On est dans de la géométrie, on fait des produits scalaires, des produits vectoriels, des additions, des soustractions, des multiplications par un scalaire… C'est parfait pour implémenter une classe Vector et des opérateurs variés. En Python, on peut par exemple définir des méthodes qui réutilisent les opérateurs standard de façon habituelle ou futée (vous allez comprendre…) :
  • __rmul__ pour le produit par un scalaire alpha * v ;
  • __xor__ pour le produit vectoriel v ^ w ;
  • __add__ et __sub__ pour l'addition et la soustraction vectorielles ;
  • __neg__ pour l'opposition ;
  • __floordiv__ pour le test de colinéarité v // w ;
  • __bool__ pour le test de non-nullité (permet d'écrire des trucs comme if vector).
• Enfin, on va travailler avec des droites, des plans, là aussi c'est parfait pour faire de la belle modélisation avec des méthodes permettant d'utiliser des opérateurs comme //, ==, etc.

Pour déterminer la position de départ donc, la première idée consiste à chercher l'intersection de deux trajectoires corrigées. Une intersection de droites donc. Sauf que c'est assez moche à calculer, on peut faire plus élégant.

Les trajectoires corrigées étant toutes sécantes au même point, celui qu'on recherche, en les prenant deux par deux on peut définir des plans. Il est temps d'ouvrir une petite parenthèse.

Plan défini par deux droites

Dans l'espace, deux droites peuvent définir un plan, à condition nécessaire et suffisante qu'elles soient soit parallèles mais non identiques, soit sécantes.

Soient deux droites pertinentes selon cette condition et définies chacune par un point et par un vecteur (p0, v0) et (p1, v1). On cherche à caractériser leur plan commun, par un point et un vecteur normal.

Si elles ne sont pas parallèles, leurs vecteurs directeurs v0 et v1 ne sont pas colinéaires. Leur produit vectoriel n = v0 ^ v1 est non nul et orthogonal aux deux droites et fait donc un très bon vecteur normal pour le plan cherché.

Si elles sont parallèles leurs vecteurs directeurs sont certes colinéraires, mais p0 - p1 n'est pas colinéaire à ces derniers (sinon, vous pouvez vérifier, les droites seraient identiques). On peut donc choisir n = v0 ^ (p0 - p1) comme vecteur normal pour le plan cherché.

Il nous reste à trouver un point sur le plan cherché : c'est trivial, il suffit de prendre par exemple p0 puisque ce plan contient par définition la première droite. Pour obtenir une équation de plan du type n ⋅ r = d, il suffit de prendre d = p0 ⋅ n.

En fait, nous nous intéressons seulement au cas de droites sécantes, voici donc le calcul pour obtenir l'équation du plan dans ce cas spécifique :

n = v0 ^ v1
d = p0 ⋅ n

n ⋅ r = d

Retour au problème

En prenant les trajectoires corrigées deux par deux, on peut définir un tas de plans contenant tous le point cherché. Or l'intersection de trois plans non parallèles est un point, qui sera forcément ce dernier ! Ouvrons une nouvelle parenthèse.

Intersection de plans

Allons-y pour l'intersection de trois plan non parallèles (p0, d0), (p1, d1) et (p2, d2).

Le point d'intersection, que nous allons noter r, respecte les équation des trois plans :

n0 ⋅ r = d0
n1 ⋅ r = d1
n2 ⋅ r = d2

L'astuce consiste ici à choisir une base vectorielle alternative :

u0 = n1 ^ n2
u1 = n2 ^ n0
u2 = n0 ^ n1

En exprimant la position cherchée comme combinaison de ces trois vecteurs r = a0 u 0 + a1 u1 + a2 u2, l'équation du premier plan devient :

n0 ⋅ (a0 u0 + a1 u1 + a2 u2)         = d0
a0 n0 ⋅ u0 + a1 n0 ⋅ u1 + a2 n0 ⋅ u2 = d0
a0 n0 ⋅ u0 + a1 × 0     + a2 × 0     = d0
a0 n0 ⋅ (n1 ^ n2)                    = d0

On peut reconnaître ici le produit mixte de nos trois vecteurs normaux, un scalaire que l'on va noter U = n0 ⋅ (n1 ^ n2). Les trois équations deviennent de la même façon :

a0 U = d0
a1 U = d1
a2 U = d2

Ce qui nous donne finalement ces fameux coefficients :

a0 = d0 / U
a1 = d1 / U
a2 = d2 / U

Qui nous donnent donc le vecteur position de l'intersection de nos trois plans. Pour rappel, voici les calculs à effectuer à partir des constantes définissant les trois plans :

u0 = n1 ^ n2
u1 = n2 ^ n0
u2 = n0 ^ n1

U = n0 ⋅ (n1 ^ n2)

a0 = d0 / U
a1 = d1 / U
a2 = d2 / U

r = a0 u0 + a1 u1 + a2 u2

Re-retour au problème

En prenant trois trajectoires corrigées (p0, v0 - v), (p1, v1 - v) et (p2, v2 - v) , on sait désormais caractériser leurs plans communs deux à deux, soit trois plan. Et on sait également déterminer l'intersection de ces trois plan. Problème résolu !

Sommaire

• Des droites sécantes
• Retour au problème
• Plus de droites
• Récapitulons
• Et la position alors ?

Bon, c'est un problème de géométrie.

Je passe sur la première partie, trouver des intersections de ligne dans le plan c'est sans grand intérêt.

La seconde partie est beaucoup, beaucoup plus intéressante. J'ai vainement cherché une solution élégante avant d'en trouver une sur Reddit. Je vous l'explique.

À supposer que l'on trouve une position de départ p et une vitesse v qui permette de percuter tous les grêlons, en se plaçant dans le référentiel de notre projectile, ce sont tous les grêlons qui vont converger jusqu'à l'atteindre, chacun à son tour. Autrement dit, pour un grêlon (p0, v0), la droite (p0, v0 - v) passe par notre position de départ p. Et il en est de même pour les autres grêlons.

Par conséquent, les trajectoires corrigées des trois premiers grêlons (p0, v0 -v), (p1, v1 -v) et (p2, v2 -v) se coupent deux à deux en p. Il est temps d'ouvrir une parenthèse sur les droites sécantes.

Des droites sécantes

Dans l'espace, contrairement au plan, des droites peuvent être identiques, parallèles, sécantes ou… rien de tout ça.

Étant données deux droites caractérisées chacune par un point et un vecteur directeur l0 = (p0, v0) et l1 = (p1, v1), la première chose à vérifier est qu'elles ne sont ni identiques ni parallèles. Autrement dit, que leurs vecteurs directeurs ne sont pas colinéaires. Une façon de faire consiste à prendre leur produit vectoriel, qui ne doit pas être nul.

Si ces droites ne sont pas parallèles, les droites vectorielles associées (O, v0) et (O, v1), définissent un plan vectoriel. Ce plan vectoriel peut être caractérisé par un vecteur normal facile à construire par le produit vectoriel des vecteurs directeurs de ces deux droites : n = v0 ^ v1.

Le plan affine parallèle à ce plan vectoriel et incluant d0 a pour équation vectorielle r ⋅ n = p0 ⋅ n. Le plan affine incluant d1 a quant a lui pour équation vectorielle r ⋅ n = p1 ⋅ n.

Ces plans sont identiques si et seulement si p0 ⋅ n = p1 ⋅ n. Autrement dit, en revenant à la définition de ce vecteur normal n, si (p0 - p1) ⋅ (v0 ^ v1) = 0. Si ces plans sont identiques, les droites sont coplanaire, et n'étant pas parallèles, elles sont donc sécantes. Réciproquement, si les droites sont coplanaires, les plans sont identiques.

Retour au problème

Puisque le problème a une solution, les trajectoires corrigées de deux grêlons (p0, v0 - v) et (p1, v1 - v) sont sécantes. Bon, ok, à condition qu'elles ne soient pas identiques : si c'était le cas on prendrait juste une autre grêlon, on en a plein à notre disposition. Mais vous pouvez vérifier sur vos données, ce cas ne se présente pas. Par conséquent :

(p0 - p1) ⋅ ((v0 - v) ^ (v1 - v))               = 0
(p0 - p1) ⋅ (v0 ^ v1 - v0 ^ v - v ^ v1 + v ^ v) = 0
(p0 - p1) ⋅ (v0 ^ v1 + v ^ v0 - v ^ v1 + 0)     = 0
(p0 - p1) ⋅ (v0 ^ v1 + v ^ (v0 - v1))           = 0

En réorganisant un peu et en utilisant les propriété du produit mixte :

(p0 - p1) ⋅ ((v0 - v1) ^ v) = (p0 - p1) ⋅ (v0 ^ v1)
v ⋅ ((p0 - p1) ^ (v0 - v1)) = (p0 - p1) ⋅ (v0 ^ v1)

Donnons un nom à ces termes constants :

A0 = (p0 - p1) ^ (v0 - v1)
M0 = (p0 - p1) ⋅ (v0 ^ v1)

On a donc :

v ⋅ A0 = M0

Plus de droites

De la même façon, en utilisant une droite de plus, posons :

A0 = (p0 - p1) ^ (v0 - v1)
A0 = (p1 - p2) ^ (v1 - v2)
A0 = (p2 - p0) ^ (v2 - v0)

M0 = (p0 - p1) ⋅ (v0 ^ v1)
M0 = (p1 - p2) ⋅ (v1 ^ v2)
M0 = (p2 - p0) ⋅ (v2 ^ v0)

On a maintenant trois équations sur v :

v ⋅ A0 = M0
v ⋅ A1 = M1
v ⋅ A2 = M2

Pour résoudre ça simplement, il y a une astuce. On va utiliser une base vectorielle ainsi définie, avec des vecteurs conçus que chacun d'entre eux soit orthogonal à deux vecteurs des équations précédentes :

u0 = A1 ^ A2
u1 = A2 ^ A0
u2 = A0 ^ A1

Et écrire la vitesse que nous cherchons sur cette base : v = a0 u0 + a1 u1 + a2 u2. Les équations précédentes deviennent désormais :

v ⋅ A0 = a0 (A1 ^ A2) ⋅ A0 = M0
v ⋅ A1 = a1 (A2 ^ A0) ⋅ A1 = M1
v ⋅ A2 = a2 (A0 ^ A1) ⋅ A2 = M2

On peut reconnaître ici le produit mixte de nos vecteurs A0 et compagnie, que l'on va nommer A* = A0 ⋅ (A1 ^ A2), ce qui donne :

a0 A* = M0
a1 A* = M1
a2 A* = M2

Et finalement nos coefficients :

a0 = M0 / A*
a1 = M1 / A*
a2 = M2 / A*

Récapitulons

Avec les trois premiers grêlons, on calcule les vecteurs et scalaires constants suivants :

A0 = (p0 - p1) ^ (v0 - v1)
A0 = (p1 - p2) ^ (v1 - v2)
A0 = (p2 - p0) ^ (v2 - v0)

M0 = (p0 - p1) ⋅ (v0 ^ v1)
M0 = (p1 - p2) ⋅ (v1 ^ v2)
M0 = (p2 - p0) ⋅ (v2 ^ v0)

A* = A0 ⋅ (A1 ^ A2)

Puis les vecteurs suivants :

u0 = A1 ^ A2
u1 = A2 ^ A0
u2 = A0 ^ A1

Et enfin les coefficients suivants :

a0 = M0 / A*
a1 = M1 / A*
a2 = M2 / A*

La vitesse de notre projectile doit être :

v = a0 u0 + a1 u1 + a2 u2

Et la position alors ?

La vitesse, c'est bien, mais c'est surtout la position de départ qu'on nous demande. On va dire que c'est facile à déduire désormais : c'est l'intersection des trajectoires corrigées des deux premiers grêlons. Par exemple, on peut en prendre d'autres si on veut.

Sauf que non, ce n'est vraiment pas trivial à calculer, l'intersection de deux droites sécantes dans l'espace. Il y a encore une astuce, et celle-là est vraiment de moi. Je vous la donnerai plus tard, là je suis fatigué de raconter mes aventures mathématiques.

Un code de cette longueur, ça aurait valu la peine de le mettre ailleurs, là ça nous fait une page terriblement longue à parcourir.

Et vous, quels fromages utilisez-vous pour vos pâtes, ou autres préparations, sous quel format et avec quel résultat, et pour quel impact sur les finances ?

Du fromage acheté chez un producteur à l'occasion de vacances à la montagne. Ou du fromage acheté à la fromagerie de mon quartier. Ou au marché. Mais en aucun cas du fromage industriel pré-râpé.

Bref, du fromage en morceau que je râpe moi-même… ou que je demande au fromager de râper et de mettre dans une gamelle qui m'appartient. De l'achat en vrac quoi.

À noter que les exemples fournis en première partie ne s'appliquaient pas à la deuxième partie, et que cette dernière ne fournissait aucun exemple utilisable. J'ai trouvé ça vache.

En pratique, j'ai honte un peu, j'ai fini de coder en voiture (au volant oui, oui),

Non mais là, faut savoir s'arrêter quand même. Ce serait dommage de mourir ou de tuer quelqu'un pour cause d'AoC.

Bon, j'ai eu mon résultat en un peu moins d'une heure avec PyPy. Mais ça reste moche à mes yeux. À l'occasion, je m'essaierai à optimiser encore ça avec un découpage plus astucieux.

Ah, je crois que je devine la subtilité. En descendant la chaîne des workflows, ou plutôt la chaîne des règles et des workflows, on peut découper sur chaque test, ce qui fait au final beaucoup moins de pavés qu'en quadrillant l'espace entier.

Est-ce que tu découpes donc tout l'espace autour de chaque plan correspondant aux valeurs des seuils des critères des workflows ?

Je ne suis pas sûr de comprendre, et ne lisant pas la Haskell, je me demande si tu peux m'éclairer. Est-ce un genre de dichotomie que tu fais ? Sur quel critère découpes-tu ou non un pavé de valeurs ?

La première partie ne pose pas de problème particulier. La seconde en revanche, c'est une autre paire de manches.

Mon idée pour optimiser cela consiste à réduire le nombre de cas que l'on teste. En effet, les workflows ont des règles basées sur des seuils, et fondamentalement, il suffit de balayer l'ensemble des combinaisons de ces valeurs seuils pour pouvoir déterminer ce qui arrivera à l'importe quelle combinaison entre ces valeurs.

Il faut faire attention à la façon dont on définit les seuils en question, parce que les définitions utilisent les opérateurs < et > qui ne sont pas l'opposé l'un de l'autre. Bref, il y a un détail important que je ne donnerai pas ici.

Toujours est-il que, pour mes données, ça me ramène à 6,4 × 10⁹ = 6,4 milliards de possibilités. Et c'est un peu long à tester : à un rythme de l'ordre de 150.000 combinaisons par seconde, ça va me prendre une douzaine d'heures. Il faut que je trouve mieux que ça…

Pour ce problème, j'ai considéré qu'on n'était pas vraiment en deux dimensions, mais plutôt en trois. Parce que l'état d'un creuset, ce n'est pas seulement sa position sur le terrain, mais aussi le nombre de cases qu'il a parcouru dans une direction donnée… ce qui se représente également très bien par un nombre, que je considère comme une troisième coordonnée.

Ça permet de se ramener à un problème de parcours de proche en proche, avec une définition bien particulière des voisins d'un point.

Voici le code :

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

import numpy as np
import numpy.typing as npt


import aoc


class City:
    def __init__(self, array: Sequence[Sequence[int]]):
        self.matrix: npt.NDArray[np.ubyte] = np.array(array, dtype=np.ubyte)
        self.ly, self.lx = self.matrix.shape

    @classmethod
    def import_lines(cls, lines: Iterable[str]) -> Self:
        array = [[int(char) for char in line if char != '\n']
                 for line in lines]
        return cls(array)

    def walk(self, minturn, maxturn) -> int:
        # We will be using a matrix with three coordinates:
        # * z indicates how many steps were made in which direction:
        #   -             z <         0: starting, no previous steps!
        #   -         0 ≤ z <   maxturn: 1 to maxturn steps up ↑
        #   -   maxturn ≤ z < 2*maxturn: 1 to maxturn steps down ↓
        #   - 2*maxturn ≤ z < 3*maxturn: 1 to maxturn steps left ←
        #   - 3*maxturn ≤ z < 4*maxturn: 1 to maxturn steps right →
        visits: npt.NDArray[np.int_] = np.full(
                (4 * maxturn, self.ly, self.lx), -1, dtype=np.int_)

        def _neighs(z: int, y: int, x: int) -> Iterator[tuple[int, int, int]]:
            """Yield all directly accessible neighbors of a point, including
            points outside the limits of the city."""
            if z < 0:
                # Special case for start
                yield (0 * maxturn, y - 1, x)
                yield (1 * maxturn, y + 1, x)
                yield (2 * maxturn, y, x - 1)
                yield (3 * maxturn, y, x + 1)
                return
            div, mod = divmod(z, maxturn)
            if div == 0:
                if mod < maxturn - 1:
                    yield (z + 1, y - 1, x)
                if mod + 1 >= minturn:
                    yield (2 * maxturn, y, x - 1)
                    yield (3 * maxturn, y, x + 1)
                return
            if div == 1:
                if mod < maxturn - 1:
                    yield (z + 1, y + 1, x)
                if mod + 1 >= minturn:
                    yield (2 * maxturn, y, x - 1)
                    yield (3 * maxturn, y, x + 1)
                return
            if div == 2:
                if mod + 1 >= minturn:
                    yield (0 * maxturn, y - 1, x)
                    yield (1 * maxturn, y + 1, x)
                if mod < maxturn - 1:
                    yield (z + 1, y, x - 1)
                return
            if div == 3:
                if mod + 1 >= minturn:
                    yield (0 * maxturn, y - 1, x)
                    yield (1 * maxturn, y + 1, x)
                if mod < maxturn - 1:
                    yield (z + 1, y, x + 1)
                return

        def neighs(z: int, y: int, x: int) -> Iterator[tuple[int, int, int]]:
            for z_, y_, x_ in _neighs(z, y, x):
                if 0 <= x_ < self.lx and 0 <= y_ < self.ly:
                    yield z_, y_, x_

        currents: dict[tuple[int, int, int], int] = {(-1, 0, 0): 0}
        while len(currents) > 0:
            nexts: dict[tuple[int, int, int], int] = {}
            for current_pos, current_total in currents.items():
                for next_pos in neighs(*current_pos):
                    z, y, x = next_pos
                    loss = self.matrix[y, x]
                    next_total = current_total + loss
                    if (visits[next_pos] < 0
                            or next_total < visits[next_pos]):
                        visits[next_pos] = next_total
                        nexts[next_pos] = next_total
            currents = nexts
        loss = -1
        for div in range(4):
            for mod in range(minturn - 1, maxturn):
                z = div * maxturn + mod
                pos = (z, self.ly - 1, self.lx - 1)
                if loss < 0 or 0 < visits[pos] < loss:
                    loss = visits[pos]
        return loss


def part1(lines: aoc.Data) -> int:
    """Solve puzzle part 1: determine the minimum total heat loss from start to
    end, using normal crucibles"""
    city = City.import_lines(lines)
    return city.walk(1, 3)


def part2(lines: aoc.Data) -> int:
    """Solve puzzle part 2: determine the minimum total heat loss from start to
    end, using ultra crucibles"""
    city = City.import_lines(lines)
    return city.walk(4, 10)

Le code :

import dataclasses
import enum
import io
import re

from collections.abc import Iterable, Iterator
from typing import ClassVar, Self

import numpy as np
import numpy.typing as npt

import aoc


Coords = tuple[int, int]
Vector = tuple[int, int]


class Direction(enum.Enum):
    UP = 'U'
    DOWN = 'D'
    LEFT = 'L'
    RIGHT = 'R'

    @property
    def vector(self) -> Vector:
        if self is self.UP:
            return (-1, 0)
        if self is self.DOWN:
            return (1, 0)
        if self is self.LEFT:
            return (0, -1)
        if self is self.RIGHT:
            return (0, 1)
        assert False, "we covered all cases"

    def translate(self, position: Coords) -> Coords:
        y, x = position
        dy, dx = self.vector
        return y + dy, x + dx


@dataclasses.dataclass(frozen=True)
class Instruction:
    direction: Direction
    length: int

    import_pattern1: ClassVar[re.Pattern] = re.compile(
            r'^([UDLR]) (\d+) \(#[0-9A-Fa-f]{6}\)\n?$')
    import_pattern2: ClassVar[re.Pattern] = re.compile(
            r'^[UDLR] \d+ \(#([0-9A-Fa-f]{5})([0-9A-Fa-f])\)\n?$')

    @classmethod
    def import_line1(cls, line: str) -> Self:
        if (m := cls.import_pattern1.match(line)) is not None:
            return cls(Direction(m[1]), int(m[2]))
        raise ValueError("invalid instruction line")

    @classmethod
    def import_line2(cls, line: str) -> Self:
        if (m := cls.import_pattern2.match(line)) is not None:
            length = int(m[1], 16)
            if m[2] == '0':
                direction = Direction.RIGHT
            elif m[2] == '1':
                direction = Direction.DOWN
            elif m[2] == '2':
                direction = Direction.LEFT
            elif m[2] == '3':
                direction = Direction.UP
            else:
                raise ValueError("invalid instruction line")
            return cls(direction, length)
        raise ValueError("invalid instruction line")

    def apply(self, position: Coords) -> Coords:
        y, x = position
        dy, dx = self.direction.vector
        return y + self.length * dy, x + self.length * dx


class Terrain1:
    def __init__(self, instructions: Iterable[Instruction]) -> None:
        position: Coords = (0, 0)
        excavated: set[Coords] = {(0, 0)}
        for instruction in instructions:
            for _ in range(instruction.length):
                position = instruction.direction.translate(position)
                excavated.add(position)
        ymin, ymax = 0, 0
        xmin, xmax = 0, 0
        for (y, x) in excavated:
            ymin = min(ymin, y)
            ymax = max(ymax, y)
            xmin = min(xmin, x)
            xmax = max(xmax, x)
        # Time to write a terrain matrix
        # It needs to span the entire excavated area, plus a margin:
        # * vertically: from ymin - 1 to ymax + 1 included;
        # * horizontally: fron xmin - 1 to xmax + 1 included.
        self.matrix: npt.NDArray[np.bool_] = np.zeros(
                (ymax - ymin + 3, xmax - xmin + 3), dtype=np.bool_)
        self.ly, self.lx = self.matrix.shape
        for (y, x) in excavated:
            y = y - ymin + 1
            x = x - xmin + 1
            self.matrix[y, x] = True

    def dig_pool(self) -> None:
        def neighs(coords: Coords) -> Iterator[Coords]:
            def _neighs(coords: Coords):
                y, x = coords
                yield y, x - 1
                yield y, x + 1
                yield y - 1, x
                yield y + 1, x
            for y, x in _neighs(coords):
                if 0 <= y < self.ly and 0 <= x < self.lx:
                    yield y, x

        outside = np.zeros_like(self.matrix)
        visited = np.zeros_like(self.matrix)
        start = (0, 0)
        outside[start] = True
        visited[start] = True
        currents: set[Coords] = {(0, 0)}
        while len(currents) > 0:
            nexts: set[Coords] = set()
            for position in currents:
                for neigh in neighs(position):
                    if visited[neigh]:
                        continue
                    if not self.matrix[neigh]:
                        outside[neigh] = True
                        nexts.add(neigh)
                    visited[neigh] = True
            currents = nexts
        for position, _ in np.ndenumerate(self.matrix):  # type: ignore
            if not outside[position]:
                self.matrix[position] = True

    def area(self) -> int:
        return np.sum(self.matrix)  # type: ignore

    def __str__(self) -> str:
        s = io.StringIO()
        for line in self.matrix:
            for excavated in line:
                if excavated:
                    s.write('█')
                else:
                    s.write(' ')
            s.write('\n')
        return s.getvalue()


@dataclasses.dataclass(frozen=True)
class HSegment:
    x1: int
    x2: int
    y: int

    def cuts(self, x: int) -> bool:
        return self.x1 <= x <= self.x2

    def __len__(self) -> int:
        return self.x2 - self.x1 + 1


@dataclasses.dataclass(frozen=True)
class VSegment:
    x: int
    y1: int
    y2: int

    def cuts(self, y: int) -> bool:
        return self.y1 <= y <= self.y2

    def __len__(self) -> int:
        return self.y2 - self.y1 + 1


class Terrain2:
    def __init__(self, instructions: Iterable[Instruction]):
        hsegments: set[HSegment] = set()
        vsegments: set[VSegment] = set()
        ys: set[int] = {0, 1}
        xs: set[int] = {0, 1}
        ymin, ymax = 0, 1
        xmin, xmax = 0, 1
        y, x = 0, 0
        for instruction in instructions:
            y_, x_ = instruction.apply((y, x))
            ymin, ymax = min(ymin, y_), max(ymax, y_ + 1)
            xmin, xmax = min(xmin, x_), max(xmax, x_ + 1)
            ys.add(y_)
            ys.add(y_ + 1)
            xs.add(x_)
            xs.add(x_ + 1)
            if instruction.direction is Direction.UP:
                vsegments.add(VSegment(x, y_, y))
            elif instruction.direction is Direction.DOWN:
                vsegments.add(VSegment(x, y, y_))
            elif instruction.direction is Direction.LEFT:
                hsegments.add(HSegment(x_, x, y))
            elif instruction.direction is Direction.RIGHT:
                hsegments.add(HSegment(x, x_, y))
            else:
                assert False, "we covered all cases for instruction direction"
            y, x = y_, x_
        ys.add(ymin - 1)
        ys.add(ymax + 1)
        xs.add(xmin - 1)
        xs.add(xmax + 1)
        self.ys = sorted(ys)
        self.xs = sorted(xs)
        self.matrix: npt.NDArray[np.bool_] = np.zeros(
                (len(ys) - 1, len(xs) - 1), dtype=np.bool_)
        self.lj, self.li = self.matrix.shape
        for hsegment in hsegments:
            j = self.ys.index(hsegment.y)
            for i in range(self.xs.index(hsegment.x1),
                           self.xs.index(hsegment.x2) + 1):
                self.matrix[j, i] = True
        for vsegment in vsegments:
            i = self.xs.index(vsegment.x)
            for j in range(self.ys.index(vsegment.y1),
                           self.ys.index(vsegment.y2) + 1):
                self.matrix[j, i] = True

    def dig_pool(self) -> None:
        def neighs(coords: Coords) -> Iterator[Coords]:
            def _neighs(coords: Coords):
                j, i = coords
                yield j, i - 1
                yield j, i + 1
                yield j - 1, i
                yield j + 1, i
            for j, i in _neighs(coords):
                if 0 <= j < self.lj and 0 <= i < self.li:
                    yield j, i

        outside = np.zeros_like(self.matrix)
        visited = np.zeros_like(self.matrix)
        start = (0, 0)
        outside[start] = True
        visited[start] = True
        currents: set[Coords] = {(0, 0)}
        while len(currents) > 0:
            nexts: set[Coords] = set()
            for position in currents:
                for neigh in neighs(position):
                    if visited[neigh]:
                        continue
                    if not self.matrix[neigh]:
                        outside[neigh] = True
                        nexts.add(neigh)
                    visited[neigh] = True
            currents = nexts
        for position, _ in np.ndenumerate(self.matrix):  # type: ignore
            if not outside[position]:
                self.matrix[position] = True

    def area(self) -> int:
        count = 0
        for j in range(self.lj):
            for i in range(self.li):
                if self.matrix[j, i]:
                    count += ((self.ys[j + 1] - self.ys[j])
                              * (self.xs[i + 1] - self.xs[i]))
        return count

    def __str__(self) -> str:
        s = io.StringIO()
        for line in self.matrix:
            for excavated in line:
                if excavated:
                    s.write('█')
                else:
                    s.write(' ')
            s.write('\n')
        return s.getvalue()


def part1(lines: aoc.Data) -> int:
    """Solve puzzle part 1: determine the sum of stuff"""
    terrain = Terrain1(Instruction.import_line1(line) for line in lines)
    terrain.dig_pool()
    return terrain.area()


def part2(lines: aoc.Data) -> int:
    """Solve puzzle part 2: determine the sum of staff"""
    terrain = Terrain2(Instruction.import_line2(line) for line in lines)
    terrain.dig_pool()
    return terrain.area()

Première partie

Pour la première partie, je fais du remplissage, voici les étapes :

1. J'alloue une matrice suffisante pour contenir tout le tracé – oui, il y a une étape pour déterminer la taille nécessaire, mais c'est sans intérêt à dérailler –, plus une marge d'une unité. En fait, pas une matrice mais trois, à valeurs booléennes : le terrain, une matrice qui indiquera si on est à l'extérieur du tracé, et une matrice qui indiquera si on a déjà visité chaque point.
2. Je trace les tranchées.
3. Je pars du point en haut à gauche, dont je suis certain qu'il est hors du bassin puisqu'il fait partie de la marge sus-mentionnée. De proche en proche, je remplis l'extérieur du bassin dans la seconde de mes matrices. C'est beaucoup plus facile que d'essayer de remplir directement l'intérieur. La troisième matrice sert à cette étape, pour ne pas passer indéfiniment sur les mêmes points.
4. Je remplis l'intérieur du bassin dans la matrice du terrain, la seule que je vais garder.

Trouver l'aire, c'est trivial.

Deuxième partie

Pareil. Comment ça, pareil, alors que les coordonnées sont beaucoup trop grandes pour pouvoir faire ça avec des matrices ? Eh bien, on n'a pas besoin de toutes les coordonnées, voyez-vous. On a seulement besoin de celles où commencent ou finissent des tranchées en fait.

Bref, je me construis une matrice donc les cases ont des dimensions virtuelles carrément variables. Ensuite, on se ramène à l'algorithme précédent, avec un détail de pondération pour le calcul de l'aire.