{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "k00",
   "metadata": {},
   "source": [
    "# Struktury danych w Pythonie — część 2: zaawansowane\n",
    "\n",
    "*Wersja notatnika: 2026-10-08 · na bazie wersji z 2025-10-11 · przygotowanie: dr inż. Szczepan Górtowski*\n",
    "\n",
    "Ten notatnik rozwija podstawy kolekcji o **praktyczne struktury i idiomy**: stos i kolejka (LIFO/FIFO),\n",
    "`collections.deque`, `heapq` (kolejka priorytetowa), `defaultdict`, `Counter`, `frozenset`, kopie płytkie\n",
    "i głębokie oraz wybór struktury. Na końcu: zajawka grafów i 4 zadania z automatycznymi testami.\n",
    "\n",
    "### Jak korzystać\n",
    "1. Uruchamiaj komórki po kolei: `Ctrl + Enter` albo `Shift + Enter`.\n",
    "2. Przy ramkach **Przewidź, zanim uruchomisz** najpierw zgadnij, potem uruchom, na końcu rozwiń odpowiedź.\n",
    "3. W zadaniach edytuj komórki z `TODO` i uruchom komórkę **Sprawdź**."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k01",
   "metadata": {},
   "source": [
    "## Spis treści\n",
    "1. Złożoność obliczeniowa w skrócie (Big-O) — **nowe:** wykres i szukanie binarne\n",
    "2. Stos (LIFO) i kolejka (FIFO)\n",
    "3. `collections.deque` — kolejka dwustronna i **nowe:** okno kroczące\n",
    "4. `defaultdict` i `Counter` — **nowe:** słowa w „Panu Tadeuszu”\n",
    "5. `heapq` — kolejka priorytetowa — **nowe:** kopiec jako drzewo, max-heap w Pythonie 3.14, remisy\n",
    "6. `frozenset` i haszowalność kluczy\n",
    "7. Kopiowanie: płytkie i głębokie (powtórka)\n",
    "8. Niezmienność: `tuple` jako klucz i `dataclass(frozen=True)`\n",
    "9. **Nowe:** zajawka grafu — najkrótsza droga przez BFS\n",
    "10. Jak wybrać strukturę danych?\n",
    "11. Zadania 4.0–4.3"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k02",
   "metadata": {},
   "source": [
    "## 1) Złożoność obliczeniowa w skrócie (Big-O)\n",
    "\n",
    "- **O(1)** — stały czas: element listy po indeksie, wartość ze słownika po kluczu (średnio).\n",
    "- **O(log n)** — logarytmicznie: szukanie binarne w posortowanej liście.\n",
    "- **O(n)** — liniowo: przejście po liście, szukanie element po elemencie.\n",
    "- **O(n log n)** — typowe sortowanie.\n",
    "- **O(n²)** — dwie zagnieżdżone pętle, np. `unikalne()` z zajęć 2.\n",
    "\n",
    "Złożoność mówi, jak rozwiązanie **skaluje się** z rozmiarem danych. Nie zastępuje pomiarów."
   ]
  },
  {
   "cell_type": "code",
   "id": "k03",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import math\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "n = list(range(1, 41))\n",
    "plt.figure(figsize=(8, 4))\n",
    "plt.plot(n, [math.log2(x) for x in n], label=\"O(log n)\")\n",
    "plt.plot(n, n, label=\"O(n)\")\n",
    "plt.plot(n, [x * math.log2(x) for x in n], label=\"O(n log n)\")\n",
    "plt.plot(n, [x * x for x in n], label=\"O(n²)\")\n",
    "plt.ylim(0, 400)\n",
    "plt.xlabel(\"n — rozmiar danych\")\n",
    "plt.ylabel(\"liczba kroków\")\n",
    "plt.legend()\n",
    "plt.title(\"Przy n = 40: log n ≈ 5, n log n ≈ 213, n² = 1600\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k04",
   "metadata": {},
   "source": [
    "### Nowe: szukanie binarne — O(log n) w praktyce\n",
    "\n",
    "W **posortowanej** liście nie musisz sprawdzać elementów po kolei. Patrzysz na środek: szukana liczba jest\n",
    "większa — odrzucasz lewą połowę, mniejsza — prawą. Po każdym kroku zostaje połowa. Dla miliona elementów\n",
    "wystarczy ok. 20 kroków. Moduł `bisect` robi to za ciebie."
   ]
  },
  {
   "cell_type": "code",
   "id": "k05",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import bisect\n",
    "import timeit\n",
    "\n",
    "N = 1_000_000\n",
    "posortowana = list(range(0, 2 * N, 2))      # milion liczb parzystych\n",
    "szukana = 2 * N - 2                          # ostatni element\n",
    "\n",
    "def binarnie(lista, x):\n",
    "    i = bisect.bisect_left(lista, x)\n",
    "    return i < len(lista) and lista[i] == x\n",
    "\n",
    "kroki = math.ceil(math.log2(N))\n",
    "t_in = min(timeit.repeat(lambda: szukana in posortowana,\n",
    "                         number=5, repeat=3)) / 5\n",
    "t_bin = min(timeit.repeat(lambda: binarnie(posortowana, szukana),\n",
    "                          number=10_000, repeat=3)) / 10_000\n",
    "print(f\"kroków szukania binarnego: ok. {kroki}\")\n",
    "print(f\"x in lista: {t_in * 1e6:12.2f} µs\")\n",
    "print(f\"bisect:     {t_bin * 1e6:12.2f} µs\")\n",
    "print(f\"bisect jest ok. {t_in / t_bin:,.0f} razy szybszy\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k06",
   "metadata": {},
   "source": [
    "## 2) Stos (LIFO) i kolejka (FIFO)\n",
    "\n",
    "**Stos (LIFO)**: ostatni wchodzi, pierwszy wychodzi. W Pythonie stos to lista z `append()` i `pop()` na końcu.\n",
    "**Kolejka (FIFO)**: pierwszy wchodzi, pierwszy wychodzi. Do kolejki użyj `collections.deque` (sekcja 3)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k07",
   "metadata": {},
   "source": [
    "> **Przewidź, zanim uruchomisz:** co wypiszą dwa kolejne `pop()`?\n",
    ">\n",
    "> <details><summary>Odpowiedź</summary>\n",
    ">\n",
    "> `3`, potem `2` — zdejmujesz z wierzchu, czyli od ostatnio położonego.\n",
    ">\n",
    "> </details>"
   ]
  },
  {
   "cell_type": "code",
   "id": "k08",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "stack = []\n",
    "stack.append(1)\n",
    "stack.append(2)\n",
    "stack.append(3)\n",
    "print(\"pop ->\", stack.pop())\n",
    "print(\"pop ->\", stack.pop())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k09",
   "metadata": {},
   "source": [
    "## 3) `collections.deque` — kolejka dwustronna\n",
    "\n",
    "`deque` ma szybkie `append`, `appendleft`, `pop` i `popleft` — wszystkie w O(1). Przydaje się w kolejkach,\n",
    "buforach i oknach kroczących."
   ]
  },
  {
   "cell_type": "code",
   "id": "k10",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "\n",
    "q = deque()\n",
    "q.append(\"A\")\n",
    "q.append(\"B\")\n",
    "q.append(\"C\")\n",
    "print(\"popleft ->\", q.popleft())\n",
    "q.appendleft(\"X\")\n",
    "print(\"po appendleft X:\", list(q))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k11",
   "metadata": {},
   "source": [
    "### Nowe: okno kroczące `deque(maxlen=3)`\n",
    "\n",
    "Z parametrem `maxlen` deque pamięta tylko ostatnie elementy: nowy element z prawej wypycha najstarszy z lewej.\n",
    "Tak liczy się średnią kroczącą — np. średnią sprzedaż z ostatnich 7 dni. Przyda się w zadaniu 4.1."
   ]
  },
  {
   "cell_type": "code",
   "id": "k12",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "okno = deque(maxlen=3)\n",
    "for pomiar in [3, 5, 7, 6, 10]:\n",
    "    okno.append(pomiar)\n",
    "    srednia = sum(okno) / len(okno)\n",
    "    print(f\"dodaję {pomiar:>2} → okno {list(okno)}, średnia {srednia:.2f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k13",
   "metadata": {},
   "source": [
    "## 4) `defaultdict` i `Counter` (agregacje i zliczanie)\n",
    "\n",
    "`defaultdict` sam tworzy wartość domyślną dla brakującego klucza. `Counter` liczy elementy i podaje najczęstsze."
   ]
  },
  {
   "cell_type": "code",
   "id": "k14",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "from collections import defaultdict, Counter\n",
    "\n",
    "text = \"ala ma kota ala lubi mleko kot ma ogon\"\n",
    "d = defaultdict(int)\n",
    "for word in text.split():\n",
    "    d[word] += 1\n",
    "print(\"defaultdict:\", dict(d))\n",
    "c = Counter(text.split())\n",
    "print(\"Counter:\", dict(c))\n",
    "print(\"Top-2:\", c.most_common(2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k15",
   "metadata": {},
   "source": [
    "### Nowe: które słowo pada najczęściej w inwokacji „Pana Tadeusza”?\n",
    "\n",
    "Tekst: Adam Mickiewicz, „Pan Tadeusz”, inwokacja (22 wersy) — Wolne Lektury, utwór w domenie publicznej.\n",
    "Zanim policzysz słowa, zamień litery na małe i usuń znaki interpunkcyjne."
   ]
  },
  {
   "cell_type": "code",
   "id": "k16",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "inwokacja = \"\"\"\n",
    "Litwo! Ojczyzno moja! ty jesteś jak zdrowie;\n",
    "Ile cię trzeba cenić, ten tylko się dowie,\n",
    "Kto cię stracił. Dziś piękność twą w całej ozdobie\n",
    "Widzę i opisuję, bo tęsknię po tobie.\n",
    "Panno święta, co Jasnej bronisz Częstochowy\n",
    "I w Ostrej świecisz Bramie! Ty, co gród zamkowy\n",
    "Nowogródzki ochraniasz z jego wiernym ludem!\n",
    "Jak mnie dziecko do zdrowia powróciłaś cudem\n",
    "(Gdy od płaczącej matki, pod Twoją opiekę\n",
    "Ofiarowany, martwą podniosłem powiekę;\n",
    "I zaraz mogłem pieszo, do Twych świątyń progu\n",
    "Iść za wrócone życie podziękować Bogu),\n",
    "Tak nas powrócisz cudem na Ojczyzny łono.\n",
    "Tymczasem przenoś moją duszę utęsknioną\n",
    "Do tych pagórków leśnych, do tych łąk zielonych,\n",
    "Szeroko nad błękitnym Niemnem rozciągnionych;\n",
    "Do tych pól malowanych zbożem rozmaitem,\n",
    "Wyzłacanych pszenicą, posrebrzanych żytem;\n",
    "Gdzie bursztynowy świerzop, gryka jak śnieg biała,\n",
    "Gdzie panieńskim rumieńcem dzięcielina pała,\n",
    "A wszystko przepasane jakby wstęgą, miedzą\n",
    "Zieloną, na niej z rzadka ciche grusze siedzą.\n",
    "\"\"\"\n",
    "\n",
    "znaki = \"!,.;()\"\n",
    "czyste = inwokacja.lower()\n",
    "for z in znaki:\n",
    "    czyste = czyste.replace(z, \" \")\n",
    "slowa = czyste.split()\n",
    "licznik = Counter(slowa)\n",
    "print(\"słów:\", len(slowa), \"| różnych:\", len(licznik))\n",
    "for slowo, ile in licznik.most_common(6):\n",
    "    print(f\"{slowo:>6} {'█' * ile} {ile}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k17",
   "metadata": {},
   "source": [
    "Najczęstsze są krótkie słowa: przyimki i spójniki. W analizie tekstu nazywa się je *stop words* i zwykle pomija,\n",
    "bo niewiele mówią o treści."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k18",
   "metadata": {},
   "source": [
    "## 5) `heapq` — kolejka priorytetowa (min-heap)\n",
    "\n",
    "Kopiec trzyma **najmniejszy element na wierzchu** (`h[0]`). Wstawienie i zdjęcie kosztują O(log n)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k19",
   "metadata": {},
   "source": [
    "> **Przewidź, zanim uruchomisz:** po wstawieniu 5, 1, 9, 2 — co jest w `h[0]`? Jak wygląda cała lista `h`?\n",
    ">\n",
    "> <details><summary>Odpowiedź</summary>\n",
    ">\n",
    "> `h[0] = 1`, a `h = [1, 2, 9, 5]` — lista **nie** jest posortowana. Kopiec pilnuje tylko, żeby rodzic był mniejszy od dzieci.\n",
    ">\n",
    "> </details>"
   ]
  },
  {
   "cell_type": "code",
   "id": "k20",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import heapq\n",
    "\n",
    "h = []\n",
    "for x in [5, 1, 9, 2]:\n",
    "    heapq.heappush(h, x)\n",
    "print(\"lista h:\", h)\n",
    "print(\"min on top ->\", h[0])\n",
    "print(\"pop ->\", heapq.heappop(h))\n",
    "print(\"pop ->\", heapq.heappop(h))\n",
    "\n",
    "# Max-heap przez negację\n",
    "h = []\n",
    "for x in [5, 1, 9, 2]:\n",
    "    heapq.heappush(h, -x)\n",
    "print(\"max on top ->\", -h[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k21",
   "metadata": {},
   "source": [
    "### Nowe: kopiec to drzewo zapisane w liście\n",
    "\n",
    "Element o indeksie `i` ma dzieci pod indeksami `2*i + 1` i `2*i + 2`, a rodzica pod `(i - 1) // 2`.\n",
    "Warunek kopca: **rodzic ≤ dzieci**. `heappush` dokłada element na koniec i zamienia go z rodzicem, dopóki jest\n",
    "mniejszy („przesiewanie w górę”) — dlatego kosztuje tylko tyle kroków, ile drzewo ma poziomów: O(log n)."
   ]
  },
  {
   "cell_type": "code",
   "id": "k22",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def pokaz_kopiec(h):\n",
    "    poziom, i = 0, 0\n",
    "    while i < len(h):\n",
    "        szerokosc = 2 ** poziom\n",
    "        print(\"   \" * (3 - poziom), h[i:i + szerokosc])\n",
    "        i += szerokosc\n",
    "        poziom += 1\n",
    "\n",
    "kopiec = []\n",
    "for x in [5, 1, 9, 2, 7, 3, 8]:\n",
    "    heapq.heappush(kopiec, x)\n",
    "print(\"lista:\", kopiec)\n",
    "pokaz_kopiec(kopiec)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k23",
   "metadata": {},
   "source": [
    "### Nowe: max-heap w Pythonie 3.14\n",
    "\n",
    "Do Pythona 3.13 kopiec maksymalny robiło się przez negację (jak wyżej). Python 3.14 (7.10.2025) dodał gotowe funkcje:\n",
    "`heappush_max`, `heappop_max`, `heapify_max`, `heapreplace_max` i `heappushpop_max`. Komórka sprawdza,\n",
    "czy twój Python je ma."
   ]
  },
  {
   "cell_type": "code",
   "id": "k24",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import sys\n",
    "\n",
    "if hasattr(heapq, \"heappush_max\"):\n",
    "    h = []\n",
    "    for x in [5, 1, 9, 2]:\n",
    "        heapq.heappush_max(h, x)\n",
    "    print(\"Python\", sys.version.split()[0], \"→ max on top:\", h[0])\n",
    "else:\n",
    "    print(\"Python\", sys.version.split()[0], \"nie ma jeszcze heappush_max —\",\n",
    "          \"używaj negacji\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k25",
   "metadata": {},
   "source": [
    "### Nowe: kolejka priorytetowa i remisy\n",
    "\n",
    "Do kopca wkładasz krotki `(priorytet, dane)`. Przy remisie priorytetu Python porównuje **drugi element**.\n",
    "W kolejce zgłoszeń wygrałby wtedy alfabet, a nie kolejność przyjścia. Rozwiązanie: numer zgłoszenia jako\n",
    "drugi element."
   ]
  },
  {
   "cell_type": "code",
   "id": "k26",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "zgloszenia = [(2, \"drukarka\"), (1, \"serwer\"), (3, \"myszka\"), (1, \"baza\")]\n",
    "\n",
    "kopiec = []\n",
    "for z in zgloszenia:\n",
    "    heapq.heappush(kopiec, z)\n",
    "print(\"bez numeru:\", [heapq.heappop(kopiec)[1] for _ in zgloszenia])\n",
    "\n",
    "kopiec = []\n",
    "for numer, (priorytet, opis) in enumerate(zgloszenia):\n",
    "    heapq.heappush(kopiec, (priorytet, numer, opis))\n",
    "print(\"z numerem: \", [heapq.heappop(kopiec)[2] for _ in zgloszenia])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k27",
   "metadata": {},
   "source": [
    "## 6) `frozenset` i haszowalność kluczy\n",
    "\n",
    "`frozenset` to niemutowalny zbiór — może być kluczem w słowniku. Przydaje się, gdy klucz ma reprezentować\n",
    "**zestaw** niezależny od kolejności."
   ]
  },
  {
   "cell_type": "code",
   "id": "k28",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "klucz = frozenset({\"jablko\", \"banan\"})\n",
    "d = {klucz: \"zestaw owoców\"}\n",
    "print(d[frozenset({\"banan\", \"jablko\"})])  # ten sam klucz, inna kolejność"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k29",
   "metadata": {},
   "source": [
    "## 7) Kopiowanie: płytkie i głębokie (powtórka z zajęć 2)\n",
    "\n",
    "Kopia **płytka** tworzy nowy pojemnik, ale elementy w środku są wspólne. Kopia **głęboka** kopiuje wszystko."
   ]
  },
  {
   "cell_type": "code",
   "id": "k30",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import copy\n",
    "\n",
    "a = [[1, 2], [3, 4]]\n",
    "b = copy.copy(a)      # płytka\n",
    "c = copy.deepcopy(a)  # głęboka\n",
    "a[0].append(99)\n",
    "print(\"a =\", a)\n",
    "print(\"b =\", b, \"<- płytka współdzieli podlisty\")\n",
    "print(\"c =\", c, \"<- głęboka nie została zmieniona\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k31",
   "metadata": {},
   "source": [
    "## 8) Niezmienność: `tuple` jako klucz i `dataclass(frozen=True)`\n",
    "\n",
    "Krotka może być kluczem. `@dataclass(frozen=True)` tworzy niemutowalny rekord z nazwanymi polami — haszowalny,\n",
    "więc może trafić do zbioru. Klasy omówimy na zajęciach o programowaniu obiektowym; tu wystarczy wzorzec."
   ]
  },
  {
   "cell_type": "code",
   "id": "k32",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "from dataclasses import dataclass\n",
    "\n",
    "m = {(0, 1): \"A\", (2, 3): \"B\"}\n",
    "print(m[(0, 1)])\n",
    "\n",
    "@dataclass(frozen=True)\n",
    "class Point:\n",
    "    x: int\n",
    "    y: int\n",
    "\n",
    "s = {Point(1, 2), Point(1, 2)}  # duplikaty znikają: obiekt jest haszowalny\n",
    "print(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k33",
   "metadata": {},
   "source": [
    "## 9) Nowe: zajawka grafu — najkrótsza droga przez BFS\n",
    "\n",
    "Graf to węzły i połączenia między nimi: mapa przystanków, sieć znajomych, linki między stronami. W Pythonie\n",
    "najprościej zapisać go słownikiem list sąsiadów. **BFS** (przeszukiwanie wszerz) bierze węzły z **kolejki**\n",
    "— najpierw sąsiadów startu, potem ich sąsiadów — więc pierwsza znaleziona droga ma najmniej przesiadek.\n",
    "Grafy i drzewa omówimy dokładnie w module o algorytmach."
   ]
  },
  {
   "cell_type": "code",
   "id": "k34",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "polaczenia = {\n",
    "    \"A\": [\"B\", \"C\"],\n",
    "    \"B\": [\"A\", \"D\"],\n",
    "    \"C\": [\"A\", \"D\", \"E\"],\n",
    "    \"D\": [\"B\", \"C\", \"F\"],\n",
    "    \"E\": [\"C\", \"F\"],\n",
    "    \"F\": [\"D\", \"E\"],\n",
    "}\n",
    "\n",
    "def najkrotsza_droga(graf, start, cel):\n",
    "    poprzednik = {start: None}\n",
    "    kolejka = deque([start])\n",
    "    while kolejka:\n",
    "        wezel = kolejka.popleft()\n",
    "        if wezel == cel:\n",
    "            break\n",
    "        for sasiad in graf[wezel]:\n",
    "            if sasiad not in poprzednik:\n",
    "                poprzednik[sasiad] = wezel\n",
    "                kolejka.append(sasiad)\n",
    "    droga = []\n",
    "    while cel is not None:\n",
    "        droga.append(cel)\n",
    "        cel = poprzednik[cel]\n",
    "    return droga[::-1]\n",
    "\n",
    "print(najkrotsza_droga(polaczenia, \"A\", \"F\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k35",
   "metadata": {},
   "source": [
    "## 10) Jak wybrać strukturę danych?\n",
    "\n",
    "| Potrzebujesz | Struktura | Kluczowa operacja |\n",
    "|---|---|---|\n",
    "| ostatni wchodzi, pierwszy wychodzi (cofanie, nawiasy, DFS) | lista jako stos | `append`, `pop` — O(1) |\n",
    "| kolejności przyjścia (zadania, BFS) | `deque` | `append`, `popleft` — O(1) |\n",
    "| ostatnich n elementów (okno kroczące) | `deque(maxlen=n)` | `append` — O(1) |\n",
    "| grupowania i zliczania | `defaultdict`, `Counter` | `d[k] += 1` — O(1) |\n",
    "| zawsze „najmniejszy teraz” (priorytety, top-K, scalanie) | `heapq` | `heappush`, `heappop` — O(log n) |\n",
    "| szukania w posortowanych danych | lista + `bisect` | O(log n) |\n",
    "| złożonego, niezmiennego klucza | `tuple`, `frozenset` | hash — O(1) |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k36",
   "metadata": {},
   "source": [
    "## 11) Zadanie 4.0 — nawiasy zbalansowane (stos)\n",
    "\n",
    "Napisz funkcję `balanced(s: str) -> bool`, która sprawdza, czy nawiasy `()[]{}` w łańcuchu `s` są poprawnie\n",
    "zbalansowane i zagnieżdżone. Użyj **stosu**. Inne znaki ignoruj."
   ]
  },
  {
   "cell_type": "code",
   "id": "k37",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def balanced(s: str) -> bool:\n",
    "    # TODO: nawias otwierający na stos, przy zamykającym zdejmij i porównaj\n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "id": "k38",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    assert balanced('([]){}')\n",
    "    assert balanced('a(b[c]{d}e)f')\n",
    "    assert not balanced('([)]')\n",
    "    assert not balanced('(')\n",
    "    assert balanced('')\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 4.0 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k39",
   "metadata": {},
   "source": [
    "## Zadanie 4.1 — średnia krocząca (deque)\n",
    "\n",
    "*W oryginalnej wersji notatnika był sam test tego zadania — bez polecenia i szablonu.*\n",
    "\n",
    "Uzupełnij metodę `add` klasy `MovingAverage`: dodaj `x` do okna i zwróć średnią z wartości w oknie.\n",
    "Okno to `deque(maxlen=n)` — pamięta tylko `n` ostatnich wartości (sekcja 3). `__init__` jest gotowe."
   ]
  },
  {
   "cell_type": "code",
   "id": "k40",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "\n",
    "\n",
    "class MovingAverage:\n",
    "    \"\"\"Średnia z ostatnich n wartości.\"\"\"\n",
    "\n",
    "    def __init__(self, n: int):\n",
    "        self.okno = deque(maxlen=n)\n",
    "\n",
    "    def add(self, x: float) -> float:\n",
    "        # TODO: dodaj x do self.okno i zwróć średnią z okna\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "id": "k41",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    ma = MovingAverage(3)\n",
    "    assert abs(ma.add(3) - 3.0) < 1e-9\n",
    "    assert abs(ma.add(5) - 4.0) < 1e-9\n",
    "    assert abs(ma.add(7) - 5.0) < 1e-9\n",
    "    assert abs(ma.add(6) - 6.0) < 1e-9  # okno [5, 7, 6]\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 4.1 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k42",
   "metadata": {},
   "source": [
    "## Zadanie 4.2 — Top-K słów (Counter)\n",
    "\n",
    "Napisz funkcję `top_k_words(text: str, k: int) -> list[tuple[str, int]]`, która zwraca listę **k najczęstszych\n",
    "słów** (małe litery, podział po białych znakach). Użyj `collections.Counter`. **Przy remisie sortuj alfabetycznie.**\n",
    "\n",
    "*Uwaga:* `most_common(k)` przy remisie zostawia kolejność pierwszego wystąpienia, a nie alfabet — test to sprawdza.\n",
    "Wskazówka: `sorted(licznik.items(), key=lambda p: (-p[1], p[0]))`."
   ]
  },
  {
   "cell_type": "code",
   "id": "k43",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "\n",
    "def top_k_words(text: str, k: int):\n",
    "    # TODO: policz słowa, posortuj malejąco po liczbie, przy remisie po słowie\n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "id": "k44",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    out = top_k_words('Ala ma kota ala Ala Lubi kota', 2)\n",
    "    assert out[0] == ('ala', 3) and out[1] == ('kota', 2)\n",
    "    assert top_k_words('b a c b a', 2) == [('a', 2), ('b', 2)]  # remis\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 4.2 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k45",
   "metadata": {},
   "source": [
    "## Zadanie 4.3 — scalanie k posortowanych list (heapq)\n",
    "\n",
    "Napisz funkcję `merge_k_sorted(lists: list[list[int]]) -> list[int]`, która scala **k posortowanych rosnąco** list\n",
    "w jedną posortowaną listę. Użyj kopca `heapq`: trzymaj w nim krotki `(wartość, nr_listy, pozycja)`."
   ]
  },
  {
   "cell_type": "code",
   "id": "k46",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import heapq\n",
    "\n",
    "\n",
    "def merge_k_sorted(lists):\n",
    "    # TODO: na start pierwszy element każdej listy; potem heappop\n",
    "    # i dokładanie następnego elementu z tej samej listy\n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "id": "k47",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    inp = [[1, 4, 5], [1, 3, 4], [2, 6]]\n",
    "    assert merge_k_sorted(inp) == [1, 1, 2, 3, 4, 4, 5, 6]\n",
    "    assert merge_k_sorted([[], [0], []]) == [0]\n",
    "    assert merge_k_sorted([]) == []\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 4.3 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k48",
   "metadata": {},
   "source": [
    "## Zapamiętaj\n",
    "\n",
    "- **Stos** — lista z `append`/`pop`. **Kolejka** — `deque` z `append`/`popleft`. Okno — `deque(maxlen=n)`.\n",
    "- **Counter** i **defaultdict** liczą i grupują bez sprawdzania, czy klucz już jest.\n",
    "- **Kopiec** (`heapq`) trzyma minimum na wierzchu; wstawianie i zdejmowanie w O(log n). To drzewo zapisane w liście.\n",
    "- **Szukanie binarne** w posortowanych danych: O(log n) zamiast O(n).\n",
    "\n",
    "## Zadania dodatkowe\n",
    "\n",
    "1. Dlaczego BFS używa kolejki, a nie stosu? Co by się stało, gdyby zamienić `popleft()` na `pop()`?\n",
    "2. Masz strumień milionów liczb i potrzebujesz 10 największych. Dlaczego kopiec o rozmiarze 10 wystarczy?\n",
    "3. Znajdź w dokumentacji `heapq.nlargest` i sprawdź, jak go użyć do zadania 2."
   ]
  }
 ],
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  }
 }
}