Banyak Soal LeetCode Sulit Sebenarnya Adalah Masalah Kendala yang Mudah

• Bahkan soal LeetCode yang sulit pun bisa diselesaikan jauh lebih mudah dengan memakai constraint solver
• Alih-alih dynamic programming yang kompleks atau algoritme buatan sendiri, kita bisa memanfaatkan constraint solver seperti MiniZinc untuk menyelesaikan masalah optimasi matematis dengan sederhana
• Bahasa pemrograman tradisional sulit mengekspresikan masalah optimasi matematis semacam ini, sehingga pendekatan berbasis kendala menjadi unggul
• Bahkan ketika muncul kasus pengecualian atau kendala tambahan, perubahan model pada constraint solver tetap minimal
• Kompleksitas runtime memang bisa lebih lambat daripada algoritme optimal yang ditulis langsung, tetapi dari sisi fleksibilitas dan produktivitas pengembangan pendekatan ini punya banyak keunggulan

---

Soal LeetCode yang Diselesaikan dengan Constraint Solver

Memilih alat yang tepat

• Penulis mendapat soal 'coin change problem' pada wawancara kerja pertamanya setelah lulus kuliah

  • Diberikan denominasi koin, tujuannya adalah mencari jumlah koin minimum yang diperlukan untuk memberikan kembalian sejumlah tertentu
  • Penulis memakai algoritme greedy sederhana, tetapi itu tidak menjamin solusi optimal untuk semua kasus
  • Jawaban yang benar adalah dynamic programming, tetapi karena gagal mengimplementasikannya, wawancara pun gagal

• Namun, tanpa mengimplementasikan algoritme sendiri, masalah ini bisa diselesaikan dengan sangat mudah memakai constraint solver seperti MiniZinc

  • Contoh kode:

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

  • Contohnya bisa langsung dijalankan secara online di MiniZinc

  • Solver akan menemukan solusi optimal secara bertahap

Beragam masalah optimasi/kepuasan

• Masalah optimasi matematis yang sering muncul di LeetCode dan sejenisnya—dengan fungsi objektif untuk dimaksimalkan/diminimalkan serta berbagai kendala—
  sulit diselesaikan dalam bahasa pemrograman biasa karena perlu implementasi level rendah, tetapi sangat cocok untuk constraint solver
• Misalnya, berbagai jenis masalah berikut termasuk dalam kategori ini

Contoh 1: masalah keuntungan saham maksimum

• 'Dari data harga saham dalam bentuk daftar, cari keuntungan maksimum yang bisa diperoleh dengan membeli sekali lalu menjual pada waktu sesudahnya'
  • Secara tradisional memerlukan brute force O(n²) atau algoritme optimal O(n)
  • Di MiniZinc, ini bisa didefinisikan secara sederhana sebagai masalah kendala berikut

    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;
    

Contoh 2: membuat 0 dengan penjumlahan/pengurangan bilangan tertentu (masalah kepuasan)

• 'Bisakah memilih tiga angka dari daftar, lalu menambah atau menguranginya sehingga hasilnya menjadi 0?'
  • Yang dicari bukan nilai optimal, melainkan sekadar solusi yang memenuhi
  • Pada constraint solver, ini bisa dinyatakan sebagai berikut

    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;
    

Contoh 3: luas persegi panjang maksimum dalam histogram

• 'Dari histogram yang tinggi tiap batangnya diberikan, carilah luas persegi panjang terbesar yang bisa dibentuk'
  • Secara tradisional perlu algoritme yang rumit dan banyak pengelolaan state
  • Dengan kendala saja, solusinya bisa dijelaskan secara ringkas

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

Apakah pendekatan constraint solver memang lebih baik?

• Dalam konteks wawancara, pendekatan ini punya kelemahan saat ditanya soal kompleksitas waktu

  • Runtime constraint solver sulit diprediksi, dan umumnya lebih lambat daripada algoritme optimal yang dirancang khusus
  • Tetapi ini tetap lebih baik daripada algoritme berkualitas rendah yang salah implementasi, dan kebanyakan programmer juga tidak mudah menulis solusi optimal dari nol setiap saat

• Kekuatan sebenarnya adalah fleksibilitas saat menambahkan kendala baru

  • Misalnya, pada contoh saham, jika diubah dari sekali transaksi menjadi beberapa kali beli-jual, kompleksitas algoritmenya langsung meningkat tajam
  • Dalam model kendala MiniZinc, kebutuhan yang jauh lebih kompleks bisa diakomodasi hanya dengan sedikit perubahan kode

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

• Contoh masalah kendala yang beredar online memang banyak berfokus pada puzzle seperti Sudoku, tetapi sebenarnya pendekatan ini lebih menarik dan praktis untuk masalah dengan business logic atau kebutuhan optimasi nyata

  • Misalnya, ada juga peluang besar untuk menerapkan teknik optimasi tingkat lanjut seperti symmetry breaking

Penutup dan referensi

• Tulisan ini berasal dari newsletter mingguan penulis yang membahas sejarah perangkat lunak, metode formal, teknologi baru, dan teori rekayasa perangkat lunak
• Jika tertarik, Anda bisa berlangganan atau melihat situs utama penulis
• Buku baru penulis, "Logic for Programmers", juga sedang dirilis