Beaucoup de problèmes difficiles sur LeetCode sont en réalité de simples problèmes à contraintes

• Même les problèmes difficiles de LeetCode peuvent être résolus bien plus facilement avec des solveurs de contraintes
• Au lieu d’une programmation dynamique complexe ou d’un algorithme maison, on peut utiliser un solveur de contraintes comme MiniZinc pour résoudre simplement des problèmes d’optimisation mathématique
• Les langages de programmation traditionnels expriment mal ce type de problèmes d’optimisation mathématique, ce qui fait la force de l’approche fondée sur les contraintes
• Même lorsque des cas particuliers ou des contraintes supplémentaires apparaissent, les modifications du modèle restent minimes dans un solveur de contraintes
• La complexité à l’exécution peut être moins bonne qu’avec un algorithme optimisé écrit à la main, mais cette approche offre de nombreux avantages en souplesse et en productivité de développement

---

Résoudre des problèmes LeetCode avec un solveur de contraintes

Choisir le bon outil

• Lors de son premier entretien après l’université, l’auteur a reçu le problème de la « monnaie à rendre »

  • Étant donné un ensemble de pièces, il faut trouver le nombre minimal de pièces nécessaire pour rendre un montant donné
  • Il a utilisé un simple algorithme glouton, sans pouvoir garantir une solution optimale dans tous les cas
  • La bonne réponse était la programmation dynamique, mais il n’a pas su l’implémenter et a échoué à l’entretien

• Pourtant, sans implémenter directement l’algorithme, on peut résoudre cela très facilement avec un solveur de contraintes comme MiniZinc

  • Exemple de code :

    int: total;
    array[int] of int: values = [10, 9, 1];
    array[index_set(values)] of var 0..: coins;
    
    constraint sum (c in index_set(coins)) (coins[c] * values[c]) == total;
    solve minimize sum(coins);
    

  • On peut essayer directement l’exemple MiniZinc en ligne

  • Le solveur trouve progressivement la solution optimale

Divers problèmes d’optimisation et de satisfaction

• Les problèmes d’optimisation mathématique courants sur LeetCode, avec fonction objectif à maximiser/minimiser et multiples contraintes,
  sont difficiles à résoudre en langage de programmation à cause du niveau d’implémentation bas, mais conviennent bien aux solveurs de contraintes
• Par exemple, les types de problèmes suivants en font partie

Exemple 1 : profit maximal sur une action

• « À partir d’une liste de prix d’actions, trouver le profit maximal qu’on peut obtenir en achetant une fois puis en revendant plus tard »
  • Traditionnellement, il faut un brute force en O(n²) ou un algorithme optimal en O(n)
  • Dans MiniZinc, on peut le définir simplement comme un problème à contraintes

    array[int] of int: prices = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
    var int: buy;
    var int: sell;
    var int: profit = prices[sell] - prices[buy];
    
    constraint sell > buy;
    constraint profit > 0;
    solve maximize profit;
    

Exemple 2 : obtenir 0 en additionnant/soustrayant certains nombres (problème de satisfaction)

• « Peut-on obtenir 0 en additionnant ou soustrayant trois nombres d’une liste ? »
  • Il ne s’agit pas de trouver une valeur optimale, seulement une solution satisfaisante
  • Dans un solveur de contraintes, cela s’exprime ainsi

    include "globals.mzn";
    array[int] of int: numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
    array[index_set(numbers)] of var {0, -1, 1}: choices;
    
    constraint sum(n in index_set(numbers)) (numbers[n] * choices[n]) = 0;
    constraint count(choices, -1) + count(choices, 1) = 3;
    solve satisfy;
    

Exemple 3 : aire maximale d’un rectangle dans un histogramme

• « Dans un histogramme dont on connaît la hauteur de chaque barre, trouver l’aire du plus grand rectangle possible »
  • Traditionnellement, cela demande un algorithme complexe et beaucoup de gestion d’état
  • Avec de seules contraintes, on peut décrire la solution de façon concise

    array[int] of int: numbers = [2,1,5,6,2,3];
    
    var 1..length(numbers): x; 
    var 1..length(numbers): dx;
    var 1..: y;
    
    constraint x + dx <= length(numbers);
    constraint forall (i in x..(x+dx)) (y <= numbers[i]);
    
    var int: area = (dx+1)*y;
    solve maximize area;
    
    output ["(\(x)->\(x+dx))*\(y) = \(area)"]
    

L’approche par solveur de contraintes est-elle meilleure ?

• En entretien, cela présente des faiblesses sur des questions comme la complexité temporelle

  • Le temps d’exécution d’un solveur de contraintes est difficile à prévoir, et il est généralement plus lent qu’un algorithme optimal sur mesure
  • Mais cela reste préférable à un algorithme mal implémenté de mauvaise qualité, et la plupart des programmeurs n’écrivent pas facilement la solution optimale eux-mêmes à chaque fois

• Sa vraie force est la souplesse face à l’ajout de nouvelles contraintes

  • Par exemple, dans le cas des actions, passer d’un seul achat/vente à plusieurs fait exploser la complexité algorithmique
  • Dans un modèle de contraintes MiniZinc, on peut accepter des exigences bien plus complexes avec de petits changements de code

    include "globals.mzn";
    int: max_sales = 3;
    int: max_hold = 2;
    array[int] of int: prices = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
    array [1..max_sales] of var int: buy;
    array [1..max_sales] of var int: sell;
    array [index_set(prices)] of var 0..max_hold: stocks_held;
    var int: profit = sum(s in 1..max_sales) (prices[sell[s]] - prices[buy[s]]);
    
    constraint forall (s in 1..max_sales) (sell[s] > buy[s]);
    constraint profit > 0;
    
    constraint forall(i in index_set(prices)) (stocks_held[i] = (count(s in 1..max_sales) (buy[s] <= i) - count(s in 1..max_sales) (sell[s] <= i)));
    constraint alldifferent(buy ++ sell);
    solve maximize profit;
    
    output ["buy at \(buy)\n", "sell at \(sell)\n", "for \(profit)"];
    

• Les exemples de problèmes à contraintes en ligne sont souvent centrés sur des puzzles comme Sudoku, mais cette approche peut être plus intéressante et plus utile en pratique pour de la logique métier ou des besoins d’optimisation réels

  • Par exemple, elle se prête aussi à l’application de techniques d’optimisation avancées comme le symmetry breaking

Conclusion et références

• Cet article est issu de la newsletter hebdomadaire de l’auteur, consacrée à l’histoire du logiciel, aux méthodes formelles, aux nouvelles technologies et à la théorie de l’ingénierie logicielle
• Si cela vous intéresse, vous pouvez vous abonner ou consulter le site principal de l’auteur
• Son nouveau livre, "Logic for Programmers", est également en cours de publication