Coverage for Day3 / part2.py: 100%

1#! /usr/bin/env python 

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

3 

4""" 

5Advent Of Code 2025 

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

7Day : 3 

8Part : 2 

9 

10Ce script extrait, pour chaque identifiant numérique, la plus grande 

11sous-séquence possible de longueur fixée tout en respectant l’ordre 

12d’apparition des chiffres. 

13 

14L’objectif est d’optimiser la valeur numérique obtenue en conservant 

15exactement `n` digits parmi ceux présents dans l’identifiant d’origine. 

16 

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

18""" 

19 

20# %% ======================================================================== 

21# Imports 

22 

23# =========================================================================== 

24 

25# %% ======================================================================== 

26# Input data 

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

28 """ 

29 Lit le fichier d'input pour le jour donné. 

30 

31 :param day: numéro du jour AOC 

32 :param example: si True, utilise le fichier example.txt sinon input.txt 

33 :return: liste de lignes du fichier 

34 :rtype: list 

35 """ 

36 file = 'example.txt' if example else 'input.txt' 

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

38 return f.readlines() 

39 

40# =========================================================================== 

41 

42# %% ======================================================================== 

43# Résolution 

44def max_subsequence_as_number(digits: list, n: int) -> int: 

45 """ 

46 Détermine la plus grande sous-séquence possible de longueur `n` 

47 en conservant l’ordre d’apparition des digits. 

48 

49 On utilise ici une approche de type « monotonic stack » : 

50 - On sait combien de digits on peut supprimer : `m - n` 

51 - On construit une pile où chaque nouveau digit pousse les précédents 

52 plus petits, tant qu’on peut encore en retirer. 

53 - Le résultat final est simplement les `n` premiers digits de la pile. 

54 

55 :param digits: liste de chiffres extraits de la ligne 

56 :param n: longueur de la sous-séquence maximale à conserver 

57 :return: le nombre entier formé par la sous-séquence maximale 

58 :rtype: int 

59 """ 

60 m = len(digits) 

61 

62 # Nombre total de suppressions possibles pour atteindre n digits 

63 remove = m - n 

64 stack = [] 

65 for d in digits: 

66 # Tant qu'on peut supprimer, et que le digit précédent est plus petit, 

67 # on le retire pour laisser place à un chiffre plus grand. 

68 while stack and remove > 0 and stack[-1] < d: 

69 stack.pop() 

70 remove -= 1 

71 

72 # On empile le digit courant dans la séquence 

73 stack.append(d) 

74 

75 # S'il reste des suppressions non utilisées, 

76 # on coupe simplement la fin de la pile. 

77 final = stack[:n] 

78 

79 # Construction du nombre final 

80 return int("".join(str(d) for d in final)) 

81 

82# --------------------------------------------------------------------------- 

83def solve(data: list, n: int = 12) -> int: 

84 """ 

85 Calcule la somme des plus grandes sous-séquences pour chaque ligne d’input. 

86 

87 Pour chaque ligne : 

88 - Nettoyage du texte 

89 - Conversion en liste de digits 

90 - Extraction de la meilleure sous-séquence possible (length = n) 

91 - Accumulation du total 

92 

93 :param data: lignes du fichier d’entrée 

94 :param n: longueur des sous-séquences à conserver 

95 :return: somme des valeurs trouvées 

96 :rtype: int 

97 """ 

98 joltage = 0 

99 for line in data: 

100 line = line.strip() 

101 digits = [int(d) for d in line] 

102 

103 joltage += max_subsequence_as_number(digits, n) 

104 

105 return joltage 

106 

107# =========================================================================== 

108 

109# %% 

110if __name__ == "__main__": 

111 RESULT = solve(get_input(3, False), 12) 

112 

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

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

115 print("═" * 60) 

116 print(f"Joltage trouvé : \033[96m{RESULT}\033[0m") 

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

118