कई कठिन LeetCode समस्याएँ दरअसल आसान constraint problems हैं

 (buttondown.com)
6 पॉइंट द्वारा GN⁺ 2025-09-13 | अभी कोई टिप्पणी नहीं है. | WhatsApp पर शेयर करें
  • LeetCode की कठिन समस्याएँ भी constraint solver का उपयोग करने पर काफ़ी आसानी से हल की जा सकती हैं
  • जटिल dynamic programming या अपने खुद के algorithm की जगह MiniZinc जैसे constraint solver का उपयोग करके mathematical optimization problems को सरलता से हल किया जा सकता है
  • पारंपरिक programming languages में ऐसे mathematical optimization problems को व्यक्त करना कठिन होता है, इसलिए constraint-based approach की अपनी मज़बूती है
  • exception cases या अतिरिक्त constraints आने पर भी constraint solver में model बदलना न्यूनतम रहता है
  • runtime complexity सीधे लिखे गए optimized algorithm की तुलना में धीमी हो सकती है, लेकिन flexibility और development productivity के लिहाज़ से इसके कई फ़ायदे हैं

constraint solver से हल की जाने वाली LeetCode समस्याएँ

सही tool का चयन

  • लेखक को कॉलेज से स्नातक होने के बाद अपने पहले इंटरव्यू में 'coin change problem' दी गई थी

    • जब coin denominations दी जाएँ, तो किसी निश्चित राशि को चुकाने के लिए ज़रूरी coins की न्यूनतम संख्या निकालने की समस्या
    • उन्होंने एक साधारण greedy algorithm का उपयोग किया, लेकिन वह हर मामले में optimal solution की गारंटी नहीं दे सका
    • dynamic programming सही उत्तर था, लेकिन उसे implement न कर पाने के कारण इंटरव्यू असफल रहा

  • लेकिन अगर algorithm को खुद implement करने की बजाय MiniZinc जैसे constraint solver का उपयोग किया जाए, तो इसे बहुत आसानी से हल किया जा सकता है

    • उदाहरण कोड:

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

    • ऑनलाइन सीधे MiniZinc उदाहरण चलाकर देखा जा सकता है

    • solver धीरे-धीरे optimal solution खोज देता है

विभिन्न optimization/satisfaction problems

  • LeetCode आदि में अक्सर आने वाली mathematical optimization problems (objective function को maximize/minimize करना और कई constraints शामिल होना)
    programming language में हल करते समय low-level implementation की वजह से कठिन लगती हैं, लेकिन constraint solver के लिए उपयुक्त होती हैं
  • उदाहरण के लिए, नीचे दिए गए स्वभाव की कई समस्याएँ इसमें आती हैं

उदाहरण 1: अधिकतम stock profit समस्या

  • 'सूची के रूप में दिए गए stock price data में, एक बार खरीदकर उसके बाद बेचने पर मिलने वाला अधिकतम लाभ निकालो'
    • पारंपरिक रूप से O(n²) brute force या O(n) optimal algorithm की आवश्यकता होती है
    • MiniZinc में इसे नीचे की तरह एक सरल constraint problem के रूप में परिभाषित किया जा सकता है 
      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;

उदाहरण 2: कुछ संख्याओं को जोड़/घटा कर 0 बनाना (satisfaction problem)

  • 'क्या सूची में से तीन संख्याओं को जोड़कर या घटाकर 0 बनाया जा सकता है?'
    • यहाँ optimal value नहीं, सिर्फ़ satisfiable solution चाहिए
    • constraint solver में इसे इस तरह व्यक्त किया जा सकता है 
      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;

उदाहरण 3: histogram में सबसे बड़ा rectangle area

  • 'हर bar की height दी गई histogram में, बनाए जा सकने वाले सबसे बड़े rectangle का area निकालो'
    • पारंपरिक रूप से जटिल algorithm और कई states को manage करना पड़ता है
    • सिर्फ़ constraints के साथ समाधान को संक्षेप में लिखा जा सकता है 
      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)"]

क्या constraint solver approach बेहतर है?

  • इंटरव्यू जैसी स्थिति में time complexity वगैरह के सवालों के सामने इसकी कमज़ोरी होती है

    • constraint solver का execution time अनुमान लगाना कठिन होता है, और यह आम तौर पर custom optimized algorithm से धीमा होता है
    • लेकिन गलत तरीके से लिखे गए निम्न-गुणवत्ता वाले algorithm से यह बेहतर है, और ज़्यादातर programmers के लिए हर बार optimal solution खुद लिखना आसान नहीं होता

  • वास्तविक ताकत नए constraints जोड़ने में लचीलापन है

    • उदाहरण के लिए, stock वाले उदाहरण में यदि एक बार की जगह कई बार खरीदने-बेचने की शर्त जोड़ दी जाए, तो algorithm की जटिलता तेज़ी से बढ़ जाती है
    • MiniZinc के constraint model में बहुत छोटे code बदलाव के साथ कहीं अधिक जटिल requirements को संभाला जा सकता है 
      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)"];

  • ऑनलाइन constraint problem के उदाहरण अक्सर Sudoku जैसे puzzles पर केंद्रित होते हैं, लेकिन वास्तव में इन्हें business logic या optimization requirements वाली समस्याओं में अधिक रोचक और व्यावहारिक रूप से इस्तेमाल किया जा सकता है

    • उदाहरण के लिए, symmetry breaking जैसी उन्नत optimization techniques लागू करने की संभावना भी अधिक होती है

समापन और संदर्भ

  • यह लेख लेखक के साप्ताहिक newsletter से लिया गया है, जो software history, formal methods, नई technologies, software engineering theory को कवर करता है
  • रुचि हो तो subscribe करें या लेखक की main website देखें
  • लेखक की नई पुस्तक "Logic for Programmers" भी प्रकाशित हो रही है

संबंधित पढ़ाई

अभी कोई टिप्पणी नहीं है.

अभी कोई टिप्पणी नहीं है.