# 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 ধারণা](../06-recursion-and-backtracking/concept.md), [call tree-এর চিত্র](../06-recursion-and-backtracking/visual-explanation.md) | base case, call frame, ছোট subproblem |
| 2 | [Subsets](../06-recursion-and-backtracking/problems/007-subsets.md) | decision tree ও branch |
| 3 | [Permutations II](../06-recursion-and-backtracking/problems/014-permutations-ii.md) | identical copy দিয়ে duplicate output কেন হয় |
| 4 | [Combination Sum II](../06-recursion-and-backtracking/problems/013-combination-sum-ii.md) | সীমিত inventory, remaining target ও pruning |
| 5 | [Generate Parentheses](../06-recursion-and-backtracking/problems/015-generate-parentheses.md) | 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 বদলানো যাবে না।

### হাতে করা উদাহরণ

```python
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।

```mermaid
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 করো।

```python
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](../practice/recursion_lab.py) · [Unit tests](../practice/test_recursion_lab.py)

```bash
python -m unittest discover -s practice -p 'test_recursion_lab.py' -v
```

১০টি 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 মাপো।