Jour 9 - Polygone inscrit

J’ai du sortir le papier et le crayon, pour celui-ci, et il m’a fallut du temps pour trouver une stratégie qui fonctionne, mais ça y est.

La première partie est très facile. Dès que j’ai vu l’énoncé ce matin, j’ai fait une solution en quelques minutes avant de partir au boulot pour voir quel serait le twist de la seconde et avoir le temps d’y réfléchir. Et le temps de réflexion fut bien nécessaire!

Et on cherche le plus grand rectangle que l’on peut former à partir de deux de ces points. Mis sur une grille, les points ci-dessus s’arrangent comme ceci:

Où, par exemple, le # en haut à droite correspond à la coordonnée 11, 1. Il y a plusieurs options dans l’exemple pour le plus grand rectangle, mais on peut en former un dont l’aire est de 50 avec les points 2, 5 et 11, 1:

Première partie: l’aire d’un rectangle

L’aire d’un rectangle défini par ses deux coins opposés est facile à calculer: il faut prendre les différences selon les deux axes, et les multiplier. On doit juste ici penser à rajouter 1 dans chaque dimension: si les deux coins sont sur la même ligne, on aura tout de même une hauteur de 1 et pas 0.

Commençons par transformer notre input en une liste de coordonnées. Je vais de nouveau utiliser un indice de typage pour la coordonnée, même si ce n’est pas nécessaire:

type Coord = list[int]

def prepare_data(data: str) -> list[Coord]:
    rows = data.split('\n')
    points = [[int(i) for i in r.split(',')] for r in rows]
    return points

Rien de particulier ici, on sépare en ligne, puis selon les ,. Pour calculer l’aire, rien de bien compliqué non plus. On peut utiliser abs pour prendre la valeur absolue quand on fait la différence entre les coordonnées, pour être sûrs que notre aire reste bien positive.

def area(p1: Coord, p2: Coord) -> int:
    return (abs(p1[0]-p2[0])+1)*(abs(p1[1]-p2[1])+1)

Pour trouver l’aire maximale, on doit tester les différentes combinaisons, ce qu’on va une nouvelle fois faire grâce à notre grand ami itertools.combinations:

def find_largest(data: list[Coord]) -> int:
    return max(area(p1, p2) for p1, p2 in itertools.combinations(data, 2))

Pour toutes les combinaisons de points deux à deux, on calcule l’aire, et on retourne le maximum. On met tout ça ensemble, et ça tourne assez rapidement, même avec les 496 points de l’input réel:

def main():
    data = load_input(9, '', prepare_data)
    print(f"Part 1: {find_largest(data)}")

Deuxième partie: une petite contrainte

Petite contrainte additionnelle: on nous indique que les points de notre input sont connectés séquentiellement, et se connectent à la fin pour former un polygone.

On doit maintenant trouver le plus grand rectangle… qui soit entièrement contenu à l’intérieur du polygone. Dans l’exemple:

J’ai mis du temps. J’ai hésité à passer via une librairie comme Shapely, qui permettrait probablement de faire ce qu’il faut, mais j’avais envie de rester dans la librairie standard. La solution “brute force” serait:

Mais faire ça n’est, déjà, pas trivial. Il faut soit d’abord lister – et détecter – quelque part tous les points intérieurs, soit trouver un prédicat permettant de vérifier si un point est à l’intérieur d’un polygone si l’on connaît tous ses sommets! Et même si on trouve comment faire, il faudra pour chaque paire de point faire beaucoup d’opérations, et l’explosion de complexité va probablement nous amener à un programme qui ne tourne pas du tout en un temps raisonnable. En général, je considère que si ça met plus que quelques secondes sur une machine “normale”, c’est qu’il y a un problème.

J’en suis arrivé à la conclusion que j’avais besoin de deux choses pour limiter les recherches:

La première chose est assez simple: si je trie tous mes candidats par leur aire, je peux les parcourir ensuite en ordre descendant: dès que je trouve un candidat valide, j’ai terminé, pas besoin de regarder les autres. On commence donc comme avant avec itertools.combinations, mais maintenant on utilise sorted pour trier la liste comme il faut. La clé de tri sera un appel à area.

def find_largest_valid(data: list[Coord]) -> int:
    all_candidates = list(itertools.combinations(data, 2))
    all_candidates = sorted(all_candidates, key=lambda x: area(*x), reverse=True)
    # ...

area(*x) va être unpacked (dépaquetté?) en area(x[0], x[1]), les x étant les éléments de all_candidates, qui sont de type Coord, et les coordonnées contiennent deux entiers!

Pour le polygone, j’ai fini par me rendre compte d’une chose utile: étant donné que deux des coins du rectangle sont, nécessairement, dans le polygone, il n’en sort que si un de ses côtés traverse un des côtés du polygone. Si je reprends l’exemple initial et que je me pose la question “pourquoi le plus grand rectangle n’est pas valide?”, on peut voir que deux de ses côtés traversent des côtés du polygone:

Il me faut donc maintenant: lister les côtés du polygone, et trouver la règle qui détermine si un côté du rectangle traverse un côté du polygone. Idéalement, ce test doit prendre le moins de temps possible. Je me suis dit pour ça que ce serait pratique de tester directement si les deux sont parallèles, auquel cas ils ne peuvent pas se croiser. J’ai donc finalement opté pour une représentation un peu particulière d’une ligne, qui stocke un booléen indiquant si la ligne est verticale ou horizontale, un entier pour la coordonnée dans la dimension “constante”, et un tuple d’entier pour la dimension variable. En faisant attention à bien toujours ordonner cet intervalle avec la valeur minimale d’abord (j’avais oublié au départ, et j’ai mis pas mal de temps à trouver pourquoi je ne trouvais pas les bons croisements!)

class Line:
    def __init__(self, p0: Coord, p1: Coord):
        if p0[0] == p1[0]:
            self.vertical = True
            self.interval: tuple[int, int] = min(p0[1], p1[1]), max(p0[1], p1[1])
            self.constant = p0[0]
        else:
            self.vertical = False
            self.interval: tuple[int, int] = min(p0[0], p1[0]), max(p0[0], p1[0])
            self.constant = p0[1]
    # ...

Ensuite: quand est-ce qu’un côté du rectangle “croise” un côté du polygone? Si les deux ont la même orientation, on sait qu’ils ne se croisent pas. Sinon, il faut regarder si la partie constante de l’un tombe bien à l’intérieur de la partie variable de l’autre, et vice-versa. J’ai eu besoin de me faire quelques exemples sur papier pour bien visionner les différents cas de figure, parce que le problème en plus n’est pas symétrique. Si je marque XOOX le côté du rectangle que je teste et #--# le côté du polygone, et que je regarde les cas suivants:

Dans A, c’est le cas facile: les deux “dépassent” des deux côtés, on a un croisement. Dans B, si le sommet du haut était dans le rectangle, le sommet du bas y est toujours car je n’ai pas dépassé de la ligne, pas de croisement. Dans C, idem, pas de croisement. Dans D, par contre, qui semble être juste un “transposé” de B, je suis bien sorti du polygone, car vu que chaque sommet marque un “coin”, le polygone doit soit continuer vers le haut (et le sommet du bas est en-dehors), soit vers le bas (et le sommet du haut est dehors).

Donc, si on teste depuis le côté du rectangle si on croise un côté du polygone, on doit vérifier si la partie constante du rectangle (self) est dans l’intervalle inclus (<=) du polygone (cas D: je suis égal à la borne inférieure) et si la partie constante du polygone (other) est dans l’intervalle exclus (<) du polygone (pour que le cas B donne bien “pas de croisement”). On a:

class Line:
    # ...
    def cross(self, other: Line) -> bool:
        if self.vertical == other.vertical:
            return False
        return (other.interval[0] <= self.constant <= other.interval[1]) and \
               (self.interval[0] < other.constant < self.interval[1])

Pour tester tout ça, maintenant, il faut qu’on récupère tous les côtés du polygone. Comme les points sont ordonnés dans l’input, on peut utiliser une autre belle fonction itertools: pairwise, qui permet de passer dans les éléments d’un itérable deux à deux. Il ne faut pas oublier de “refermer” le polygone en rajoutant le premier point à la fin.

def find_largest_valid(data: list[Coord]) -> int:
    # ...
    lines = list(Line(*p) for p in itertools.pairwise(data + [data[0]]))
    # ...

p dans l’itération ici sera un tuple p0, p1 avec deux points successifs dans data, et on peut les utiliser pour construire les lignes. On doit encore récupérer les côtés du rectangle sous forme d’une liste de Line:

def get_sides(p0: Coord, p1: Coord) -> list[Line]
    corners = [[min(p0[0], p1[0]), min(p0[1], p1[1])],
               [min(p0[0], p1[0]), max(p0[1], p1[1])],
               [max(p0[0], p1[0]), max(p0[1], p1[1])],
               [max(p0[0], p1[0]), min(p0[1], p1[1])],
               [min(p0[0], p1[0]), min(p0[1], p1[1])]]
    return [Line(*p) for p in itertools.pairwise(corners)]

Il nous reste à définir la fonction déterminant si un candidat est valide. Si un des côtés traverse une ligne du polygone, alors le candidat est invalide. Si tous les côtés passent le test, alors il est valide.

def is_valid(candidate: tuple[Coord, Coord], lines: list[Line]):
    sides = get_sides(*candidate)
    if any(side.cross(line) 
            for side in sides 
            for line in lines):
        return False
    return True

J’utilise la notation un peu barbare any(predicate(x) for a in b for x in a), qui est un raccourci pour:

res = False
for a in b:
    for x in a:
        if predicate(x): 
            return True

def find_largest_valid(data: list[Coord]) -> int:
    # ...    
    for candidate in all_candidates:
        if is_valid(candidate, lines):
            return area(*candidate)

    raise ValueError(f"Couldn't find acceptable candidate.")

def main():
    # ...
    print(f"Part 2: {find_largest_valid(data)}")

Avec une petite visualisation Matplotlib du fameux polygone et du rectangle qu’on a trouvé:

On notera la petite fourberie qui assure, avec la longue indentation au milieu, que l’on doive passer sur un grand nombre de candidats avant de trouver le bon. Bien joué Eric.

Addendum

En lisant des discussions par la suite, je me suis rendu compte que j’avais loupé un cas de figure qui, heureusement pour moi, n’affecte pas mon résultat. Si on reprend l’exemple, ce rectangle-ci:

Est considéré comme “valide” par mon code, car il ne traverse aucun bord. Il est entièrement à l’extérieur. Je me suis laissé avoir par le fait que “les deux coins sont nécessairement à l’intérieur du polygone”. Oui et non: selon le critère qu’il faut “traverser” entièrement le bord pour passer de l’intérieur à l’extérieur, les points sur le bord sont à la fois interne et externe. Donc ma solution n’est pas générale. Zut.

N’ayant plus très envie de me remettre à réfléchir au problème, j’ai utilisé ce formidable outil qu’est “internet” pour chercher comment on teste si un point se trouve à l’intérieur d’un polygone, et je suis tombé sur cette page Wikipédia décrivant le Point in Polygon problem. Le “ray casting algorithm” correspond assez bien à ce que je cherche, et l’idée est assez proche de ce que je fais déjà pour vérifier la validité d’un rectangle: si je fais partir un rayon dans une direction arbitraire depuis mon point, et qu’il traverse un nombre pair de bords (0 inclus), alors je suis à l’extérieur. Sinon, je suis à l’intérieur.

Un peu la flemme de revenir dessus dans le code pour l’instant, je corrigerai peut-être plus tard.