ক্যাপস্টোন — বাজারঘরের সমস্যায় discrete math

from itertools import product, combinations
imp = lambda a, b: (not a) or b
# f ঠান্ডা পণ্য, e এক্সপ্রেস, b বাইক, v ভ্যান, n রাতের স্লট
R = {"R1": lambda f, e, b, v, n: imp(f, v),
     "R2": lambda f, e, b, v, n: imp(e, b),
     "R3": lambda f, e, b, v, n: b or v,
     "R4": lambda f, e, b, v, n: not (b and v),
     "R5": lambda f, e, b, v, n: imp(n, not v)}
F = {"F1": lambda f, e, b, v, n: f,       # অর্ডারটি ঠান্ডা পণ্যের
     "F2": lambda f, e, b, v, n: e}       # আর এক্সপ্রেস
rows = list(product([True, False], repeat=5))
def models(rules):
    return [r for r in rows if all(g(*r) for g in rules)]

print("R1-R5 সত্য করে", len(models(R.values())), "/ 32 সারি")
def entails(goal):                        # R ⊨ goal ⇔ R ∧ ¬goal-এর model নেই
    return all(goal(*r) for r in models(R.values()))
print("R ⊨ f -> ¬n ?", entails(lambda f, e, b, v, n: imp(f, not n)))
print("R ⊨ e -> ¬v ?", entails(lambda f, e, b, v, n: imp(e, not v)))
print("R ⊨ n -> e  ?", entails(lambda f, e, b, v, n: imp(n, e)))

allr = {**R, **F}
print("ঠান্ডা + এক্সপ্রেস অর্ডারে model:", len(models(allr.values())))
for k in range(1, len(allr) + 1):
    cores = [c for c in combinations(allr, k) if not models([allr[x] for x in c])]
    if cores:
        print("ক্ষুদ্রতম বিরোধ:", cores)
        break

import random
random.seed(78)

def run(S0, events, slack=0):              # slack > 0 মানে ইচ্ছাকৃত bug
    stock, got, sent, rej = S0, 0, 0, 0
    for i, (kind, q) in enumerate(events):
        assert stock == S0 + got - sent and stock >= 0, (i, stock)   # I
        if kind == "in":                   # মাল এল
            stock, got = stock + q, got + q
        elif q <= stock + slack:           # অর্ডার: মজুত থাকলে পাঠানো
            stock, sent = stock - q, sent + q
        else:                              # নইলে ফেরত
            rej += 1
    assert stock == S0 + got - sent and stock >= 0, ("end", stock)   # Q
    return stock, got, sent, rej

days = [[(random.choice(["in", "out", "out"]), random.randint(1, 12))
         for _ in range(60)] for _ in range(2000)]
res = [run(20, d) for d in days]
print("২০০০ দিন x ৬০ ঘটনা: invariant সবখানে টিকেছে")
print("দিন ০: (শেষ মজুত, এল, গেল, ফেরত) =", res[0])
print("সবচেয়ে কম শেষ মজুত:", min(r[0] for r in res))

for k, d in enumerate(days):               # bug: ৫ ইউনিট ধার দেওয়া
    try:
        run(20, d, slack=5)
    except AssertionError as err:
        print("slack=5: দিন", k, "-তে ভাঙল, (ঘটনা, মজুত) =", err)
        break

import random
random.seed(26)
W11 = [7, 6, 5, 4, 3, 2, 1]                # ৬টি অঙ্ক + check, mod 11
W10 = [1, 3, 1, 3, 1, 3, 1]               # তুলনার জন্য: EAN-ধাঁচ, mod 10

def val(ch):
    return 10 if ch == "X" else int(ch)
def valid(code, W, m):
    return sum(w * val(ch) for w, ch in zip(W, code)) % m == 0
def make(p, W, m):                         # p = ৬ অঙ্কের payload
    c = -sum(w * int(x) for w, x in zip(W, p)) % m
    return p + ("X" if c == 10 else str(c))

pay = [f"{random.randrange(10**6):06d}" for _ in range(1000)]
print("নমুনা id:", ["BG" + make(p, W11, 11) for p in pay[:3]])
for W, m in ((W11, 11), (W10, 10)):
    ids = [make(p, W, m) for p in pay]
    alpha = "0123456789X" if m == 11 else "0123456789"
    s1 = m1 = s2 = m2 = 0
    for code in ids:
        for i in range(7):
            for ch in alpha:
                if ch != code[i]:
                    s1 += 1; m1 += valid(code[:i] + ch + code[i+1:], W, m)
            if i < 6 and code[i] != code[i + 1]:    # পাশাপাশি অদলবদল
                t = code[:i] + code[i + 1] + code[i] + code[i + 2:]
                s2 += 1; m2 += valid(t, W, m)
    print(f"mod {m}: একক ভুল {s1}, ফসকেছে {m1} | অদলবদল {s2}, ফসকেছে {m2}")

import hashlib
n, e, d = 3233, 17, 2753                   # খেলনা key: n = 61 · 53 (শুধু শেখার জন্য)

def H(msg):                                # খেলনা hash: SHA-256 mod n
    return int.from_bytes(hashlib.sha256(msg.encode()).digest(), "big") % n

summary = "2026-11-12|orders=137|cod=88|total=245610"
h = H(summary)
s = pow(h, d, n)                           # সই: h^d mod n
print("h =", h, "| s =", s, "| যাচাই s^e ≡ h:", pow(s, e, n) == h)

fake = summary.replace("245610", "254610")
print("এক অঙ্ক বদলানো সারাংশ:", pow(s, e, n) == H(fake))

# দুর্বলতা ১: h মাত্র 3233টি মান নিতে পারে, তাই মিল খোঁজা সহজ
for k in range(1, 10**6):
    forged = f"2026-11-12|orders=137|cod=88|total={k}"
    if H(forged) == h:
        print(k, "নম্বর চেষ্টায় একই h-এর জাল সারাংশ:", forged)
        print("  পুরোনো সই দিয়েই যাচাই:", pow(s, e, n) == H(forged))
        break

# দুর্বলতা ২: ছোট n ভাগ করে d বের করা
p = next(q for q in range(2, n) if n % q == 0)
print("n =", p, "x", n // p, "| d =", pow(e, -1, (p - 1) * (n // p - 1)))

from itertools import product
from math import comb, perm

def formulas(L, D, k):                     # L অক্ষর, D অঙ্ক, দৈর্ঘ্য k
    A = L + D
    return {"মোট": A**k,
            "অন্তত একটি অঙ্ক": A**k - L**k,
            "ঠিক ২টি অঙ্ক": comb(k, 2) * D**2 * L**(k - 2),
            "কোনো চিহ্ন দুবার নয়": perm(A, k),
            "ক্রমহীন (multiset)": comb(A + k - 1, k)}

def brute(letters, digits, k):             # সব কোড বানিয়ে গোনা
    cs = list(product(letters + digits, repeat=k))
    nd = lambda c: sum(ch in digits for ch in c)
    return {"মোট": len(cs),
            "অন্তত একটি অঙ্ক": sum(nd(c) >= 1 for c in cs),
            "ঠিক ২টি অঙ্ক": sum(nd(c) == 2 for c in cs),
            "কোনো চিহ্ন দুবার নয়": sum(len(set(c)) == k for c in cs),
            "ক্রমহীন (multiset)": len({tuple(sorted(c)) for c in cs})}

for letters, digits, k in [("ABC", "23", 4), ("ABCD", "234", 5)]:
    print(letters, digits, k, "→ সূত্র = brute force:",
          brute(letters, digits, k) == formulas(len(letters), len(digits), k))

print("২৪ অক্ষর + ৮ অঙ্ক, দৈর্ঘ্য ৬:")
for name, v in formulas(24, 8, 6).items():
    print(f"  {name}: {v:,}")

from math import exp, sqrt, comb

def p_clash(k, N):                         # 1 − ∏ (1 − i/N), i = 0..k−1
    q = 1.0
    for i in range(k):
        q *= 1 - i / N
    return 1 - q

N = 32 ** 4                                # ৪ চিহ্নের ছোট কোড
print("N =", N)
for k in (100, 500, 1000, 1206, 2000):
    approx = 1 - exp(-k * (k - 1) / (2 * N))
    print(f"k = {k:>4}: সূত্রে {p_clash(k, N):.4f} | আসন্ন {approx:.4f}"
          f" | ওপরের সীমা C(k,2)/N {min(1, comb(k, 2) / N):.4f}")
k50 = next(k for k in range(1, 5000) if p_clash(k, N) >= 0.5)
print("প্রথম k যেখানে ≥ 0.5:", k50, "| 1.1774·√N ≈", round(1.1774 * sqrt(N), 1))

K = 100_000                                # এক বছরের কোড
for L in range(4, 12):
    if comb(K, 2) / 32 ** L <= 0.001:      # union bound: নিশ্চিত সীমা
        print(f"{K:,} কোডে P(মিল) ≤ 0.001 নিশ্চিত: দৈর্ঘ্য {L},",
              f"সীমা {comb(K, 2) / 32 ** L:.6f}, সূত্রে {p_clash(K, 32 ** L):.6f}")
        break

import heapq
E = [("A", "B", 7), ("A", "C", 3), ("B", "C", 3), ("B", "D", 2), ("C", "D", 6),
     ("C", "E", 8), ("D", "E", 4), ("D", "F", 7), ("E", "F", 2)]   # কিমি, কাল্পনিক
W = {frozenset((u, v)): w for u, v, w in E}
adj = {}
for u, v, w in E:
    adj.setdefault(u, []).append((v, w)); adj.setdefault(v, []).append((u, w))
dist, par, pq, done = {"A": 0}, {"A": None}, [(0, "A")], []   # Dijkstra, গুদাম A থেকে
while pq:
    du, u = heapq.heappop(pq)
    if u in done: continue
    done.append(u)
    for v, w in adj[u]:
        if du + w < dist.get(v, float("inf")):
            dist[v], par[v] = du + w, u
            heapq.heappush(pq, (du + w, v))
print("settle-এর ক্রম:", done)
print("দূরত্ব:", dict(sorted(dist.items())))
spt = [(par[v], v) for v in sorted(par) if par[v]]
print("পথের tree:", spt, "| মোট:", sum(W[frozenset(e)] for e in spt), "কিমি")

root = {v: v for v in adj}                                  # Kruskal + union-find
def find(x):
    while root[x] != x: x = root[x]
    return x
mst = []
for u, v, w in sorted(E, key=lambda t: t[2]):
    if find(u) != find(v):
        root[find(u)] = find(v); mst.append((u, v, w))
print("MST:", mst, "| মোট:", sum(w for *_, w in mst), "কিমি")

from itertools import product, combinations
E = ["AB", "AC", "BC", "BD", "CD", "CE", "DE", "DF", "EF"]   # হাবের রাস্তা
V = "ABCDEF"
ok = lambda col: all(col[u] != col[v] for u, v in E)
greedy = {}
for v in V:                                # বর্ণক্রমে greedy
    used = {greedy[u] for u in V if u in greedy and (u + v in E or v + u in E)}
    greedy[v] = min(c for c in range(6) if c not in used)
print("greedy শিফট:", greedy, "| বৈধ:", ok(greedy))
for k in (1, 2, 3):                        # brute force: কত রঙে সম্ভব
    n = sum(ok(dict(zip(V, c))) for c in product(range(k), repeat=6))
    print(f"{k} শিফটে বৈধ বণ্টন: {n}")

can = {"O1": ["R1", "R2"], "O2": ["R1", "R3"], "O3": ["R4", "R5"],
       "O4": ["R4", "R5"], "O5": ["R4"]}   # কোন অর্ডার কোন রাইডার নিতে পারেন
match = {}                                 # রাইডার -> অর্ডার
def augment(o, seen):                      # augmenting path খোঁজা
    for r in can[o]:
        if r not in seen:
            seen.add(r)
            if r not in match or augment(match[r], seen):
                match[r] = o
                return True
    return False
size = sum(augment(o, set()) for o in can)
print("সবচেয়ে বড় matching:", size, dict(sorted(match.items())))
bad = [S for k in range(1, 6) for S in combinations(can, k)
       if len({r for o in S for r in can[o]}) < len(S)]
print("Hall ভাঙে এমন ক্ষুদ্রতম দল:", min(bad, key=len))

import heapq, random
from collections import Counter
from math import log2
random.seed(68)
# D ডেলিভারি হয়েছে, T পথে, P প্যাক হচ্ছে, R ফেরত, C বাতিল (কাল্পনিক লগ)
log = list("D" * 45 + "T" * 25 + "P" * 15 + "R" * 10 + "C" * 5)
random.shuffle(log)
freq = Counter(log)
heap = [(f, i, {s: ""}) for i, (s, f) in enumerate(sorted(freq.items()))]
heapq.heapify(heap)
nxt = len(heap)
while len(heap) > 1:                       # সবচেয়ে হালকা দুটি জোড়া
    f1, _, a = heapq.heappop(heap)
    f2, _, b = heapq.heappop(heap)
    merged = {s: "0" + c for s, c in a.items()} | {s: "1" + c for s, c in b.items()}
    heapq.heappush(heap, (f1 + f2, nxt, merged)); nxt += 1
code = heap[0][2]
print("code:", dict(sorted(code.items(), key=lambda t: len(t[1]))))
bits = "".join(code[s] for s in log)
N = len(log)
H = -sum(f / N * log2(f / N) for f in freq.values())
print(f"bit: Huffman {len(bits)}, fixed 3-bit {3 * N}; গড় {len(bits) / N:.2f}, H = {H:.3f}")
back = {c: s for s, c in code.items()}
def decode(b):                             # prefix code: বাঁ থেকে পড়া
    out, cur = [], ""
    for x in b:
        cur += x
        if cur in back: out.append(back[cur]); cur = ""
    return out
print("ফেরত পড়া নিখুঁত:", decode(bits) == log, "| প্রথম ১২টি:", "".join(log[:12]))

G = ["1110000", "1001100", "0101010", "1101001"]   # Hamming(7,4)-এর সারি
def enc(d4):
    c = 0
    for bit, row in zip(d4, G):
        if bit == "1": c ^= int(row, 2)
    return format(c, "07b")
def dec(r):                                # syndrome = 1 থাকা অবস্থানগুলোর XOR
    s = 0
    for pos, bit in enumerate(r, start=1):
        if bit == "1": s ^= pos
    if s: r = r[:s - 1] + "10"[int(r[s - 1])] + r[s:]
    return r[2] + r[4] + r[5] + r[6]       # data: অবস্থান 3, 5, 6, 7
flip = lambda w, i: w[:i] + "10"[int(w[i])] + w[i + 1:]

blocks = [bits[i:i + 4] for i in range(0, len(bits), 4)]
sent = [enc(b) for b in blocks]
print("data", len(bits), "bit →", len(blocks), "block →", 7 * len(sent), "bit")
rng = random.Random(72)
hit = rng.sample(range(len(sent)), 12)     # ১২টি block-এ একটি করে বিট উল্টানো
got = [flip(w, rng.randrange(7)) if j in hit else w for j, w in enumerate(sent)]
print("১২টি একক ভুল, Hamming শোধরানোর পর লগ নিখুঁত:",
      decode("".join(dec(w) for w in got)) == log)

raw = flip(bits, 40)                       # Hamming ছাড়া একটিমাত্র বিট
out = decode(raw)
print("সুরক্ষা ছাড়া ১টি বিট উল্টালে: চিহ্ন", len(out), "টি, ভুল জায়গায়",
      sum(a != b for a, b in zip(out, log)), "টি")
two = [flip(flip(w, 0), 1) if j == 0 else w for j, w in enumerate(sent)]
print("এক block-এ ২টি ভুল:", decode("".join(dec(w) for w in two)) == log)

import random
W, DIG = [7, 6, 5, 4, 3, 2, 1], "0123456789"
def step(q, ch):                           # q = (অবস্থান, যোগফল mod 11) বা "dead"
    if q == "dead": return "dead"
    i, r = q
    if i == 0: return (1, 0) if ch == "B" else "dead"
    if i == 1: return (2, 0) if ch == "G" else "dead"
    if 2 <= i <= 7 and ch in DIG: return (i + 1, (r + W[i - 2] * int(ch)) % 11)
    if i == 8 and (ch in DIG or ch == "X"):
        return (9, (r + (10 if ch == "X" else int(ch))) % 11)
    return "dead"
def accepts(s):
    q = (0, 0)
    for ch in s: q = step(q, ch)
    return q == (9, 0)                     # শেষ অবস্থান, যোগফল ≡ 0
seen, todo = {(0, 0)}, [(0, 0)]            # পৌঁছানো যায় এমন state গোনা
while todo:
    q = todo.pop()
    for t in {step(q, ch) for ch in "BGXZ" + DIG} - seen:
        seen.add(t); todo.append(t)
print("পৌঁছানো যায় এমন state:", len(seen))
def by_math(s):                            # অঙ্কের হিসাবে একই নিয়ম
    ok = len(s) == 9 and s[:2] == "BG" and s[2:8].isdigit() and s[8] in DIG + "X"
    return ok and sum(w * (10 if c == "X" else int(c)) for w, c in zip(W, s[2:])) % 11 == 0
random.seed(74)
tests = ["BG" + "".join(random.choice(DIG + "X") for _ in range(7)) for _ in range(20000)]
tests += ["BG0472131", "BG04721X", "bg0472131", "BG0472113"]
print("DFA = হিসাব, সব", len(tests), "স্ট্রিংয়ে:", all(accepts(t) == by_math(t) for t in tests))
print("গৃহীত:", sum(map(accepts, tests)), "| শেষ চারটির গৃহীত:", [t for t in tests[-4:] if accepts(t)])

from itertools import product
V = "abcd"                                 # x সত্য = রাইডার x সকালের শিফটে
neg = lambda l: l[1:] if l[0] == "~" else "~" + l
def solve(clauses):
    g = {}
    for a, b in clauses:                   # (a ∨ b): ¬a → b, ¬b → a
        g.setdefault(neg(a), []).append(b); g.setdefault(neg(b), []).append(a)
    def reach(s, t):
        seen, st = {s}, [s]
        while st:
            u = st.pop()
            for w in g.get(u, []):
                if w not in seen: seen.add(w); st.append(w)
        return t in seen
    bad = [x for x in V if reach(x, "~" + x) and reach("~" + x, x)]
    val = lambda l, m: not m[l[1:]] if l[0] == "~" else m[l]
    models = [m for m in (dict(zip(V, t)) for t in product([1, 0], repeat=4))
              if all(val(a, m) or val(b, m) for a, b in clauses)]
    return bad, models

C = [("a", "b"), ("~a", "~c"), ("c", "d"), ("~b", "~d")]
bad, models = solve(C)
print("x আর ¬x একই SCC-তে:", bad, "| model:", len(models), models)
C2 = C + [("~a", "c"), ("a", "d")]         # দুটি নতুন অনুরোধ
bad, models = solve(C2)
print("নতুন অনুরোধসহ: একই SCC-তে", bad, "| model:", len(models))

from z3 import Ints, Bools, Implies, And, Or, Not, Solver, prove, If, get_version_string

print("z3", get_version_string())
S0, got, sent, stock, q = Ints("S0 got sent stock q")
I = And(stock == S0 + got - sent, stock >= 0)

def after(kind_in, slack):
    st2 = If(kind_in, stock + q, If(q <= stock + slack, stock - q, stock))
    got2 = If(kind_in, got + q, got)
    sent2 = If(kind_in, sent, If(q <= stock + slack, sent + q, sent))
    return And(st2 == S0 + got2 - sent2, st2 >= 0)

for slack in (0, 5):
    for kind_in in (True, False):
        print(f"slack={slack} kind_in={kind_in}:", end=" ")
        prove(Implies(And(I, q >= 1), after(kind_in, slack)))

f, e, b, v, n = Bools("f e b v n")
R = [Implies(f, v), Implies(e, b), Or(b, v), Not(And(b, v)), Implies(n, Not(v))]
print("R entails f -> not n:", end=" ")
prove(Implies(And(R), Implies(f, Not(n))))
s = Solver()
for i, r in enumerate(R + [f, e], 1):
    s.assert_and_track(r, f"c{i}")
print(s.check(), "core:", sorted(str(c) for c in s.unsat_core()))