Muchos problemas difíciles de LeetCode son problemas fáciles con solucionadores de restricciones

• Incluso los problemas difíciles de LeetCode se pueden resolver mucho más fácilmente usando un solucionador de restricciones
• En lugar de programación dinámica compleja o algoritmos propios, se puede usar un solucionador de restricciones como MiniZinc para resolver de forma sencilla problemas de optimización matemática
• Los lenguajes de programación tradicionales tienen dificultades para expresar este tipo de problemas de optimización matemática, por lo que el enfoque basado en restricciones destaca especialmente
• Incluso cuando aparecen casos excepcionales o restricciones adicionales, los cambios al modelo en un solucionador de restricciones son mínimos
• La complejidad en tiempo de ejecución puede ser peor que la de un algoritmo optimizado escrito a mano, pero tiene muchas ventajas en flexibilidad y productividad de desarrollo

---

Problemas de LeetCode resueltos con un solucionador de restricciones

Elegir la herramienta correcta

• El autor recibió el problema del “cambio con monedas” en su primera entrevista después de graduarse de la universidad

  • Dadas ciertas denominaciones de monedas, se trata de encontrar la cantidad mínima de monedas necesaria para completar una cantidad determinada
  • Usó un algoritmo voraz simple, pero no podía garantizar la solución óptima en todos los casos
  • La respuesta correcta era programación dinámica, pero como no pudo implementarla, falló en la entrevista

• Sin embargo, en lugar de implementar el algoritmo directamente, se puede resolver muy fácilmente usando un solucionador de restricciones como MiniZinc

  • Código de ejemplo:

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

  • Se puede ejecutar directamente el ejemplo de MiniZinc en línea

  • El solucionador encuentra progresivamente la solución óptima

Distintos problemas de optimización/satisfacción

• Los problemas de optimización matemática que aparecen con frecuencia en LeetCode y similares (incluyendo maximizar/minimizar una función objetivo y varias restricciones)
  suelen ser difíciles de resolver en un lenguaje de programación por la implementación de bajo nivel, pero encajan bien con un solucionador de restricciones
• Por ejemplo, distintos problemas del siguiente tipo entran en esta categoría

Ejemplo 1: problema de máxima ganancia con acciones

• “Dada una lista de precios de acciones, encuentra la ganancia máxima que se puede obtener comprando una vez y vendiendo después”
  • Tradicionalmente requiere fuerza bruta O(n²) o un algoritmo óptimo O(n)
  • En MiniZinc se puede definir de forma simple como el siguiente problema de restricciones

    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;
    

Ejemplo 2: llegar a 0 sumando/restando ciertos números (problema de satisfacción)

• “¿Se puede llegar a 0 sumando o restando tres números de la lista?”
  • No hace falta encontrar un valor óptimo, solo una solución satisfacible
  • En un solucionador de restricciones se expresa así

    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;
    

Ejemplo 3: área máxima de rectángulo en un histograma

• “Dado un histograma con la altura de cada barra, encuentra el área del rectángulo más grande que se puede formar”
  • Tradicionalmente requiere un algoritmo complejo y manejo de múltiples estados
  • Con solo restricciones se puede describir la solución de forma concisa

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

¿Es mejor el enfoque con solucionadores de restricciones?

• En una entrevista técnica tiene debilidades frente a preguntas sobre complejidad temporal

  • Es difícil predecir el tiempo de ejecución de un solucionador de restricciones, y normalmente será más lento que un algoritmo óptimo hecho a medida
  • Aun así, puede ser mejor que un algoritmo de mala calidad mal implementado, y para la mayoría de programadores no es fácil escribir siempre la mejor solución a mano

• La fortaleza real está en la flexibilidad para agregar nuevas restricciones

  • Por ejemplo, en el caso de las acciones, cambiar de una sola compra/venta a varias hace que la complejidad algorítmica aumente mucho
  • En el modelo de restricciones de MiniZinc, se pueden aceptar requisitos mucho más complejos con cambios mínimos en el código

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

• Los ejemplos de problemas de restricciones en línea suelen centrarse en rompecabezas como Sudoku, pero en realidad pueden usarse de forma más interesante y práctica en problemas con lógica de negocio o necesidades de optimización

  • Por ejemplo, también hay mucho potencial para aplicar técnicas avanzadas de optimización como symmetry breaking

Cierre y referencias

• Este texto forma parte del boletín semanal del autor, que trata sobre historia del software, métodos formales, nuevas tecnologías y teoría de ingeniería de software
• Si te interesa, puedes revisar la suscripción o el sitio web principal del autor
• Su nuevo libro "Logic for Programmers" también está en publicación