Pfiou, j'en suis venu à bout, mais pas tout seul. Ça a fini par me rappeler des notions d'optimisation linéaire, du coup j'ai été rafraîchir mes connaissances sur le sujet.
Un problème d'optimisation linéaire est défini par :
une fonction de coût (en fait un vecteur, dont on prend le produit scalaire avec chaque solution possible) ;
des contraintes d'inégalité sur les variables, individuellement ou collectivement (une matrice et un vecteur borne supérieure) ;
des contraintes d'égalité collectives sur les variables (une matrice et un vecteur résultat).
Il se trouve que ça colle plutôt bien avec notre problème :
le coût, qu'on cherche à minimiser, c'est la somme des pressions sur chaque bouton, autrement dit un vecteur dont chaque coordonnée vaut un ;
les contraintes d'inégalité individuelles, c'est plus grand que zéro et moins grand que le plus petit joltage cible piloté par le bouton considéré ;
la contrainte d'égalité collective, c'est la matrice de pilotage et les joltages cibles.
Avec scipy.optimize.linprog, ça marche super bien. À un petit détail près : ça sort des résultats qui ne sont pas toujours entiers. Mais ça tombe bien, il a aussi une option pour définir des contraintes d'entièreté pour les variable. Et hop, on a le résultat cherché.
Clairement, j'aurais été incapable de résoudre ça sans recourir à un optimiseur linéaire. Mais je reste satisfait d'avoir d'une part déterminé que ça correspondait à un problème d'optimisation linéaire et d'avoir correctement spécifié tout ça pour l'entrer dans ledit solveur.
[^] # Re: Jour 10
Posté par 🚲 Tanguy Ortolo (site web personnel) . En réponse au journal Advent of Code 2025. Évalué à 4. Dernière modification le 11 décembre 2025 à 18:05.
Pfiou, j'en suis venu à bout, mais pas tout seul. Ça a fini par me rappeler des notions d'optimisation linéaire, du coup j'ai été rafraîchir mes connaissances sur le sujet.
Un problème d'optimisation linéaire est défini par :
Il se trouve que ça colle plutôt bien avec notre problème :
Avec
scipy.optimize.linprog, ça marche super bien. À un petit détail près : ça sort des résultats qui ne sont pas toujours entiers. Mais ça tombe bien, il a aussi une option pour définir des contraintes d'entièreté pour les variable. Et hop, on a le résultat cherché.Clairement, j'aurais été incapable de résoudre ça sans recourir à un optimiseur linéaire. Mais je reste satisfait d'avoir d'une part déterminé que ça correspondait à un problème d'optimisation linéaire et d'avoir correctement spécifié tout ça pour l'entrer dans ledit solveur.