◂ 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
⋮
Première partie: un algo simple qui tente toutes les possibilités fonctionne.
Pour la seconde, il faut un meilleur algo, mais on peut appliquer quelques règles utiles lors de la résolution d'un
nonogramme.
- code1.py
- code2.py
f = open("input.txt", 'r', encoding='utf-8')
lines = [line[:-1] for line in f.readlines()]
from itertools import combinations
def get_longueur_iles(line: str) -> list[int] :
return [len(ile) for ile in line.split() if len(ile)]
def remplacer_inconnus(symboles: list[str], indices_placement: list[int]) -> str:
symboles = symboles[:] # faire une copie pour ne pas modifier l'original
for indice in indices_placement:
symboles[indice] = '#'
return ''.join(symboles).replace('?', ' ')
def get_nb_possibilites(symboles: list[str], longueurs_voulues: list[int]) -> int:
nb = 0
nb_hash_a_placer = sum(longueurs_voulues) - symboles.count('#')
indices_statut_inconnu = [indice for indice in range(len(symboles)) if symboles[indice] == '?']
for indices_placement in combinations(indices_statut_inconnu, nb_hash_a_placer):
if get_longueur_iles(remplacer_inconnus(symboles, indices_placement)) == longueurs_voulues:
nb += 1
return nb
nb = 0
for line in lines:
symboles, longueurs_voulues = line.split()
longueurs_voulues = [int(i) for i in longueurs_voulues.split(',')]
symboles = list(symboles.replace('.', ' ')) # pour appeler facilement split() ensuite
nb += get_nb_possibilites(symboles, longueurs_voulues)
print("Réponse partie 1:", nb)