# Домашнє завдання · Множини

> Лекція: [lecture.html](lecture.html) · Практика: [practice.ipynb](practice.ipynb) · Тест: [quiz.html](quiz.html)

Три рівні. Кожен наступний спирається на попередній, але братися можна за будь-який.
Пиши в окремому файлі `homework_09.py` або в новому зошиті — головне, щоб код
запускався й друкував результат.

Дозволено з бібліотек: `sys`, `time`. Більше нічого не треба.
Циклів і умов ми ще не проходили — усі завдання розв'язуються без них, окрім
позначених 🔁 (там цикл і `if` дозволені як забігання наперед у теми 11–12).

**Одне правило на всі рівні.** Множина порядку не зберігає, а хеш рядка змінюється
між запусками. Тому будь-який вивід множини рядків друкуй через `sorted(...)`, а
в `assert`-ах порівнюй множини з множинами (`==` дивиться на склад, не на порядок),
а не списки зі списками.

---

## 🟢 Рівень 1 — База

### 1.1 · Скільки різних

Склади список щонайменше з 12 елементів, у якому є повтори, — наприклад, назви фільмів,
які ти дивився за місяць, або міста, де ти був. Далі:

1. надрукуй довжину списку;
2. зроби з нього множину й надрукуй її довжину;
3. надрукуй, скільки повторів було відкинуто;
4. надрукуй сам набір різних значень через `sorted(...)`.

**Зроблено, якщо:** у виводі видно всі чотири рядки, а наприкінці виконуються

```python
assert len(унікальні) < len(мій_список)
assert len(мій_список) - len(унікальні) == кількість_повторів
```

і жодного разу не з'явився `{}` там, де мала бути порожня множина.

### 1.2 · Дві помилки, які треба побачити

Напиши три короткі перевірки й надрукуй результат кожної:

1. `type({})` і `type(set())` — покажи, що це різні типи;
2. `discard` на елементі, якого немає, — покажи `assert`-ом, що множина не змінилась;
3. `remove` на тому самому елементі — злови помилку через `try/except KeyError` і
   надрукуй її текст.

**Зроблено, якщо:** програма доходить до кінця й не падає, але у виводі видно
справжній `KeyError` та його елемент. Підказка: конструкція
`except KeyError as помилка: print(помилка)` робить рівно це.

---

## 🟡 Рівень 2 — Плюс

### 2.1 · Два дні відвідувань

Дано сирі логи (у них є повтори — це нормально, людина заходила двічі):

```python
вчора = ["/головна", "/ціни", "/про-нас", "/головна", "/ціни"]
сьогодні = ["/ціни", "/контакти", "/головна", "/контакти"]
```

Порахуй і надрукуй **чотири** відповіді, кожну одним виразом над множинами:

1. які сторінки дивились обидва дні;
2. які сторінки з'явились сьогодні;
3. які сторінки зникли;
4. які сторінки дивились лише в один із двох днів.

**Зроблено, якщо:** виконуються всі чотири перевірки

```python
assert спільні == {"/головна", "/ціни"}
assert зʼявились == {"/контакти"}
assert зникли == {"/про-нас"}
assert лише_в_одному == {"/контакти", "/про-нас"}
```

і ти пояснив у коментарі одним реченням, чому пункт 4 — це не сума пунктів 2 і 3
випадково, а завжди.

### 2.2 · Права доступу без жодного `if`

Дано:

```python
потрібні = {"читати", "писати"}
адмін = {"читати", "писати", "видаляти", "запрошувати"}
гість = {"читати"}
редактор = {"читати", "писати"}
```

Для кожного з трьох користувачів надрукуй один рядок виду
`адмін: доступ дозволено = True`. Використай **тільки** порівняння множин
(`<=`, `>=`, `<`, `>`), без жодної перевірки `if` і без `len`.

Далі відповідь на питання зі зіркою: покажи кодом, що `редактор` — підмножина
`потрібні` **і** надмножина `потрібні` одночасно, і поясни в коментарі, що це означає.

**Зроблено, якщо:** виконуються

```python
assert потрібні <= адмін
assert not (потрібні <= гість)
assert редактор <= потрібні and редактор >= потрібні
assert редактор == потрібні
```

і в коментарі сказано, чому останні два рядки — це одне й те саме твердження.

### 2.3 · 🔁 Скільки коштує «немає»

Побудуй список із 50 000 рядків виду `"слово00000"`, `"слово00001"`, … і множину
з тих самих рядків. Заміряй `time.perf_counter()` навколо перевірки
`"такого-слова-немає" in ...` для обох структур, повторивши перевірку 100 разів.

**Зроблено, якщо:** ти надрукував обидва часи й відношення між ними, а в коментарі
відповів на два питання:

1. чому ми міряємо саме випадок «слова немає», а не «слово є першим»;
2. чому в лекції ті самі дані показані в **кроках**, а не в мілісекундах.

---

## 🔴 Рівень 3 — Виклик

### 3.1 · Своя алгебра множин

Реалізуй чотири функції, які повторюють вбудовані операції, **не використовуючи**
операторів `|`, `&`, `-`, `^` і однойменних методів. Дозволено тільки `in`, `not in`,
`add`, `set()` і цикл `for`:

- `моє_обʼєднання(a, b)`
- `мій_перетин(a, b)`
- `моя_різниця(a, b)`
- `моя_симетрична(a, b)`

**Зроблено, якщо:** усі перевірки проходять на трьох різних парах множин —
таких, що перетинаються частково, не перетинаються зовсім і збігаються повністю:

```python
for A, B in [({1,2,3}, {3,4}), ({1,2}, {3,4}), ({1,2}, {1,2})]:
    assert моє_обʼєднання(A, B) == A | B
    assert мій_перетин(A, B) == A & B
    assert моя_різниця(A, B) == A - B
    assert моя_симетрична(A, B) == A ^ B
print("✅ уся алгебра збіглася")
```

і ти дописав у коментарі, скільки разів кожна функція виконує `in` залежно від
розмірів `a` і `b`.

### 3.2 · Множина множин

Є список команд, кожна — список імен. Ті самі люди могли записатись у різному порядку:

```python
команди = [["Аня", "Богдан"], ["Богдан", "Аня"], ["Галя", "Оля", "Петро"], ["Аня", "Галя"]]
```

Порахуй, скільки серед них **різних** команд. Пряме `set(команди)` не спрацює —
розберись, чому саме, і полагодь це одним словом.

Далі зроби словник «команда → кількість людей у ній» і надрукуй його.

**Зроблено, якщо:** виконуються

```python
assert len(різні_команди) == 3
assert frozenset({"Богдан", "Аня"}) in різні_команди
assert розміри[frozenset({"Галя", "Оля", "Петро"})] == 3
```

і ти пояснив у коментарі двома реченнями, чому тут потрібен саме `frozenset`,
а не кортеж: що зламалось би, якби ключем був `("Аня", "Богдан")`.

### 3.3 · Де межа заповнення

Спираючись на розділ 15 практики, знайди експериментом, на якому за рахунком елементі
множина перебудовує таблицю. Зроби те саме зі словником (додавай пари `номер: номер`)
і надрукуй обидві послідовності «номер елемента → новий `sys.getsizeof`».

**Зроблено, якщо:** ти показав числами, що множина перебудовується **раніше** за
словник на тому самому розмірі, і письмово відповів, чому так: у словника дірки
живуть у маленькій індексній таблиці по байту на комірку, а в множини кожна дірка —
повноцінна комірка. Одного речення досить, але воно має спиратись на твої числа.

---

## Підказки

- **`{}` — це словник.** Якщо десь у розв'язку з'явився порожній набір, він мусить
  бути `set()`. Найшвидший спосіб зловити помилку — надрукувати `type(...)`.
- **Порівнюй множини з множинами.** `sorted(A) == sorted(B)` теж працює, але ховає
  саму ідею: `A == B` для множин дивиться на склад, а не на порядок, і це коротше.
- **У 2.2 не потрібен жоден `if`.** `потрібні <= адмін` уже повертає `True` або
  `False` — залишається це надрукувати.
- **У 3.1 симетричну різницю простіше зібрати з двох різниць,** які ти вже написав,
  ніж окремим проходом. Але спершу перевір, чи не порушує це умову задачі.
- **У 3.2 підказка в одне слово — `frozenset`.** Друга частина питання складніша:
  подумай, скільки різних кортежів дадуть ті самі двоє людей і чому це псує підрахунок.
- **У 3.3 не роби висновку з одного стрибка.** Візьми хоча б 40 елементів і подивись
  на всі стрибки: перший може здатися випадковим, три поспіль — уже закономірність.