On voit que pour obtenir le résultat de la ligne 2, 25, on a quatre boutons possibles, notés a, b, c, d. On a a+b+c+d=25, ça fait pas beaucoup de combinaisons, ici 3276, calculées en python avec itertools.combinations_with_replacement([a,b,c,d],25).
Et après je brute-force un peu en espérant avoir suffisamment réduit le champs des possibles.
Ça simplifie suffisamment le problème pour permettre de résoudre la plupart des problèmes parfois en assez longtemps, mais clairement pas tous, j'ai oublié mon programme deux jours, et j'ai un problème qui tournait encore.
Donc là il faut simplifier la matrice. Je fais avec une diagonale, en gardant des nombres entiers positifs, donc je n'ai plus uniquement des 1 dedans.
Je réduis à ça, en réorganisant les lignes, mais l'ordre des boutons n'a pas d'importance, on a juste besoin du nombre total de boutons appuyés :
Ensuite, bah j'ai ma dernière colonne qui casse les pieds, on voit un maximum à 864/60, ou 56/4, ou 264/12, et un minimum à -468/-54, donc une valeur entre 9 et 14.
Alors on remplace, on regarde si notre solution devenue triviale (matrice diagonale, ça va :)) est entière, on jette, et on calcule la solution avec le minimum de boutons appuyés.
Facile.
Parfois, on n'a même pas de dernière colonne et la matrice est diagonale directement, super.
Et puis parfois on en a 2 ou 3, et ça devient casse-pied.
Les calculs de maxima et minima ne tiennent plus, puisque les boutons rebelles influent les uns sur les autres.
Au final j'ai énuméré toutes les possibilités d'appuyer de 0 à 200 fois sur chacun des derniers boutons et résolu, comme au dessus, solution entière, que des valeurs positives, et on prend la plus petite.
Le tout optimisé comme un projet Microsoft, ça prend 2 minutes 36s, et le résultat est valide.
Je n'arrive déjà plus à relire mon code, et ça sent qu'il faudrait utiliser une bibliothèque d'algèbre linéaire, au moins pour les simplifications, et manipulations de lignes et colonnes, un numpy avec des matrices propres serait probablement une grande avancée dans la lisibilité et les performances.
À noter qu'avec un solveur, dans l'exemple au dessus, il suffit de rajouter une ligne [0, 0, 0, 0, 0, 0, 0, 0, 0, 1] = (valeur de 9 à 14), et de lui dire « c'est bon, c'est carré, alors c'est quoi ma solution ? », de vérifier qu'elle est entière et de passer à la suite.
Mais bon, la résolution d'une matrice diagonale, c'est pas vraiment le plus difficile !
Bref, j'aurais bien pataugé dans ce problème, pour au final ne pas avoir trouvé de truc sensiblement différent des autres, moins bien fait et en plus longtemps.
Officiellement la cuvée 2025 n'est pas la meilleure pour moi ;)
[^] # Re: Jour 10
Posté par Yth (Mastodon) . En réponse au journal Advent of Code 2025. Évalué à 3.
Ben j'ai fini par bricoler un truc qui fonctionne, mais bigre, j'ai pas les maths bien à plat sur ce problème.
Au début j'avais cherché les boutons avec le moins de choix possibles.
Exemple :
On voit que pour obtenir le résultat de la ligne 2, 25, on a quatre boutons possibles, notés a, b, c, d. On a a+b+c+d=25, ça fait pas beaucoup de combinaisons, ici 3276, calculées en python avec
itertools.combinations_with_replacement([a,b,c,d],25).Et après je brute-force un peu en espérant avoir suffisamment réduit le champs des possibles.
Ça simplifie suffisamment le problème pour permettre de résoudre la plupart des problèmes parfois en assez longtemps, mais clairement pas tous, j'ai oublié mon programme deux jours, et j'ai un problème qui tournait encore.
Donc là il faut simplifier la matrice. Je fais avec une diagonale, en gardant des nombres entiers positifs, donc je n'ai plus uniquement des 1 dedans.
Je réduis à ça, en réorganisant les lignes, mais l'ordre des boutons n'a pas d'importance, on a juste besoin du nombre total de boutons appuyés :
Ensuite, bah j'ai ma dernière colonne qui casse les pieds, on voit un maximum à 864/60, ou 56/4, ou 264/12, et un minimum à -468/-54, donc une valeur entre 9 et 14.
Alors on remplace, on regarde si notre solution devenue triviale (matrice diagonale, ça va :)) est entière, on jette, et on calcule la solution avec le minimum de boutons appuyés.
Facile.
Parfois, on n'a même pas de dernière colonne et la matrice est diagonale directement, super.
Et puis parfois on en a 2 ou 3, et ça devient casse-pied.
Les calculs de maxima et minima ne tiennent plus, puisque les boutons rebelles influent les uns sur les autres.
Au final j'ai énuméré toutes les possibilités d'appuyer de 0 à 200 fois sur chacun des derniers boutons et résolu, comme au dessus, solution entière, que des valeurs positives, et on prend la plus petite.
Le tout optimisé comme un projet Microsoft, ça prend 2 minutes 36s, et le résultat est valide.
Je n'arrive déjà plus à relire mon code, et ça sent qu'il faudrait utiliser une bibliothèque d'algèbre linéaire, au moins pour les simplifications, et manipulations de lignes et colonnes, un numpy avec des matrices propres serait probablement une grande avancée dans la lisibilité et les performances.
À noter qu'avec un solveur, dans l'exemple au dessus, il suffit de rajouter une ligne
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1] = (valeur de 9 à 14), et de lui dire « c'est bon, c'est carré, alors c'est quoi ma solution ? », de vérifier qu'elle est entière et de passer à la suite.Mais bon, la résolution d'une matrice diagonale, c'est pas vraiment le plus difficile !
Bref, j'aurais bien pataugé dans ce problème, pour au final ne pas avoir trouvé de truc sensiblement différent des autres, moins bien fait et en plus longtemps.
Officiellement la cuvée 2025 n'est pas la meilleure pour moi ;)