◂ 7 décembre 2025 ▸
Laboratories : Faire se séparer des chemins et compter le nombre de façons récursivement
.. … .......S......... … ..
.. … ................. … ..
.. … .......^......... … ..
.. … ................. … ..
.. … ......^.^........ … ..
.. … ................. … ..
.. … .....^...^....... … ..
.. … ................. … ..
.. … ....^.^.^.^...... … ..
⋮
.. … .^...^...^.^.^.^. … ..
⋮
L'input représente un sapin de 142 lignes de longueur 141, mais avec une ligne sur deux remplie uniquement de points et inutiles dans les calculs.
La partie 2, sans memoization, partirait façon exponentielle avec plus de 2^1750 appels.
Le plus simple est de calculer la réponse à la partie 1 via une variable globale, mais ce n'est pas très beau.
Une version plus propre, mais plus lente, est donnée dans code1_2_noGlobal.py.
- code1.py
- code1_2.py
- code1_2_noGlobal.py
from functools import lru_cache
lines = []
with open('input.txt', 'r', encoding='utf-8') as f:
lines = [line.strip() for line in f.readlines()[::2]] # suppress useless even lines
@lru_cache(maxsize=None) # maxsize=None important to get the right value of rep1
def nb_ways(row, pos):
global rep1 # cannot be a parameter as it would break memoization
if row == len(lines) - 1:
return 1
line = lines[row + 1]
if line[pos] == '.':
return nb_ways(row + 1, pos)
else:
rep1 += 1
return nb_ways(row + 1, pos - 1) + nb_ways(row + 1, pos + 1)
rep1 = 0
rep2 = nb_ways(0, lines[0].index('S'))
print("Réponse partie 1:", rep1)
print("Réponse partie 2:", rep2)