Coverage for Day11 / part2.py: 100%

1#! /usr/bin/env python 

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

3 

4""" 

5Advent Of Code 2025 

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

7Day : 11 

8Part : 2 

9 

10Résolution du problème : compter le nombre total de chemins allant de 'svr' vers 'out' 

11tout en imposant que chaque chemin passe obligatoirement par *dac* ET *fft*. 

12Le graphe est dirigé, potentiellement très ramifié, et l'exploration naïve serait 

13explosive. On utilise donc une recherche en profondeur combinée à un mécanisme 

14de mémoïsation afin d'éviter toute recomputation inutile. 

15 

16L'état de recherche inclut le nœud courant ainsi que deux indicateurs booléens 

17permettant de savoir si 'dac' et/ou 'fft' ont déjà été visités. 

18""" 

19 

20# =========================================================================== 

21 

22# %% ======================================================================== 

23# LECTURE DE L’INPUT 

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

25 """ 

26 Lit le fichier d'entrée associé au jour donné. 

27 

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

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

30 :return: Liste de lignes (chaînes de caractères) sans retour à la ligne final. 

31 """ 

32 # /!\ Jour11 la part2 à son propre fichier d'exemple 

33 file = "example2.txt" if example else "input.txt" 

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

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

36 

37# =========================================================================== 

38 

39 

40# %% ======================================================================== 

41# Résolution 

42def solve(data: list) -> int: 

43 """ 

44 Compte le nombre total de chemins allant de 'svr' à 'out' et passant 

45 obligatoirement par les nœuds 'dac' et 'fft'. 

46 

47 Le graphe est décrit sous la forme : 

48 device: a b c 

49 signifiant que `device` pointe vers les nœuds a, b, c. 

50 

51 La fonction réalise une exploration DFS annotée : 

52 - Chaque appel de dfs(device, seen_dac, seen_fft) représente un état unique 

53 associé au nœud courant et aux flags déjà rencontrés. 

54 - Un cache (memo) évite de recalculer les sous-chemins identiques. 

55 - Lorsqu'on atteint 'out', on ne valide le chemin que si DAC ET FFT ont 

56 effectivement été rencontrés. 

57 

58 :param data: Liste de lignes représentant le graphe. 

59 :return: Nombre total de chemins valides. 

60 """ 

61 # Construction du graphe sous forme de dictionnaire { noeud: [sorties...] } 

62 server = {} 

63 for line in data: 

64 device, outputs = line.split(": ") 

65 server[device] = outputs.split() 

66 

67 # Mémoïsation : 

68 # (device, seen_dac, seen_fft) → nombre de chemins valides depuis cet état. 

69 memo = {} 

70 

71 def dfs(device: str, seen_dac: bool, seen_fft: bool) -> int: 

72 """ 

73 Explore récursivement tous les chemins depuis 'device'. 

74 Les indicateurs seen_dac et seen_fft suivent l'état du chemin courant. 

75 """ 

76 key = (device, seen_dac, seen_fft) 

77 

78 # Résultat déjà calculé → accélération massive sur les grands graphes 

79 if key in memo: 

80 return memo[key] 

81 

82 # Cas terminal : arrivée sur 'out' 

83 if device == "out": 

84 # Le chemin est valide uniquement si les deux nœuds obligatoires ont été vus 

85 memo[key] = 1 if (seen_dac and seen_fft) else 0 

86 return memo[key] 

87 

88 total = 0 

89 

90 # Exploration des successeurs 

91 for nxt in server.get(device, []): 

92 total += dfs( 

93 nxt, 

94 seen_dac or (nxt == "dac"), # Mémoire de passage par 'dac' 

95 seen_fft or (nxt == "fft") # Mémoire de passage par 'fft' 

96 ) 

97 

98 memo[key] = total 

99 return total 

100 

101 # Lancement depuis la racine 

102 return dfs("svr", False, False) 

103 

104# =========================================================================== 

105 

106 

107# %% ======================================================================== 

108# MAIN 

109if __name__ == "__main__": 

110 RESULT = solve(get_input(11, False)) 

111 

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

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

114 print("═" * 60) 

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

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

117 

118# ===========================================================================