Coverage for Day9 / part2.py: 100%
32 statements
« prev ^ index » next coverage.py v7.13.0, created at 2025-12-12 09:47 +0000
1#! /usr/bin/env python
2# -*- coding: utf-8 -*-
4"""
5Advent of Code 2025
6===================
7Day : 9
8Part : 2
10Ce script calcule la plus grande aire d’un rectangle axis-aligné totalement
11contenu dans une boucle décrite par une liste de points (x,y).
13L’algorithme utilisé est une version optimisée (O(N²)) :
14- on parcourt toutes les paires de points,
15- on calcule le rectangle correspondant,
16- on vérifie rapidement s’il est entièrement contenu dans la boucle,
17- on garde le maximum.
19La vérification s’appuie sur les segments de la boucle (edges), ce qui évite
20les bibliothèques lourdes comme shapely tout en restant efficace.
22.. codeauthor:: Alexandre Condette <alexandre.condette@wanadoo.fr>
23"""
25# %% ========================================================================
26# Import
27from itertools import combinations
29# ===========================================================================
31# %% ========================================================================
32# Lecture de l’input
33def get_input(day: int = 1, example: bool = False) -> list:
34 """
35 Lit le fichier d'entrée pour le jour demandé.
37 :param day: numéro du jour AoC
38 :param example: True → example.txt, False → input.txt
39 :return: liste de lignes sans fin de ligne
40 """
41 file = 'example.txt' if example else 'input.txt'
42 with open(f"./Day{day}/{file}", 'r', encoding='utf-8') as f:
43 return f.read().strip()
44# ===========================================================================
46# %% ========================================================================
47# Fonctions utilitaires
48def calculate_area(p1: tuple[int, int], p2: tuple[int, int]) -> int:
49 """
50 Calcule l’aire d’un rectangle défini par deux coins.
52 Les deux coins sont inclus → +1 sur chaque dimension.
54 :param p1: premier point (x, y)
55 :param p2: second point (x, y)
56 :return: aire du rectangle
57 :rtype: int
58 """
59 return (abs(p1[0] - p2[0]) + 1) * (abs(p1[1] - p2[1]) + 1)
61# ---------------------------------------------------------------------------
62def is_fully_contained(
63 edges: list[tuple[int, int, int, int]],
64 min_x: int,
65 min_y: int,
66 max_x: int,
67 max_y: int,
68) -> bool:
69 """
70 Vérifie si un rectangle est entièrement contenu dans la boucle.
72 On teste si le rectangle coupe un des segments :
73 - si oui → il n’est pas contenu,
74 - sinon → il est contenu.
76 :param edges: segments de la boucle (min_x, min_y, max_x, max_y)
77 :param min_x: borne gauche du rectangle
78 :param min_y: borne basse
79 :param max_x: borne droite
80 :param max_y: borne haute
81 :return: True si contenu, False sinon
82 :rtype: bool
83 """
84 for e_min_x, e_min_y, e_max_x, e_max_y in edges:
85 # intersection stricte avec un segment → rectangle "sort"
86 if min_x < e_max_x and max_x > e_min_x and min_y < e_max_y and max_y > e_min_y:
87 return False
89 return True
91# ===========================================================================
93# %% ========================================================================
94# Résolution — Partie 2 optimisée
95def solve(data: str) -> int:
96 """
97 Calcule la plus grande aire contenue dans la boucle.
99 Étapes :
100 1. Parser les points,
101 2. Construire les segments,
102 3. Tester toutes les paires,
103 4. Vérifier la containment,
104 5. Garder le maximum.
106 :param data: texte brut des points "x,y"
107 :return: aire maximale trouvée
108 :rtype: int
109 """
110 # parse des points
111 tiles = [
112 (int(x), int(y))
113 for line in data.splitlines()
114 for (x, y) in [line.split(",")]
115 ]
117 n = len(tiles)
119 # construction des segments (edges)
120 edges = []
121 for i in range(n - 1):
122 p1, p2 = tiles[i], tiles[i + 1]
123 edges.append(
124 (min(p1[0], p2[0]), min(p1[1], p2[1]), max(p1[0], p2[0]), max(p1[1], p2[1]))
125 )
127 # segment final (boucle)
128 p_last = tiles[-1]
129 p_first = tiles[0]
130 edges.append(
131 (
132 min(p_last[0], p_first[0]),
133 min(p_last[1], p_first[1]),
134 max(p_last[0], p_first[0]),
135 max(p_last[1], p_first[1]),
136 )
137 )
139 best = 0
141 # test toutes les paires
142 for p1, p2 in combinations(tiles, 2):
144 area = calculate_area(p1, p2)
146 # prune → inutile de tester les petites aires
147 if area <= best:
148 continue
150 min_x, max_x = sorted((p1[0], p2[0]))
151 min_y, max_y = sorted((p1[1], p2[1]))
153 # containment
154 if is_fully_contained(edges, min_x, min_y, max_x, max_y):
155 best = area
157 return best
159# ======================================================================
161# %% ========================================================================
162# Programme principal
163if __name__ == "__main__":
164 INPUT = get_input(9, False)
165 RESULT = solve(INPUT)
167 print("\n" + "═" * 60)
168 print(" 🔐 Advent of Code 2025 — Day 9 | Part 2".center(60))
169 print("═" * 60)
170 print(f"Résultat : \033[96m{RESULT}\033[0m")
171 print("═" * 60 + "\n")
173# ===========================================================================