Coverage for Day10 / part1.py: 75%

1#! /usr/bin/env python 

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

3 

4""" 

5Advent Of Code 2025 

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

7Day : 10 

8Part : 1 

9 

10Résolution du problème sous GF(2) : identification du nombre minimal 

11d'appuis de boutons permettant de reproduire un motif binaire ciblé. 

12 

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

14""" 

15 

16# %% ======================================================================== 

17# LECTURE DE L’INPUT 

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

19 """ 

20 Lit le fichier d'entrée associé au jour demandé. 

21 

22 :param day: Numéro du jour AoC. 

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

24 :return: Liste de chaînes, chaque ligne du fichier sans retour à la ligne. 

25 """ 

26 file = "example.txt" if example else "input.txt" 

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

28 return [line.rstrip("\n") for line in f] 

29 

30# =========================================================================== 

31 

32# %% ======================================================================== 

33# Fonctions utiles 

34def gauss(A: list, b: list): 

35 """ 

36 Réduction de Gauss en arithmétique mod 2. 

37 

38 :param A: Matrice binaire n×m (liste de listes). 

39 :param b: Vecteur binaire de taille n. 

40 :return: 

41 - is_ok : bool — une solution existe ? 

42 - x0 : solution particulière (liste binaire) 

43 - null_basis : base du noyau (liste de vecteurs binaires) 

44 """ 

45 n = len(A) 

46 m = len(A[0]) if n > 0 else 0 

47 

48 M = [row[:] + [rhs] for row, rhs in zip(A, b)] 

49 row = 0 

50 pivots = [] 

51 

52 # Pivotisation sur chaque colonne 

53 for col in range(m): 

54 sel = None 

55 for r in range(row, n): 

56 if M[r][col] == 1: 

57 sel = r 

58 break 

59 

60 if sel is None: 

61 continue 

62 

63 # Échange de lignes 

64 M[row], M[sel] = M[sel], M[row] 

65 pivots.append((row, col)) 

66 

67 # Élimination 

68 for r in range(n): 

69 if r != row and M[r][col] == 1: 

70 for c in range(col, m + 1): 

71 M[r][c] ^= M[row][c] 

72 

73 row += 1 

74 if row == n: 

75 break 

76 

77 # Détection d'incohérence 

78 for r in range(row, n): 

79 if all(M[r][c] == 0 for c in range(m)) and M[r][m] == 1: 79 ↛ 80line 79 didn't jump to line 80 because the condition on line 79 was never true

80 return (False, None, None) 

81 

82 # Solution particulière 

83 x0 = [0] * m 

84 for r, c in reversed(pivots): 

85 acc = M[r][m] 

86 for cc in range(c + 1, m): 

87 acc ^= (M[r][cc] & x0[cc]) 

88 x0[c] = acc 

89 

90 # Base du noyau 

91 pivot_cols = {c for _, c in pivots} 

92 free_cols = [c for c in range(m) if c not in pivot_cols] 

93 null_basis = [] 

94 

95 for f in free_cols: 

96 v = [0] * m 

97 v[f] = 1 

98 for r, c in reversed(pivots): 

99 s = 0 

100 for cc in range(c + 1, m): 

101 s ^= (M[r][cc] & v[cc]) 

102 v[c] = s 

103 null_basis.append(v) 

104 

105 return (True, x0, null_basis) 

106 

107# --------------------------------------------------------------------------- 

108def weight(vec: list) -> int: 

109 """ 

110 Calcule le poids de Hamming d’un vecteur binaire. 

111 

112 Le poids correspond au nombre total de bits égaux à 1.  

113 Utilisé pour mesurer le nombre d'appuis (ou la "taille") d'une solution 

114 dans l’espace GF(2). 

115 

116 :param vec: Liste d'entiers 0/1. 

117 :return: Nombre d’éléments valant 1. 

118 """ 

119 return sum(vec) 

120 

121# --------------------------------------------------------------------------- 

122def add_mod2(u: list, v: list) -> list: 

123 """ 

124 Effectue une addition binaire terme à terme (XOR). 

125 

126 Cette opération correspond à l'addition dans le corps GF(2) : 

127 0⊕0=0, 1⊕0=1, 0⊕1=1, 1⊕1=0.  

128 Employé pour combiner une solution particulière et des vecteurs du noyau. 

129 

130 :param u: Premier vecteur binaire (liste 0/1). 

131 :param v: Second vecteur binaire (liste 0/1), même taille que u. 

132 :return: Nouveau vecteur résultant de u ⊕ v. 

133 """ 

134 return [(a ^ b) for a, b in zip(u, v)] 

135 

136# --------------------------------------------------------------------------- 

137def min_presses(target_str: str, buttons: list) -> int: 

138 """ 

139 Calcule le nombre minimal d'appuis nécessaires pour reproduire 

140 un pattern binaire donné. 

141 

142 :param target_str: Motif cible ('.' ou '#'). 

143 :param buttons: Liste de tuples ; chaque bouton liste les positions togglées. 

144 :return: Nombre minimal d'appuis ou None si impossible. 

145 """ 

146 n = len(target_str) 

147 b = [1 if c == "#" else 0 for c in target_str] 

148 m = len(buttons) 

149 

150 # Construction de A (n × m) 

151 A = [[0] * m for _ in range(n)] 

152 for j, btn in enumerate(buttons): 

153 for idx in btn: 

154 A[idx][j] = 1 

155 

156 ok, x0, null_basis = gauss(A, b) 

157 if not ok: 157 ↛ 158line 157 didn't jump to line 158 because the condition on line 157 was never true

158 return None 

159 

160 k = len(null_basis) 

161 best = None 

162 

163 # Cas dimension faible → exploration exhaustive 

164 if k <= 24: 164 ↛ 175line 164 didn't jump to line 175 because the condition on line 164 was always true

165 for mask in range(1 << k): 

166 x = x0[:] 

167 for i in range(k): 

168 if (mask >> i) & 1: 

169 x = add_mod2(x, null_basis[i]) 

170 w = weight(x) 

171 if best is None or w < best: 

172 best = w 

173 

174 # Bruteforce direct si peu de boutons 

175 elif m <= 24: 

176 for mask in range(1 << m): 

177 state = [0] * n 

178 presses = 0 

179 for j in range(m): 

180 if (mask >> j) & 1: 

181 presses += 1 

182 for idx in buttons[j]: 

183 state[idx] ^= 1 

184 if state == b and (best is None or presses < best): 

185 best = presses 

186 

187 # Heuristique sinon 

188 else: 

189 x = x0[:] 

190 improved = True 

191 while improved: 

192 improved = False 

193 for v in null_basis: 

194 cand = add_mod2(x, v) 

195 if weight(cand) < weight(x): 

196 x = cand 

197 improved = True 

198 best = weight(x) 

199 

200 return best 

201 

202# =========================================================================== 

203 

204# %% ======================================================================== 

205# Résolution 

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

207 """ 

208 Parse chaque ligne du fichier d'entrée puis applique la résolution GF(2). 

209 

210 Format attendu : 

211 [.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) 

212 

213 :param lines: Liste de lignes du fichier d'entrée. 

214 :return: Somme des minima pour toutes les lignes. 

215 """ 

216 total = 0 

217 

218 for line in lines: 

219 if not line.strip(): 219 ↛ 220line 219 didn't jump to line 220 because the condition on line 219 was never true

220 continue 

221 

222 diag = line.split("]")[0].split("[")[1] 

223 

224 parts = line.split("]")[1].strip().split(")") 

225 buttons = [] 

226 for p in parts: 

227 if "(" not in p: 

228 continue 

229 inside = p.split("(")[1] 

230 if inside.strip() == "": 230 ↛ 231line 230 didn't jump to line 231 because the condition on line 230 was never true

231 buttons.append(()) 

232 else: 

233 buttons.append(tuple(int(x) for x in inside.split(",") if x != "")) 

234 

235 res = min_presses(diag, buttons) 

236 total += res 

237 

238 return total 

239 

240# =========================================================================== 

241 

242# %% ======================================================================== 

243# MAIN 

244if __name__ == "__main__": 

245 RESULT = solve(get_input(10, False)) 

246 

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

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

249 print("═" * 60) 

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

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

252 

253# ===========================================================================