Advent of code

◂ 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.
  1. code1.py
  2. code1_2.py
  3. 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
def split_points_and_number_of_ways(row, pos) -> tuple[set, int]:
    if row == len(lines) - 1:
        return set(), 1 
    line = lines[row + 1]
    if line[pos] == '.':
        return split_points_and_number_of_ways(row + 1, pos)
    else:
        splits1, nb_ways1 = split_points_and_number_of_ways(row + 1, pos - 1)
        splits2, nb_ways2 = split_points_and_number_of_ways(row + 1, pos + 1)
        return splits1.union(splits2).union([(row,pos)]), nb_ways1 + nb_ways2

split_points, nb_ways = split_points_and_number_of_ways(0, lines[0].index('S'))
print("Réponse partie 1:", len(split_points))
print("Réponse partie 2:", nb_ways)