• [^] # Re: Solution en Haskell

    Posté par . En réponse au message Advent of Code 2023, jour 12. Évalué à 2.

    Quelques commentaires sur ce que j'ai fait.

    Tout d'abord, par soucis de simplicité, je rajoute un symbole Operational (".") à la fin de la liste des sources.
    Ensuite, je calcule un tableau nextOperational qui pour chaque index dans la liste des sources me renvoie l'index de la prochaine source opérationnelle. Ca se fait aisément en temps linéaire et ça me permet d'optimiser le temps de calcul dans la programmation dynamique.

    Maintenant vient la programmation dynamique.
    Je note springs et groups la liste des sources et des groupes respectivement.
    J'essaie de résoudre récursivement le problème suivant:
    étant donné pos et groupPos combien y a-t-il d'arrangemnts dans la sous liste springs[pos:] satisfaisant les contraintes groups[groupPos:]. Je note f une telle fonction.
    Le cas de base est quand pos == taille(springs). Si groupPos = taille(groups), ça veut dire que les listes springs[pos:] et groups[groupPos:] sont vides. Ca match bien donc f(pos, groupPos) = 1. Sinon, f(pos, groupPos) = 0.
    Dans le cas récursif, il y a deux possibilités (non mutuellement excluses).
    Si la source à la position springs[pos] est opérationnelle ou inconnue alors je rajoute
    f(pos, groupPos+1) à f(pos, groupPos).
    L'autre cas est quand le bloc groups[groupPos] peut rentrer à la position pos.
    Pour vérifier cela, j'utilise mon tableau nextOperational et le fait donc en temps constant.
    Si le bloc rentre, je rajoute f(pos+groups[groupPos]+1, groupPos+1) à f(pos, groupPos).

    Je ne vais pas rentrer dans les détails mais j'obtiens au final une complexité en O(|springs| . |groups|) et du coup une résolution en 30ms pour la partie 2.