Coverage for Day10 / part2.py: 85%

1#! /usr/bin/env python 

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

3 

4""" 

5Advent Of Code 2025 

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

7Day : 10 

8Part : 2 

9 

10Résolution ILP (Integer Linear Programming) full silencieuse 

11pour déterminer le nombre minimal d'appuis nécessaires afin 

12de configurer les compteurs de tension (« joltage »). 

13 

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

15""" 

16 

17# %% ======================================================================== 

18# Import 

19import os 

20import sys 

21from contextlib import contextmanager 

22from typing import List, Tuple 

23 

24from pulp import ( 

25 LpProblem, LpVariable, lpSum, LpMinimize, LpInteger, 

26 LpStatusOptimal, PULP_CBC_CMD 

27) 

28 

29# =========================================================================== 

30 

31# %% ======================================================================== 

32# Lecture de l’input 

33def get_input(day: int = 1, example: bool = False) -> List[str]: 

34 """ 

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

36 

37 :param day: Numéro du jour AoC 

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

39 :return: Liste des lignes sans retour chariot 

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 [line.rstrip('\n') for line in f] 

44 

45# =========================================================================== 

46 

47# %% ======================================================================== 

48# Outils 

49@contextmanager 

50def suppress_output(): 

51 """ 

52 Contexte supprimant TOUTE sortie stdout/stderr durant son exécution. 

53 

54 Utile pour neutraliser complètement les sorties verboses de CBC 

55 ou GLPK, même celles envoyées directement au terminal. 

56 """ 

57 with open(os.devnull, 'w') as devnull: 

58 old_stdout, old_stderr = sys.stdout, sys.stderr 

59 sys.stdout, sys.stderr = devnull, devnull 

60 try: 

61 yield 

62 finally: 

63 sys.stdout, sys.stderr = old_stdout, old_stderr 

64 

65 

66# --------------------------------------------------------------------------- 

67def min_presses_joltage(target_list: List[int], 

68 buttons: List[Tuple[int, ...]]) -> int: 

69 """ 

70 Calcule exactement le nombre minimal d'appuis pour atteindre les 

71 compteurs de tension souhaités. 

72 

73 Chaque bouton incrémente certains compteurs, et les variables de 

74 décision sont le nombre entier d'appuis par bouton. 

75 

76 Modélisation ILP : 

77 - Variables : x_i ≥ 0 entiers (nb d'appuis du bouton i) 

78 - Contraintes : somme(x_i pour i affectant k) = target[k] 

79 - Objectif : min(sum(x_i)) 

80 

81 L'utilisation du solveur CBC est forcée et toute sortie est 

82 totalement supprimée. 

83 

84 :param target_list: Liste des valeurs finales souhaitées par compteur 

85 :param buttons: Liste de boutons, chacun étant un tuple d'indices 

86 de compteurs à incrémenter. 

87 :return: Nombre minimal d'appuis (int) 

88 """ 

89 b = target_list 

90 n = len(b) 

91 m = len(buttons) 

92 

93 if n == 0: 93 ↛ 94line 93 didn't jump to line 94 because the condition on line 93 was never true

94 return 0 

95 

96 # Modèle 

97 prob = LpProblem("aoc_day10_part2", LpMinimize) 

98 

99 # Variables : nombre d'appuis par bouton 

100 x = [LpVariable(f"x{i}", lowBound=0, cat=LpInteger) for i in range(m)] 

101 

102 # Objectif : minimiser la somme des appuis 

103 prob += lpSum(x) 

104 

105 # Contraintes : chaque compteur doit atteindre sa cible 

106 for k in range(n): 

107 prob += lpSum(x[i] for i, btn in enumerate(buttons) if k in btn) == b[k] 

108 

109 # Solveur CBC silencieux 

110 solver = PULP_CBC_CMD(msg=False, keepFiles=False) 

111 

112 with suppress_output(): 

113 status = prob.solve(solver) 

114 

115 if status != LpStatusOptimal: 115 ↛ 116line 115 didn't jump to line 116 because the condition on line 115 was never true

116 return None 

117 

118 return int(sum(v.value() for v in x)) 

119 

120# =========================================================================== 

121 

122# %% ======================================================================== 

123# Résolution 

124def solve(lines: List[str]) -> int: 

125 """ 

126 Parse une ligne du type : 

127 

128 [.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7} 

129 

130 Extraction : 

131 - le schéma lumineux [] est ignoré 

132 - les boutons (a,b,c) 

133 - la cible {x,y,z} 

134 

135 On calcule pour chaque machine le minimal d'appuis et on cumule. 

136 

137 :param lines: Liste des lignes du fichier d'entrée 

138 :return: Somme des minima d'appuis pour toutes les machines 

139 """ 

140 total = 0 

141 

142 for line in lines: 

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

144 continue 

145 

146 # Ignorer la partie entre [] 

147 after = line.split(']')[1] if ']' in line else line 

148 

149 # ---- Boutons ---- 

150 before_brace = after.split('{')[0].strip() 

151 parts = before_brace.split(')') 

152 

153 buttons = [] 

154 for p in parts: 

155 if '(' not in p: 

156 continue 

157 inside = p.split('(')[1].strip() 

158 if inside == '': 158 ↛ 159line 158 didn't jump to line 159 because the condition on line 158 was never true

159 buttons.append(()) 

160 else: 

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

162 

163 # ---- Cibles ---- 

164 if '{' in line and '}' in line: 164 ↛ 168line 164 didn't jump to line 168 because the condition on line 164 was always true

165 inside = line.split('{')[1].split('}')[0] 

166 target_list = [int(x) for x in inside.split(',') if x.strip() != ''] 

167 else: 

168 target_list = [] 

169 

170 res = min_presses_joltage(target_list, buttons) 

171 if res is None: 171 ↛ 172line 171 didn't jump to line 172 because the condition on line 171 was never true

172 raise ValueError(f"Aucune solution trouvée pour la ligne : {line!r}") 

173 

174 total += res 

175 

176 return total 

177 

178# =========================================================================== 

179 

180# %% ======================================================================== 

181# MAIN 

182if __name__ == "__main__": 

183 RESULT = solve(get_input(10, False)) # True pour example, False pour input réel 

184 

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

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

187 print("═" * 60) 

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

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

190 

191# ===========================================================================