Coverage for Day8 / part1.py: 78%

1#! /usr/bin/env python 

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

3 

4""" 

5Advent Of Code 2025 

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

7Day : 8 

8Part : 1 

9 

10Ce script identifie les trois plus grandes composantes connectées dans un nuage 

11de points 3D en utilisant seulement les 1000 arêtes les plus proches. 

12 

13Concept : 

14---------- 

15- Chaque point est un tuple (x, y, z). 

16- On calcule toutes les distances au carré entre les points. 

17- On garde uniquement les K plus petites distances (1000 par défaut). 

18- Chaque paire sélectionnée relie deux points dans une structure Union-Find. 

19- Une fois les unions réalisées, on récupère les tailles des composantes. 

20- Le résultat est le produit des tailles des trois plus grandes composantes. 

21 

22L’objectif correspond exactement à l'énoncé AoC 2025 Day 8 Part 1. 

23 

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

25""" 

26 

27# %% ======================================================================== 

28# Import 

29import heapq 

30 

31# =========================================================================== 

32 

33# %% ======================================================================== 

34# Lecture de l’input 

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

36 """ 

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

38 

39 :param day: numéro du jour AoC 

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

41 :return: liste des lignes sans fin de ligne 

42 """ 

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

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

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

46 

47 

48# =========================================================================== 

49 

50# %% ======================================================================== 

51# Structures et fonctions utilitaires 

52class UnionFind: 

53 """ 

54 Structure Union-Find (Disjoint Set Union) avec : 

55 - compression de chemin, 

56 - union par taille, 

57 - extraction des tailles de composantes. 

58 """ 

59 

60 def __init__(self, n: int): 

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

62 self.size = [1] * n 

63 

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

65 """Retourne le représentant du set contenant x.""" 

66 if self.parent[x] != x: 

67 self.parent[x] = self.find(self.parent[x]) 

68 return self.parent[x] 

69 

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

71 """ 

72 Fusionne les ensembles contenant a et b. 

73 Retourne True si une fusion a réellement eu lieu. 

74 """ 

75 ra = self.find(a) 

76 rb = self.find(b) 

77 

78 if ra == rb: 

79 return False 

80 

81 # union par taille 

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

83 ra, rb = rb, ra 

84 

85 self.parent[rb] = ra 

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

87 

88 return True 

89 

90 def component_sizes(self): 

91 """Retourne les tailles des composantes, triées décroissantes.""" 

92 roots = {} 

93 for i in range(len(self.parent)): 

94 r = self.find(i) 

95 roots[r] = roots.get(r, 0) + 1 

96 return sorted(roots.values(), reverse=True) 

97 

98# --------------------------------------------------------------------------- 

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

100 """ 

101 Convertit une liste de lignes au format "x,y,z" en tuples. 

102 

103 Accepté : 

104 - lignes chaînes, 

105 - tuples déjà formés. 

106 

107 :return: liste de tuples (x, y, z) 

108 """ 

109 pts = [] 

110 

111 for line in lines: 

112 if isinstance(line, tuple): 

113 pts.append(line) 

114 continue 

115 

116 s = line.strip() 

117 if not s: 

118 continue 

119 

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

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

122 

123 return pts 

124 

125# =========================================================================== 

126# Résolution 

127def solve(lines, K=1000): 

128 """ 

129 Résout la partie 1 : 

130 - calcule toutes les distances, 

131 - garde les K plus petites, 

132 - les fusionne dans un Union-Find, 

133 - produit les tailles des 3 plus grandes composantes. 

134 

135 :param lines: lignes de points 

136 :param K: nombre de paires à conserver 

137 :return: produit des trois plus grandes composantes 

138 """ 

139 pts = [tuple(map(int, l.split(","))) for l in lines if l.strip()] 

140 n = len(pts) 

141 

142 # calcul brute des distances (comme dans ton code) 

143 pairs = [] 

144 for i in range(n): 

145 xi, yi, zi = pts[i] 

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

147 xj, yj, zj = pts[j] 

148 d2 = (xi - xj)**2 + (yi - yj)**2 + (zi - zj)**2 

149 pairs.append((d2, i, j)) 

150 

151 # garde les K plus proches 

152 pairs = heapq.nsmallest(K, pairs, key=lambda x: x[0]) 

153 

154 uf = UnionFind(n) 

155 

156 for _, i, j in pairs: 

157 uf.union(i, j) 

158 

159 sizes = uf.component_sizes() 

160 return sizes[0] * sizes[1] * sizes[2] 

161 

162# =========================================================================== 

163# %% 

164if __name__ == "__main__": 

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

166 

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

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

169 print("═" * 60) 

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

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