Recursion ও Backtracking — workshop day planner¶
একটি workshop day-তে ঠিক নির্দিষ্ট সংখ্যক মিনিটের session সাজাতে হবে। প্রতিটি session type-এর সীমিত copy আছে। একই topic-এর দুই session পাশাপাশি বসবে না। সব বৈধ plan বের করো, এবং একই state বারবার গণনা না করে মোট plan-এর সংখ্যাও বের করো। এখানে প্রতিটি সিদ্ধান্ত final schedule-এর অংশ।
কোর্স-সংযোগ: recursive problem solving-এর প্রস্তুতি হিসেবে এই lab ব্যবহার করো; memoized count advanced problem-solving/DP-এর সেতু। Screenshot-এর module title থেকে এই নির্দিষ্ট workshop problem-কে official course assignment বলা হচ্ছে না।
১. আগে পড়বে¶
| ক্রম | নোট | কী বুঝতে হবে |
|---|---|---|
| 1 | Recursion ধারণা, call tree-এর চিত্র | base case, call frame, ছোট subproblem |
| 2 | Subsets | decision tree ও branch |
| 3 | Permutations II | identical copy দিয়ে duplicate output কেন হয় |
| 4 | Combination Sum II | সীমিত inventory, remaining target ও pruning |
| 5 | Generate Parentheses | invalid branch পুরো গড়ার আগেই থামানো |
২. সমস্যার চুক্তি¶
plan_workshop(workshops, budget) লিখো। প্রতিটি item (name, duration, copies, topic)। name ও topic খালি নয় এমন string; name unique; 1 ≤ duration ≤ 100, copies ≥ 0; 0 ≤ budget ≤ 100। সর্বোচ্চ 6 type ও সব মিলিয়ে 8 copy রাখা যাবে, যাতে সব answer সত্যিই দেখা যায়।
- Plan-এর duration-এর যোগফল ঠিক budget হবে; কম হলে চলবে না। সব available copy ব্যবহার করতেই হবে না।
- একই topic পাশাপাশি নিষিদ্ধ, নাম আলাদা হলেও। একই name দূরে পুনরাবৃত্তি হতে পারে, যদি copy বাকি থাকে।
- একই type-এর copy-গুলো indistinguishable: A-এর প্রথম ও দ্বিতীয় copy অদলবদল করে নতুন plan হয় না।
- Order গুরুত্বপূর্ণ:
A,BওB,Aআলাদা plan। output-এ name-এর tuple থাকবে, lexicographic order-এ। countহলো বৈধ plan-এর সংখ্যা;plansসেই পূর্ণ list। budget 0 হলে একটিই empty plan:[()], count 1। কোনো plan না থাকলে count 0 ও[]।- invalid duration, duplicate name বা সীমার বাইরে input-এ
ValueError; input inventory বদলানো যাবে না।
হাতে করা উদাহরণ¶
workshops = [
("A", 2, 2, "math"),
("B", 1, 1, "code"),
("C", 3, 1, "code"),
]
plan_workshop(workshops, budget=5)
# {"count": 3, "plans": [("A", "B", "A"), ("A", "C"), ("C", "A")]}
A,B,A-এর duration 2+1+2=5, topic math,code,math। A,A,B-ও 5 মিনিট, কিন্তু পাশাপাশি দুই math হওয়ায় invalid। B,C 4 মিনিট এবং পাশাপাশি code—দুই কারণেই invalid।
flowchart TD
R["বাকি 5; আগের topic নেই"] --> A["A নাও: বাকি 3; math"]
R --> B["B নাও: বাকি 4; code"]
R --> C["C নাও: বাকি 2; code"]
A --> AB["B নাও: বাকি 2; code"]
AB --> ABA["A নাও: A,B,A ✓"]
A --> AC["C নাও: A,C ✓"]
B --> BA["A নাও: বাকি 2; math"]
BA --> X["বাকি A-ও math; C সময়ের চেয়ে বড় → থামো"]
C --> CA["A নাও: C,A ✓"]এই চিত্রে বৈধ প্রথম তিনটি branch-ই দেখানো হয়েছে। প্রত্যেক node-এ একই নিয়মে পরের available type বেছে নিতে হবে।
৩. চারটি guided milestone¶
ধাপ A — state ঠিক করো¶
Name অনুযায়ী workshop sort করো। প্রতিটি type-এর remaining copy counts[i]-তে রাখো। recursion state হবে (remaining_minutes, counts, previous_topic); সঙ্গে output তৈরির জন্য path থাকবে।
কেন এই state: ভবিষ্যতে কোন session নেওয়া যাবে তা remaining time, inventory এবং শেষ topic-এর ওপর নির্ভর করে। পুরো পুরনো path দরকার হয় না। কিন্তু answer লেখার জন্য path লাগবে।
Checkpoint: sample-এর শুরুতে counts [2,1,1]। A নেওয়ার পরে [1,1,1], remaining 3, previous topic math। name বা topic একই জিনিস নয়—এটি স্পষ্ট করে লেখো।
ধাপ B — choose, recurse, undo¶
enumerate_plans(workshops, budget) লিখো। প্রতিটি type দেখো। copy নেই, duration remaining-এর চেয়ে বড়, অথবা topic previous topic-এর সমান হলে skip। অন্যথায় count কমাও, name path-এ append করো, recursive call করো; ফিরে এসে path pop এবং count restore করো।
counts[index] -= 1
path.append(name)
search(remaining - duration, topic)
path.pop()
counts[index] += 1
Invariant: প্রতিটি call-এর শুরুতে path বৈধ এবং counts ঠিক তার পরে বাকি থাকা inventory। call থেকে ফেরার পরে parent-এর state সম্পূর্ণ আগের অবস্থায় থাকতে হবে।
Base case: remaining 0 হলে tuple(path) answer-এ যোগ করে return। Positive duration থাকার কারণে পরে আর কিছু যোগ করলে budget ছাড়িয়ে যাবে। path list-টিই append করলে পরের pop-এ saved answer বদলে যাবে।
Checkpoint: sample-এর তিন plan ছাড়া আর কিছু থাকবে না। A-এর দুই copy-কে আলাদা index দিয়ে branch করলে A,B,A duplicate হতে পারে; type-এর count দিয়ে কাজ করলে তা হয় না।
ধাপ C — প্রমাণযোগ্য pruning¶
বাকি সব copy-এর মোট duration বের করো। সেটি remaining-এর চেয়ে ছোট হলে branch বন্ধ করো; সব নিলেও budget ভরবে না। এই পরীক্ষা একটি necessary condition, sufficient নয়: সময় যথেষ্ট থাকলেও topic rule-এর কারণে plan অসম্ভব হতে পারে।
Invariant: pruning কোনো বৈধ answer বাদ দেয় না। Hint: “এই branch দেখতে খারাপ লাগছে” কারণ নয়; কেন অসম্ভব তার যুক্তি দিতে হবে।
Checkpoint: শুধু A:2-এর একটি copy, budget 3 হলে root-এই count 0। একই topic-এর A:1,B:1 ও budget 2-তে সময় যথেষ্ট, কিন্তু recursion শেষে কোনো answer নেই।
ধাপ D — একই state একবার গুনে রাখো¶
count_plans(workshops, budget) আলাদাভাবে লিখো। এবার path list লাগবে না। base case remaining 0-তে 1; invalid/no-choice state-এ 0; সব বৈধ child-এর count যোগ করো। state-এর counts-কে immutable tuple করে memoization key বানাও।
Invariant: cached value হলো ওই state থেকে তৈরি করা সম্ভব suffix plan-এর সংখ্যা। Key থেকে previous topic বাদ দিলে অন্য branch-এর ভুল answer চলে আসবে। name-এর sequence না রেখেও কেন future একই থাকে, তা নিজের ভাষায় বোঝাও।
Checkpoint: count যেন len(enumerate_plans(...))-এর সমান হয়। final plan_workshop দুটো ফল এক report-এ দেবে। দুইভাবে হিসাব করার উদ্দেশ্য: enumeration বোঝা এবং memoization কী কাজ বাঁচায় তা তুলনা করা।
৪. Unit test ও reference solution¶
Python implementation · Unit tests
১০টি test-এ sample, zero budget, empty inventory, duplicate-copy handling, same-topic rejection, order sensitivity, restore ও invalid input আছে। ৬০টি random ছোট inventory-তে সব labeled-copy permutation brute-force করে duplicate বাদ দিয়ে expected answer বানানো হয়; তারপর পুরো plan list এবং count—দুটিই মেলানো হয়।
Reference-এ enumerate_plans-এর mutable counts এবং count_plans-এর tuple counts তুলনা করো। একটিতে undo জরুরি; অন্যটিতে child state আলাদা বানানো হয়। দুটিই parent state ঠিক রাখে, তবে কৌশল আলাদা।
৫. Coverage ও complexity¶
| ধারণা | এই সমস্যায় কোথায় |
|---|---|
| Base case ও decreasing measure | remaining time কমে; exact budget-এ থামে |
| Backtracking / choose-undo | sequence তৈরি ও inventory restore |
| Multiset ও duplicate avoidance | একই type-এর copy গুনে রাখা |
| Constraint pruning | time, inventory, previous topic |
| Memoized recursion | একই suffix state-এর count পুনরায় না-করা |
| আলাদা অনুশীলন | grid word search, N-Queens diagonal, Sudoku constraints, divide-and-conquer merge sort এই problem-এ নেই |
Type সংখ্যা t, মোট copy N, বৈধ output সংখ্যা P ধরো। Enumeration-এর loose upper bound O(t^(N+1) + PN); বাস্তবে copy/topic/time constraints অনেক branch কমায়। recursion depth O(N); output রাখতে O(PN) memory লাগে। সব answer ফেরাতে হলে output-এর এই খরচ এড়ানো যায় না।
Memoized count-এর জন্য conservative state bound S = (budget+1) × (t+1) × ∏(copies[i]+1)। tuple বানানোসহ Python implementation-এর upper bound সময় O(t²S), cache memory O(tS)। ছোট input-এর সীমা ইচ্ছাকৃত; বড় inventory-র জন্য শুধু count ফেরানোর সংস্করণ বানিয়ে state growth মাপো।