Ah, c'est bien ça, shapely.
Parce que bon, j'ai salement polioté sur cette partie, et au final j'ai une solution en faisant une hypothèse de travail et 9 minutes de calculs avec PyPy.
Il faut beaucoup trop réfléchir pour modéliser le bidule proprement, savoir ce qui est dedans et dehors, dépatouiller les sous-ensembles etc.
Et mon code aurait foiré s'il y avait eu des « crochets » du genre ça, en considérant le rectangle entre les deux O, la case avec un _ rend le rectangle impossible, mais n'est pas « vue » par mon algo :
######.#....#.#O##.#.##_#.O#...#..#.###..#.######
Bref, c'est moche, je montre pas, mais dans l'idée, je liste toutes les arêtes, puis pour chaque x possible (0 à 100000 en gros) on regarde le y maximal et minimal, et on fait idem pour les les y possible avec les x maximal et minimal.
L'hypothèse ici c'est qu'on voit toutes les arêtes depuis l'extérieur de la surface, nord, sud, est ouest, on a soit une arête dans l'axe et on voit une seule case, soit elle est entièrement visible face à nous.
Là dessus, pour chaque rectangle possible, triés par superficie décroissante, on regarde si les sommets sont « à l'intérieur », c'est à dire si pour le x du sommet, le y est entre le max et le min, et si pour le y du sommet le x est entre le min et le max.
Si c'est le cas, on pousse plus loin, et on teste tous les bords du rectangle (nous avons ici une optimisation d'échelle, permettant d'éliminer très rapidement la majorité des rectangles, et de se concentrer sur ceux qui ont un potentiel !).
Dès qu'on est 100% OK, on a le bon résultat, et ça fonctionne.
C'est brutal, je ne suis pas sûr de pourquoi ça prend tant de temps, je suppose que je pourrais optimiser mon calcul initial des bornes, j'ai utiliser un cache de fonction, puis j'ai forcé le remplissage du cache au début pour voir pourquoi c'était long.
Et la version Python (non PyPy donc) bloque au calcul du bon rectangle.
D'expérience, si la version Python est plus lente que la version PyPy, c'est qu'on a fait de la boue...
Une bonne optimisation serait de simplifier le terrain par tous les x et y existant dans les coordonnées.
Dans l'exemple on a x dans [2, 7, 9, 11] et y dans [1, 3, 5, 7], et en réalité le « terrain » fait 4x4 et non 11x7. Dans le cas réel, on a un terrain de moins de 250x250 (496 lignes et chaque coordonnées y est normalement au moins représentée deux fois), et là c'est plutôt facile de parcourir un peu en force sur une terrain minuscule (60 000 cases contre 10 milliards...).
Mais ça demande de bien réfléchir à ne pas tomber sur des effets de bords.
Et ceci m'a - enfin - amené à une optimisation intermédiaire : je reprend exactement mon algo, mais après avoir testé les sommets des différents rectangles, au lieu de tester les côtés entiers, je ne teste que les points dont les coordonnées sont dans cette fameuse liste réduite de ~250 x et ~250 y.
Je tombe à 3s avec PyPy, ce qui prouve qu'on doit pouvoir optimiser pour aller à une vitesse raisonnable.
Mais...
Mais est-ce que ça répond au problème dans le cas général ? Est-ce que j'ai un biais de chez-moi-ça-marche ? Parce que je peux décrire des situations où ça ne fonctionne pas, typiquement mon exemple plus haut. J'ai quand même une simplification qui n'est absolument pas prévue par l'énoncé du problème.
Bref, shapely c'est officiellement une bonne solution...
[^] # Re: jour 9
Posté par Yth (Mastodon) . En réponse au journal Advent of Code 2025. Évalué à 3.
Ah, c'est bien ça, shapely.
Parce que bon, j'ai salement polioté sur cette partie, et au final j'ai une solution en faisant une hypothèse de travail et 9 minutes de calculs avec PyPy.
Il faut beaucoup trop réfléchir pour modéliser le bidule proprement, savoir ce qui est dedans et dehors, dépatouiller les sous-ensembles etc.
Et mon code aurait foiré s'il y avait eu des « crochets » du genre ça, en considérant le rectangle entre les deux O, la case avec un _ rend le rectangle impossible, mais n'est pas « vue » par mon algo :
Bref, c'est moche, je montre pas, mais dans l'idée, je liste toutes les arêtes, puis pour chaque x possible (0 à 100000 en gros) on regarde le y maximal et minimal, et on fait idem pour les les y possible avec les x maximal et minimal.
L'hypothèse ici c'est qu'on voit toutes les arêtes depuis l'extérieur de la surface, nord, sud, est ouest, on a soit une arête dans l'axe et on voit une seule case, soit elle est entièrement visible face à nous.
Là dessus, pour chaque rectangle possible, triés par superficie décroissante, on regarde si les sommets sont « à l'intérieur », c'est à dire si pour le x du sommet, le y est entre le max et le min, et si pour le y du sommet le x est entre le min et le max.
Si c'est le cas, on pousse plus loin, et on teste tous les bords du rectangle (nous avons ici une optimisation d'échelle, permettant d'éliminer très rapidement la majorité des rectangles, et de se concentrer sur ceux qui ont un potentiel !).
Dès qu'on est 100% OK, on a le bon résultat, et ça fonctionne.
C'est brutal, je ne suis pas sûr de pourquoi ça prend tant de temps, je suppose que je pourrais optimiser mon calcul initial des bornes, j'ai utiliser un cache de fonction, puis j'ai forcé le remplissage du cache au début pour voir pourquoi c'était long.
Et la version Python (non PyPy donc) bloque au calcul du bon rectangle.
D'expérience, si la version Python est plus lente que la version PyPy, c'est qu'on a fait de la boue...
Une bonne optimisation serait de simplifier le terrain par tous les x et y existant dans les coordonnées.
Dans l'exemple on a x dans [2, 7, 9, 11] et y dans [1, 3, 5, 7], et en réalité le « terrain » fait 4x4 et non 11x7. Dans le cas réel, on a un terrain de moins de 250x250 (496 lignes et chaque coordonnées y est normalement au moins représentée deux fois), et là c'est plutôt facile de parcourir un peu en force sur une terrain minuscule (60 000 cases contre 10 milliards...).
Mais ça demande de bien réfléchir à ne pas tomber sur des effets de bords.
Et ceci m'a - enfin - amené à une optimisation intermédiaire : je reprend exactement mon algo, mais après avoir testé les sommets des différents rectangles, au lieu de tester les côtés entiers, je ne teste que les points dont les coordonnées sont dans cette fameuse liste réduite de ~250 x et ~250 y.
Je tombe à 3s avec PyPy, ce qui prouve qu'on doit pouvoir optimiser pour aller à une vitesse raisonnable.
Mais...
Mais est-ce que ça répond au problème dans le cas général ? Est-ce que j'ai un biais de chez-moi-ça-marche ? Parce que je peux décrire des situations où ça ne fonctionne pas, typiquement mon exemple plus haut. J'ai quand même une simplification qui n'est absolument pas prévue par l'énoncé du problème.
Bref, shapely c'est officiellement une bonne solution...