Coverage for Day8 / part2.py: 92%

1#! /usr/bin/env python 

2# -*- coding: utf-8 -*- 

3 

4""" 

5Advent Of Code 2025 

6=================== 

7Day : 8 

8Part : 2 

9 

10Ce script poursuit la logique de la Part 1 mais cette fois : 

11------------------------------------------------------------ 

12On connecte les points dans l’ordre des distances croissantes, 

13comme dans Kruskal, jusqu'à ce que le graphe devienne entièrement 

14connecté (une seule composante). 

15 

16L'arête qui réalise la connexion finale est la plus éloignée 

17dans l'arbre couvrant minimal. 

18 

19Le résultat demandé est : 

20 produit des abscisses (x) des deux points reliés par cette 

21 dernière arête. 

22 

23Concept : 

24---------- 

25- calcul de toutes les distances au carré, 

26- tri des arêtes, 

27- union-find pour fusionner les composantes, 

28- quand il ne reste plus qu’une composante, 

29 on retourne x_i * x_j pour cette arête. 

30 

31La logique est identique à ton implémentation originale, 

32seule la documentation est améliorée. 

33 

34.. codeauthor:: Alexandre Condette <alexandre.condette@wanadoo.fr> 

35""" 

36 

37# %% ======================================================================== 

38# Lecture de l’input 

39def get_input(day: int = 1, example: bool = False) -> list: 

40 """ 

41 Lit le fichier d'entrée pour le jour demandé. 

42 

43 :param day: numéro du jour AoC 

44 :param example: True → example.txt, False → input.txt 

45 :return: liste des lignes sans fin de ligne 

46 """ 

47 filename = 'example.txt' if example else 'input.txt' 

48 with open(f"./Day{day}/{filename}", 'r', encoding='utf-8') as f: 

49 return [line.rstrip('\n') for line in f] 

50 

51# =========================================================================== 

52 

53# =========================================================================== 

54# Structures et fonctions utilitaires 

55class UnionFind: 

56 """ 

57 Structure Union-Find (Disjoint Set Union). 

58 Fonctionne avec : 

59 - compression de chemin, 

60 - union par taille, 

61 - fusion des composantes. 

62 """ 

63 

64 def __init__(self, n: int): 

65 self.parent = list(range(n)) 

66 self.size = [1] * n 

67 

68 def find(self, x: int) -> int: 

69 """Retourne le représentant de la composante contenant x.""" 

70 while self.parent[x] != x: 

71 self.parent[x] = self.parent[self.parent[x]] 

72 x = self.parent[x] 

73 return x 

74 

75 def union(self, a: int, b: int) -> bool: 

76 """ 

77 Fusionne les composantes de a et b. 

78 Retourne True si une fusion a eu lieu. 

79 """ 

80 ra = self.find(a) 

81 rb = self.find(b) 

82 

83 if ra == rb: 

84 return False 

85 

86 if self.size[ra] < self.size[rb]: 

87 ra, rb = rb, ra 

88 

89 self.parent[rb] = ra 

90 self.size[ra] += self.size[rb] 

91 return True 

92 

93# --------------------------------------------------------------------------- 

94def parse_coords(lines: list) -> list: 

95 """ 

96 Convertit des lignes "x,y,z" en tuples (x, y, z). 

97 

98 :param lines: lignes de texte 

99 :return: liste de tuples 

100 """ 

101 pts = [] 

102 for line in lines: 

103 s = line.strip() 

104 if not s: 104 ↛ 105line 104 didn't jump to line 105 because the condition on line 104 was never true

105 continue 

106 x, y, z = s.split(",") 

107 pts.append((int(x), int(y), int(z))) 

108 return pts 

109 

110 

111# =========================================================================== 

112# Résolution 

113def solve(lines: list) -> int: 

114 """ 

115 Partie 2 : connexion complète du graphe. 

116 

117 On : 

118 - génère toutes les arêtes avec distance, 

119 - trie les arêtes, 

120 - applique Kruskal, 

121 - quand il reste une seule composante, 

122 on retourne le produit des abscisses des deux points 

123 connectés par la dernière arête. 

124 

125 :param lines: input brut 

126 :return: produit x_i * x_j de la dernière connexion 

127 """ 

128 

129 pts = parse_coords(lines) 

130 n = len(pts) 

131 

132 if n <= 1: 132 ↛ 133line 132 didn't jump to line 133 because the condition on line 132 was never true

133 return 0 

134 

135 # Construction de toutes les arêtes (dist², i, j) 

136 edges = [] 

137 for i in range(n): 

138 xi, yi, zi = pts[i] 

139 for j in range(i + 1, n): 

140 xj, yj, zj = pts[j] 

141 dx = xi - xj 

142 dy = yi - yj 

143 dz = zi - zj 

144 dist2 = dx * dx + dy * dy + dz * dz 

145 edges.append((dist2, i, j)) 

146 

147 # tri des arêtes par distance croissante 

148 edges.sort(key=lambda e: e[0]) 

149 

150 uf = UnionFind(n) 

151 components = n 

152 

153 # Kruskal : on fusionne jusqu'à une seule composante 

154 for dist2, i, j in edges: 154 ↛ 164line 154 didn't jump to line 164 because the loop on line 154 didn't complete

155 if uf.union(i, j): 

156 components -= 1 

157 

158 # dernière arête → graphe connecté 

159 if components == 1: 

160 x1 = pts[i][0] 

161 x2 = pts[j][0] 

162 return x1 * x2 

163 

164 return 0 

165 

166# =========================================================================== 

167if __name__ == "__main__": 

168 RESULT = solve(get_input(8, False)) 

169 

170 print("\n" + "═" * 60) 

171 print(" 🔐 Advent of Code 2025 — Day 8 | Part 2".center(60)) 

172 print("═" * 60) 

173 print(f"Résultat : \033[96m{RESULT}\033[0m") 

174 print("═" * 60 + "\n")