• [^] # Re: Rien de vraiment compliqué, il faut juste utiliser tout ce qu'on sait faire.

    Posté par . En réponse au message Advent of Code 2023, jour 12. Évalué à 2. Dernière modification le 16 décembre 2023 à 00:29.

    Je met mon message en réponse à vous 2 au cas où vous auriez un peu de temps. Je bute sur la partie 2 et je voudrais pas lire une solution directement donc j'ai essayé de ne lire que le minimum de vos échanges pour savoir si vous aviez une solution vraiment plus efficace que la mienne et c'est le cas.

    Pour la partie 1 j'ai fais du bête de chez bête j'itère de 0 à 2 puissance le nombre de ? et je place de # là où j'ai des 1 et des . là où j'ai des 0 dans le nombre courant.

    Évidement O(2n) ça marche pas pour la partie 2. J'ai repris la question autrement et je conçois les solutions possibles comme un arbre binaire je fais un parcours en largeur de l'arbre pour pouvoir couper les branches dès que je vois qu'elles ne marchent pas.

    Si je montre ça en pseudo code python ça donne :

    paths=['???.###????.###????.###????.###????.###']
result=0
while len(paths) > 0:
 current_path=pop(paths)
 switch one_step(current_path, [1,1,3,1,1,3,1,1,3,1,1,3,1,1,3]:
 case Success:
 result += 1
 case Fail:
 pass
 case Path(p1, p2):
 paths.append(p1)
 paths.append(p2)

    avec one_step() qui vérifie s'il y a encore des ? si ce n'est pas le cas il vérifie si c'est bon ou non et renvoie Success/Fail

    s'il reste des ? il vérifie si c'est partiellement valide (il ne vérifie pas que tous les blocs sont présents) si ça ne l'est pas Fail si oui il renvoie la chaine qu'il a en argument 2 fois : une en ayant remplacé le prochain ? par un # et une ou c'est par un .

    Pour moi je suis en O(log2(N)) et ça marche bien sur l'exemple mais pas du tout sur le puzzle.

    Je suis complètement à côté de la plaque ? (là ça tourne depuis 23 minutes... :( )

    https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll