Greedy — local সিদ্ধান্তে global জয়, কখন সম্ভব

import heapq
import itertools
import random


# ---------- part ১: interval scheduling greedy vs brute force ----------

def max_activities_greedy(intervals):
    chosen, last_end = [], float('-inf')
    for s, f in sorted(intervals, key=lambda iv: iv[1]):   # earliest finish
        if s >= last_end:
            chosen.append((s, f))
            last_end = f
    return len(chosen)


def max_activities_brute(intervals):
    best = 0
    n = len(intervals)
    for mask in range(1 << n):
        picked = [intervals[i] for i in range(n) if mask >> i & 1]
        picked.sort()
        ok = all(picked[i][1] <= picked[i + 1][0]
                 for i in range(len(picked) - 1))
        if ok:
            best = max(best, len(picked))
    return best


rng = random.Random(42)
mismatch = 0
trials = 1000
for t in range(trials):
    n = rng.randint(2, 12)
    starts = sorted(rng.sample(range(30), n))
    intervals = [(s, s + rng.randint(1, 8)) for s in starts]
    g, b = max_activities_greedy(intervals), max_activities_brute(intervals)
    assert g <= b, 'greedy beat optimum?! impossible'
    if g != b:
        mismatch += 1
print(f'interval scheduling: {trials} trials, mismatches={mismatch} '
      f'(proof বলে 0 হতেই হবে)')


# ---------- part ২: huffman on bangla text ----------

def huffman_codes(text):
    freq = {}
    for ch in text:
        freq[ch] = freq.get(ch, 0) + 1
    if len(freq) == 1:                       # degenerate: একটাই symbol
        return {next(iter(freq)): '0'}, freq
    heap = [[f, i, [ch]] for i, (ch, f) in enumerate(sorted(freq.items()))]
    heapq.heapify(heap)
    tie = len(heap)
    codes = {ch: '' for ch in freq}
    while len(heap) > 1:
        f1, _, syms1 = heapq.heappop(heap)
        f2, _, syms2 = heapq.heappop(heap)
        for ch in syms1:
            codes[ch] = '0' + codes[ch]
        for ch in syms2:
            codes[ch] = '1' + codes[ch]
        tie += 1
        heapq.heappush(heap, [f1 + f2, tie, syms1 + syms2])
    return codes, freq


sample = (
    'বাংলা ভাষার জন্মকথা প্রাচীন ভারতীয় আর্যভাষার সঙ্গে সম্পর্কিত। '
    'মৌর্যযুগে প্রাচীন বাংলার জনগণের ভাষা ছিল প্রাকৃত। '
    'বাংলা ভাষার বিকাশে প্রাকৃত ও অপভ্রংশের গুরুত্বপূর্ণ ভূমিকা ছিল। '
) * 20

codes, freq = huffman_codes(sample)
bits_huffman = sum(freq[c] * len(codes[c]) for c in freq)
n_symbols = len(freq)
bits_fixed = len(sample) * 16                      # UTF-16 baseline
bits_ascii_like = len(sample) * 8                  # 8-bit fixed baseline

top = sorted(freq.items(), key=lambda kv: -kv[1])[:5]
print(f'\nsample: {len(sample)} chars, {n_symbols} unique')
for ch, f in top:
    print(f'  {ch!r} freq={f:<4} code={codes[ch]:<12} ({f*len(codes[ch])} bits)')
print(f'huffman total : {bits_huffman:>9,} bits  '
      f'({bits_huffman/len(sample):.2f} bits/char)')
print(f'8-bit fixed   : {bits_ascii_like:>9,} bits  '
      f'ratio {bits_ascii_like/bits_huffman:.2f}x')
print(f'UTF-16 fixed  : {bits_fixed:>9,} bits  '
      f'ratio {bits_fixed/bits_huffman:.2f}x')

# entropy comparison — theoretical floor
import math
H = -sum((f / len(sample)) * math.log2(f / len(sample)) for f in freq.values())
print(f'entropy floor : {H:.2f} bits/char (Huffman ≤ H+1 গ্যারান্টি)')

সাধারণ ফলাফল:

interval scheduling: 1000 trials, mismatches=0 (proof বলে 0 হতেই হবে)

sample: 3540 chars, 36 unique
  ' ' freq=480  code=101          (1440 bits)
  'া' freq=440  code=011          (1320 bits)
  'র' freq=340  code=001          (1020 bits)
  '্' freq=260  code=1100         (1040 bits)
  'ভ' freq=140  code=11100        (700 bits)
huffman total :    16,220 bits  (4.58 bits/char)
8-bit fixed   :    28,320 bits  ratio 1.75x
UTF-16 fixed  :    56,640 bits  ratio 3.49x
entropy floor : 4.55 bits/char (Huffman ≤ H+1 গ্যারান্টি)

পড়ার বিষয়:

১. ×১০০০ mismatch=0 — প্রমাণ empirical নয়, কিন্তু brute-force cross-check implementation bug ধরার সস্তা safety net; production optimization-এও এই pattern ব্যবহার হয় (property-based testing)।

২. Huffman 4.58 bits/char — 8-bit baseline-এ ~৪৩% savings, UTF-16-এ ~৭১%; আর entropy floor-এর মাত্র 0.03 ওপরে — প্রমাণিত near-optimality-র হাতে-কলমে প্রমাণ।

৩. Frequent ‘া’/’ ’ 3-bit, rare ‘ভ’ 5-bit — frequency-depth inversion চোখে দেখা যাচ্ছে।