# Guided challenge — পণ্যের catalogue ও দ্রুত query

আপনার দোকানের product list বারবার price দিয়ে খুঁজতে হয়। একই data-তে তিনটি sort-এর কাজের সংখ্যা তুলনা করুন; তারপর sorted price-এর উপর binary search চালিয়ে query-র উত্তর দিন। এটি নিজের শেখার project, কোনো coding platform বা Microsoft assignment-এর অনুলিপি নয়।

## আগে কী পড়বেন

1. [Array ও index](../02-arrays-and-strings/concept.md): কোন item কোথায় আছে বুঝুন।
2. [Bubble sort](../sorting-searching/problems/001-bubble-sort.md): pass-এর invariant লিখুন।
3. [Merge sort](../sorting-searching/problems/002-merge-sort.md) ও [quicksort](../sorting-searching/problems/003-quicksort.md): ভাগ করা ও sorted অংশ জোড়া দেওয়া আলাদা কাজ।
4. [Boundary binary search](../sorting-searching/problems/004-binary-search.md): lower/upper bound-এর পার্থক্য।

**Course মিল:** [Microsoft · M2](../practice-map.md#course-map)-এর topic। Complexity তুলনা M5-এর performance-analysis অনুশীলনেও সাহায্য করে; এখানে Copilot বা .NET lab অনুকরণ করা হয়নি।

## নির্দিষ্ট সমস্যা

`products`-এ `(id, price)` জোড়া, `queries`-এ খোঁজার price, আর একটি `budget` পাবেন। ফেরত দিতে হবে:

- Price অনুযায়ী sorted product; সমান price-তে input-এর আগের ক্রম থাকবে।
- প্রতিটি query-র জন্য সেই price-এর সব product ID। Query আবার এলেও আবার output দিন।
- `price <= budget` এমন সব ID, sorted ক্রমে।
- Bubble, merge ও quicksort-এর **key comparison** সংখ্যা। এটি runtime benchmark নয়।

**সীমা:** `0 <= products-এর সংখ্যা <= 200`; ID nonempty ও unique string; price, query ও budget nonnegative integer (Boolean নয়)। Empty products/queries গ্রহণযোগ্য। মূল input বদলানো যাবে না। বেশি বড় input-এ bubble চালানো এই শিক্ষামূলক lab-এর লক্ষ্য নয়।

## ছোট input থেকে পুরো ফল

```python
products = [("A", 40), ("B", 20), ("C", 40), ("D", 10)]
queries = [40, 25]
budget = 20
```

```dsa
kind: array
title: Price সাজলেও সমান price-এর ক্রম থাকে
steps:
  - label: Input-এর price
    values: [40, 20, 40, 10]
    pointers: {A: 0, B: 1, C: 2, D: 3}
  - label: Sorted price
    values: [10, 20, 40, 40]
    active: [2, 3]
    pointers: {D: 0, B: 1, A: 2, C: 3}
    note: A ও C দুটিই 40; A আগে ছিল, তাই এখনও আগে।
```

| অংশ | ফল |
| --- | --- |
| ordered | `[("D",10),("B",20),("A",40),("C",40)]` |
| price 40 | `["A","C"]`, কারণ boundary `[2,4)` |
| price 25 | `[]`, কারণ দুই boundary-ই 2 |
| budget 20 | `["D","B"]`, কারণ upper bound 2 |

Comparison counter-এ algorithm অনুযায়ী ভিন্ন সংখ্যা আসবে। নিচের tests-এ sorted input-এর bubble pass-এ ঠিক `n−1` comparison হয় কি না আলাদা করে যাচাই করা আছে।

## Milestone ১ — সরল baseline লিখুন

`bubble_sort` লিখুন। প্রতি pass শেষে ডানের স্থির অংশে সবচেয়ে বড়গুলো থাকবে।

**Hint:** এক pass-এ swap হয়নি মানে পুরো বর্তমান অংশ sorted। **Checkpoint:** reverse input, already-sorted input ও সব price সমান—তিনটিই পরীক্ষা করুন। সমান price-তে swap করলে স্থির ক্রম নষ্ট হতে পারে।

## Milestone ২ — কম comparison-এর পদ্ধতি

Bottom-up `merge_sort`-এ width 1 → 2 → 4 করে এগোন। প্রতিটি merge-এ result-এর শেষ item সবচেয়ে ছোট অব্যবহৃত front থেকে এসেছে—এটাই invariant।

Three-way `quick_sort`-এ ছোট, সমান, বড় list বানান। Reference explicit task stack ব্যবহার করে; খারাপ partition হলেও Python recursion limit-এ আটকে যায় না।

**Checkpoint:** তিনটি result-ই Python-এর `sorted(products, key=lambda p: p[1])`-এর সঙ্গে মেলে। `sorted` test oracle; নিজের implementation-এর বদলে এটি ব্যবহার করবেন না। একই input অপরিবর্তিত থাকবে।

## Milestone ৩ — exact price query

Sorted prices-এর `lower_bound(target)` এবং `upper_bound(target)` বের করুন। Result slice `[left:right]`-এ সব match; আলাদা করে linear scan করে শুরু খুঁজবেন না।

**Invariant:** lower bound-এর বাঁয়ে সব মান target-এর চেয়ে ছোট। **Checkpoint:** `[1,2,2,2,5]`-তে target 2 দিলে `(1,4)`, 3 দিলে `(4,4)`, empty list-এ `(0,0)`।

## Milestone ৪ — budget ও পুরো report

Budget-এর upper bound পর্যন্ত prefix-ই affordable products। আগের তিন stage জুড়ে `catalog_report` বানান।

**Checkpoint:** worked input-এর report table মেলে, repeated query হারায় না, invalid ID/price-এ `ValueError` হয়। শেষে sorting comparison report থেকে কোন কাজ বারবার হচ্ছে তা ব্যাখ্যা করুন।

## Reference solution ও unit test

[সম্পূর্ণ runnable solution](../practice/sorting_lab.py) · [আটটি test group](../practice/test_sorting_lab.py)

Repository root থেকে:

```bash
python -m unittest discover -s practice -p "test_sorting_lab.py" -v
```

```python
from practice.sorting_lab import catalog_report

result = catalog_report([("A", 40), ("B", 20), ("C", 40), ("D", 10)], [40, 25], 20)
assert result["affordable"] == ["D", "B"]
assert result["matches"][0]["ids"] == ["A", "C"]
```

নিজে করতে চাইলে solution file-এর function body লিখে একই tests চালান। Reference code আগে পড়ে ফেললে নতুন input নিজে তৈরি করে expected output হাতে লিখুন।

## খরচ, coverage ও বাকি অনুশীলন

| অংশ | কী শিখছেন | এই challenge-এ নেই |
| --- | --- | --- |
| Sort তুলনা | stability, invariant, comparison, early exit | external sorting, counting/radix sort |
| Quicksort | three-way partition, explicit stack | in-place partition-এর memory guarantee |
| Boundary query | duplicate, absent key, half-open interval | binary search on a general feasibility predicate |
| Integration | sort একবার, query বারবার, validation | concurrent database index বা database engine |

এই lab তিনটি sort-ই চালায়, তাই মোট worst time O(n² + q log n + K), যেখানে K হলো সব query-তে ফেরত দেওয়া ID-এর মোট সংখ্যা। শুধু merge sort রেখে production-style variant করলে O(n log n + q log n + K)। Input বাদে sorting scratch O(n), returned query data O(q + K)।

একটি short counterexample লিখুন: unsorted price-এ binary search কেন ভুল হতে পারে? তারপর [পুরো problem map](../practice-map.md#section-sorting)-এ ফিরে remaining exercises করুন।