Pour la partie 1, il faut remarquer que l'ordre d'appui sur les boutons importe peu et qu'il ne sert à rien d'appuyer deux fois sur le même bouton.
Donc on peut tout encoder sous forme de bitset et faire un parcours en largeur sur les configurations possibles.
J'ai pris beaucoup de temps mais je suis finalement arrivé à avoir une solution pour la partie 2 sans utiliser de solveurs externes (j'ai d'abord utilisé Z3).
L'idée est qu'il faut résoudre un système d'équations linéaires comme dit dans un post plus haut en cherchant une solution avec des valeurs entières positives et qui minimisent la somme totale.
Le problème, c'est que la matrice n'est forcément carrée, pas forcément invertible donc il peut y avoir une infinité de solutions.
Le pivot de Gauss peut nous donner une solution mais ce n'est pas forcément la bonne.
Si on oublie la dernière colonne, on dit qu'une colonne est pivot si l'élément non nul le plus bas de cette colonne a la propriété suivante, il y a que des 0 à gauche et en dessous.
Donc, on voit ici que toutes les colonnes sont pivots sauf les deux avant-dernières.
L'algorithme se base sur le fait qu'il y a peu de colonnes non pivots.
Si la matrice n'a aucune colonne non pivot alors il existe une solution et donc on n'a pas besoin de cherche plus loin.
Sinon, on va partir d'en bas à droite et affectant les valeurs de la solution de droite à gauche.
Si une colonne j est pivot et que les variables à droite ont déjà affectés alors il n'y a qu'une seule valeur possible pour la variable x_j.
Par contre, si la colonne j n'est pas pivot, il peut y avoir plusieurs valeurs affectables à la variable x_j. On va donc affecter à cette variable, une valeur entre 0 et une certaine limite et faire du backtracking.
Comme il y a au plus 3 colonnes non pivots dans chaque matrice du jeu de données, il n'y pas une grande profondeur de backtracking.
Pour la limite, j'ai choisi une valeur qui allait bien pour le jeu de données, à savoir 200 si il y a au plus de colonnes non pivots et 30 si il y a 3 colonnes non pivots.
[^] # Re: Jour 10
Posté par Guillaume.B . En réponse au journal Advent of Code 2025. Évalué à 3.
Pour la partie 1, il faut remarquer que l'ordre d'appui sur les boutons importe peu et qu'il ne sert à rien d'appuyer deux fois sur le même bouton.
Donc on peut tout encoder sous forme de bitset et faire un parcours en largeur sur les configurations possibles.
J'ai pris beaucoup de temps mais je suis finalement arrivé à avoir une solution pour la partie 2 sans utiliser de solveurs externes (j'ai d'abord utilisé Z3).
L'idée est qu'il faut résoudre un système d'équations linéaires comme dit dans un post plus haut en cherchant une solution avec des valeurs entières positives et qui minimisent la somme totale.
Le problème, c'est que la matrice n'est forcément carrée, pas forcément invertible donc il peut y avoir une infinité de solutions.
Le pivot de Gauss peut nous donner une solution mais ce n'est pas forcément la bonne.
Imaginons qu'on est ce système d'équations
On va appliquer le pivot de gauss sur cette matrice et obtenir la matrice "échelonnée":
Si on oublie la dernière colonne, on dit qu'une colonne est pivot si l'élément non nul le plus bas de cette colonne a la propriété suivante, il y a que des 0 à gauche et en dessous.
Donc, on voit ici que toutes les colonnes sont pivots sauf les deux avant-dernières.
L'algorithme se base sur le fait qu'il y a peu de colonnes non pivots.
Si la matrice n'a aucune colonne non pivot alors il existe une solution et donc on n'a pas besoin de cherche plus loin.
Sinon, on va partir d'en bas à droite et affectant les valeurs de la solution de droite à gauche.
Si une colonne j est pivot et que les variables à droite ont déjà affectés alors il n'y a qu'une seule valeur possible pour la variable x_j.
Par contre, si la colonne j n'est pas pivot, il peut y avoir plusieurs valeurs affectables à la variable x_j. On va donc affecter à cette variable, une valeur entre 0 et une certaine limite et faire du backtracking.
Comme il y a au plus 3 colonnes non pivots dans chaque matrice du jeu de données, il n'y pas une grande profondeur de backtracking.
Pour la limite, j'ai choisi une valeur qui allait bien pour le jeu de données, à savoir 200 si il y a au plus de colonnes non pivots et 30 si il y a 3 colonnes non pivots.
En parallélisant, le temps d'exécution est 4ms.