Advent of code

◂ 12 décembre 2023 ▸

  Hot Springs : Compter les façons de compléter une ligne façon nonogramme.

.?#??.??#???.?? 2,6,2

?#??.?#.???#. 3,1,3

.#??#?#?.?##?#. 6,5

1. code1.py
2. code2.py

f = open("input.txt", 'r', encoding='utf-8')
lines = [line[:-1] for line in f.readlines()]

from functools import lru_cache
@lru_cache(None)    # permet de gagner un temps fou, résultat quasi instantané au lieu de plusieurs heures,jours?
def get_nb_possibilites(symbs: str, longueurs: list[int]) -> int :
    symbs = symbs.strip()
    if len(longueurs) == 0:
        return 0 if '#' in symbs else 1
    # Place minimale pour mettre les iles (deux critères en un). Optimise un peu et évite une vérif plus loin
    if len(symbs) < sum(longueurs) + max(symbs.count(' '), len(longueurs) - 1):
        return 0
        
    if symbs[0] == '#':
        if ' ' in symbs[:longueurs[0]]:
            return 0
        if len(symbs) == longueurs[0]:
            if len(longueurs) == 1:
                return 1
            else:
                return 0
        if symbs[longueurs[0]] == '#':
            return 0
        return get_nb_possibilites(symbs[longueurs[0]+1:], tuple(longueurs[1:]))

    ####  Le problème est symétrique. Change peu et même un peu +long au final (->appel de fonction) si on vide le cache entre les lignes
    #if symbs[-1] == '#':     
    #    return get_nb_possibilites(symbs[::-1], longueurs[::-1])

    return get_nb_possibilites('#' + symbs[1:], longueurs) + get_nb_possibilites(symbs[1:], longueurs)

    
for partie, multiplicateur in enumerate([1, 5]):
    nb = 0
    for line in lines:
        symboles, longueurs_voulues = line.split()
        longueurs_voulues = multiplicateur * [int(i) for i in longueurs_voulues.split(',')]
        symboles = symboles.replace('.', ' ')   # cette fois, pour appeler facilement strip() ensuite
        symboles = (multiplicateur-1) * (symboles + '?') + symboles
        nb += get_nb_possibilites(symboles, tuple(longueurs_voulues))
        get_nb_possibilites.cache_clear()   # le cache est surtout utile sur une même ligne, donc on évite 
                                            # de le charger avec les anciennes lignes (change peu le résultat)

    print(f"Réponse partie {partie + 1}: {nb}")