โจทย์ LeetCode ยากหลายข้อ จริง ๆ แล้วเป็นปัญหาเงื่อนไขที่ง่าย

 (buttondown.com)
6 คะแนน โดย GN⁺ 2025-09-13 | ยังไม่มีความคิดเห็น | แชร์ทาง WhatsApp
  • แม้แต่ โจทย์ยากของ LeetCode ก็แก้ได้ง่ายขึ้นมากเมื่อใช้ constraint solver
  • แทนที่จะใช้ dynamic programming ที่ซับซ้อนหรืออัลกอริทึมที่เขียนเอง ก็สามารถใช้ constraint solver อย่าง MiniZinc เพื่อแก้ปัญหา optimization ทางคณิตศาสตร์ได้อย่างเรียบง่าย
  • ภาษาโปรแกรมแบบดั้งเดิมแสดงปัญหา optimization ทางคณิตศาสตร์ลักษณะนี้ได้ยาก จึงเป็นจุดแข็งของ แนวทางแบบอิงข้อจำกัด
  • ต่อให้มี กรณียกเว้นหรือเงื่อนไขเพิ่มเติม ก็แทบไม่ต้องเปลี่ยนโมเดลใน constraint solver มากนัก
  • แม้ความซับซ้อนด้าน runtime อาจช้ากว่าอัลกอริทึมที่ปรับแต่งเอง แต่ก็มีข้อดีมากในด้าน ความยืดหยุ่นและประสิทธิภาพการพัฒนา

โจทย์ LeetCode ที่แก้ด้วย constraint solver

การเลือกเครื่องมือที่เหมาะสม

  • ผู้เขียนเคยเจอโจทย์ “ปัญหาเงินทอนเหรียญ” ในการสัมภาษณ์ครั้งแรกหลังเรียนจบมหาวิทยาลัย

    • เมื่อกำหนดมูลค่าเหรียญมาให้ ต้องหาว่าจำนวนเหรียญ น้อยที่สุด ที่ใช้ทอนเงินตามจำนวนที่กำหนดคือเท่าใด
    • ตอนนั้นใช้ greedy algorithm แบบง่าย ๆ แต่ไม่สามารถรับประกันคำตอบที่ดีที่สุดได้ในทุกกรณี
    • คำตอบที่ถูกต้องคือ dynamic programming แต่ผู้เขียนทำ implementation ไม่ได้ จึงสัมภาษณ์ไม่ผ่าน

  • แต่ถ้าไม่เขียนอัลกอริทึมเองโดยตรง แล้วใช้ constraint solver อย่าง MiniZinc ก็แก้ได้ง่ายมาก

    • โค้ดตัวอย่าง:

      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 ที่หลากหลาย

  • ปัญหา optimization ทางคณิตศาสตร์ ที่พบบ่อยใน LeetCode และที่อื่น ๆ (มีทั้งการ maximize/minimize objective function และมีหลายข้อจำกัด)
    มักยากเมื่อแก้ด้วยภาษาโปรแกรมทั่วไปเพราะต้องทำ implementation ระดับล่าง แต่กลับเหมาะกับ constraint solver มาก
  • ตัวอย่างเช่น ปัญหาหลายลักษณะด้านล่างนี้เข้าข่ายดังกล่าว

ตัวอย่าง 1: ปัญหาหากำไรจากหุ้นสูงสุด

  • “จากรายการราคาหุ้นที่ให้มา จงหาว่าหากซื้อหนึ่งครั้งแล้วขายในภายหลังหนึ่งครั้ง จะได้ กำไรสูงสุด เท่าใด”
    • แบบดั้งเดิมต้องใช้ brute force O(n²) หรืออัลกอริทึมที่เหมาะที่สุด O(n)
    • ใน MiniZinc สามารถนิยามเป็นปัญหาเงื่อนไขได้อย่างง่ายดังนี้ 
      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)

  • “สามารถเลือกตัวเลขสามตัวจากลิสต์ แล้วบวกหรือลบให้ผลรวมเป็น 0 ได้หรือไม่?”
    • ไม่ได้ต้องหาค่าที่ดีที่สุด แต่ต้องการแค่ คำตอบที่เป็นไปได้
    • ใน 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: พื้นที่สี่เหลี่ยมผืนผ้าสูงสุดในฮิสโตแกรม

  • “จากฮิสโตแกรมที่กำหนดความสูงของแต่ละแท่งมา จงหาว่า พื้นที่ของสี่เหลี่ยมผืนผ้าที่ใหญ่ที่สุด ที่สร้างได้มีค่าเท่าใด”
    • แบบดั้งเดิมต้องใช้อัลกอริทึมที่ซับซ้อนและต้องจัดการหลายสถานะ
    • แต่สามารถอธิบายวิธีแก้ด้วยข้อจำกัดอย่างกระชับได้ 
      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 ดีกว่าหรือไม่?

  • ในสถานการณ์สัมภาษณ์งาน มันยังมีจุดอ่อนในแง่คำถามเรื่อง time complexity

    • runtime ของ constraint solver คาดเดาได้ยาก และโดยทั่วไปมักช้ากว่าอัลกอริทึมที่ออกแบบเฉพาะทางอย่างเหมาะสม
    • แต่ก็ยังดีกว่าอัลกอริทึมคุณภาพต่ำที่เขียนผิดเอง และสำหรับโปรแกรมเมอร์ส่วนใหญ่ การจะเขียนวิธีที่ดีที่สุดขึ้นมาใหม่ทุกครั้งก็ไม่ใช่เรื่องง่าย

  • จุดแข็งที่แท้จริงคือความยืดหยุ่นเมื่อเพิ่มข้อจำกัดใหม่

    • ตัวอย่างเช่น ในโจทย์หุ้น ถ้าเปลี่ยนจากซื้อขายครั้งเดียวเป็นหลายครั้ง ความซับซ้อนของอัลกอริทึมจะเพิ่มขึ้นอย่างมาก
    • แต่ในโมเดลข้อจำกัดของ MiniZinc สามารถรองรับความต้องการที่ซับซ้อนขึ้นมากได้ด้วยการแก้โค้ดเพียงเล็กน้อย 
      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 บนออนไลน์มักเน้นพัซเซิลอย่าง Sudoku แต่ในความเป็นจริงสามารถนำไปใช้กับ business logic หรือข้อกำหนดด้าน optimization ได้อย่างน่าสนใจและเป็นประโยชน์มากกว่า

    • เช่น ยังมีโอกาสใช้เทคนิค optimization ขั้นสูงอย่าง symmetry breaking ได้ด้วย

สรุปและข้อมูลอ้างอิง

  • บทความนี้มาจากจดหมายข่าวรายสัปดาห์ของผู้เขียน ซึ่งพูดถึง ประวัติศาสตร์ซอฟต์แวร์, formal methods, เทคโนโลยีใหม่ และทฤษฎีวิศวกรรมซอฟต์แวร์
  • หากสนใจ สามารถดู สมัครรับข้อมูล หรือ เว็บไซต์หลัก ของผู้เขียนได้
  • หนังสือใหม่ของผู้เขียน "Logic for Programmers" ก็กำลังวางจำหน่ายอยู่

บทความที่เกี่ยวข้อง

ยังไม่มีความคิดเห็น

ยังไม่มีความคิดเห็น