Viele schwierige LeetCode-Probleme sind einfache Constraint-Probleme

• Selbst schwierige LeetCode-Probleme lassen sich mit einem Constraint-Solver deutlich leichter lösen
• Statt komplexer dynamischer Programmierung oder eigener Algorithmen können mit Constraint-Solvern wie MiniZinc mathematische Optimierungsprobleme einfach gelöst werden
• Traditionelle Programmiersprachen eignen sich nur schwer dazu, solche mathematischen Optimierungsprobleme auszudrücken, weshalb ein constraint-basierter Ansatz hier seine Stärken ausspielt
• Selbst wenn Sonderfälle oder zusätzliche Constraints hinzukommen, sind bei einem Constraint-Solver nur minimale Änderungen am Modell nötig
• Die Laufzeitkomplexität kann zwar schlechter sein als bei einem handoptimierten Algorithmus, aber bei Flexibilität und Entwicklungsgeschwindigkeit gibt es viele Vorteile

---

LeetCode-Probleme mit einem Constraint-Solver lösen

Das richtige Werkzeug wählen

• Der Autor bekam in seinem ersten Bewerbungsgespräch nach dem Uniabschluss das "Coin Change Problem"

  • Gegeben sind Münzwerte, gesucht ist die minimale Anzahl von Münzen, um einen bestimmten Betrag herauszugeben
  • Er verwendete einen einfachen Greedy-Algorithmus, der jedoch nicht in allen Fällen die optimale Lösung garantiert
  • Dynamische Programmierung wäre die richtige Antwort gewesen, aber weil er sie nicht implementieren konnte, scheiterte das Gespräch

• Mit einem Constraint-Solver wie MiniZinc lässt sich das Problem aber sehr einfach lösen, ohne den Algorithmus selbst zu implementieren

  • Beispielcode:

    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);
    

  • Das Beispiel lässt sich online direkt in MiniZinc ausführen

  • Der Solver findet schrittweise die optimale Lösung

Verschiedene Optimierungs-/Erfüllungsprobleme

• Mathematische Optimierungsprobleme, wie sie auf LeetCode häufig vorkommen (Maximierung/Minimierung einer Zielfunktion unter mehreren Constraints), sind in Programmiersprachen wegen der Low-Level-Implementierung oft schwer auszudrücken, passen aber gut zu Constraint-Solvern
• Dazu gehören zum Beispiel verschiedene Probleme der folgenden Art

Beispiel 1: Problem des maximalen Aktiengewinns

• "Gegeben ist eine Liste von Aktienkursen. Bestimme den maximalen Gewinn, der durch einmaliges Kaufen und späteres Verkaufen erzielt werden kann"
  • Traditionell braucht man dafür entweder O(n²)-Brute-Force oder einen optimalen O(n)-Algorithmus
  • In MiniZinc lässt sich das einfach als Constraint-Problem formulieren

    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;
    

Beispiel 2: Mit Addition/Subtraktion bestimmter Zahlen 0 erzeugen (Erfüllbarkeitsproblem)

• "Kann man aus einer Liste drei Zahlen addieren oder subtrahieren, sodass 0 entsteht?"
  • Es muss kein optimaler Wert gefunden werden, sondern nur eine erfüllbare Lösung
  • In einem Constraint-Solver kann man das so ausdrücken

    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;
    

Beispiel 3: Größte Rechteckfläche in einem Histogramm

• "Gegeben ist ein Histogramm mit den Höhen seiner Balken. Bestimme die größte mögliche Rechteckfläche"
  • Traditionell braucht man dafür komplexe Algorithmen und die Verwaltung vieler Zustände
  • Mit Constraints allein lässt sich die Lösung kompakt beschreiben

    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)"]
    

Ist der Constraint-Solver-Ansatz wirklich besser?

• In Bewerbungsgesprächen hat dieser Ansatz Schwächen, etwa bei Fragen zur Zeitkomplexität

  • Die Laufzeit eines Constraint-Solvers ist schwer vorherzusagen und meist langsamer als ein maßgeschneiderter optimaler Algorithmus
  • Trotzdem ist er besser als ein fehlerhaft implementierter schlechter Algorithmus, und die meisten Programmierer können nicht jedes Mal die optimale Lösung selbst schreiben

• Die eigentliche Stärke ist die Flexibilität, wenn neue Constraints hinzukommen

  • Wenn man im Aktienbeispiel etwa nicht nur einmal, sondern mehrfach kaufen und verkaufen darf, steigt die algorithmische Komplexität stark an
  • In einem Constraint-Modell in MiniZinc lassen sich solche deutlich komplexeren Anforderungen mit nur kleinen Codeänderungen abbilden

    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)"];
    

• Online-Beispiele für Constraint-Probleme drehen sich oft um Rätsel wie Sudoku, doch tatsächlich lässt sich der Ansatz interessanter und praktischer für Business-Logik oder Optimierungsanforderungen nutzen

  • Zum Beispiel ist auch der Einsatz fortgeschrittener Optimierungstechniken wie symmetry breaking gut möglich

Abschluss und Hinweise

• Dieser Text stammt aus dem wöchentlichen Newsletter des Autors und behandelt Softwaregeschichte, formale Methoden, neue Technologien und Theorien des Software Engineering
• Bei Interesse kann man den Newsletter abonnieren oder die Hauptwebsite des Autors besuchen
• Das neue Buch des Autors "Logic for Programmers" ist ebenfalls erschienen