# Домашнє завдання · Словники

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

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

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

---

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

### 1.1 · Твоя телефонна книга

Створи словник `книга` щонайменше з чотирма записами «ім'я → номер». Потім:

1. надрукуй номер одного з наявних імен через квадратні дужки;
2. надрукуй номер неіснуючого імені через `.get()` зі значенням за замовчуванням
   `"немає в книзі"`;
3. додай новий запис і одразу перезапиши його іншим номером;
4. видали один запис через `pop`, зберігши видалений номер у змінну й надрукувавши його.

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

```python
assert len(книга) == 4
assert книга.get("такого точно немає") is None
```

і жодного разу програма не впала з `KeyError`.

### 1.2 · Таблиця замість умов

Дано словник відповідностей «літера ноти → її частота в герцах»:

```python
частоти = {"до": 261.6, "ре": 293.7, "мі": 329.6, "фа": 349.2, "соль": 392.0}
```

Надрукуй частоти для `"мі"`, `"соль"` і для неіснуючої `"сі"` — останню з поясненням
`"такої ноти в таблиці немає"`. Усе через `.get()`, без жодної перевірки `if`.

**Зроблено, якщо:** твій код друкує три рядки, третій із них — саме пояснення, а не
`None` і не помилка. Перевір, що словник після всіх звертань лишився з п'ятьма ключами:

```python
assert len(частоти) == 5
```

---

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

### 2.1 · Злиття налаштувань

Є три словники: типові налаштування програми, налаштування команди й особисті
налаштування користувача.

```python
типові = {"тема": "світла", "мова": "uk", "шрифт": 14, "автозбереження": True}
командні = {"мова": "en", "шрифт": 13}
особисті = {"тема": "темна"}
```

Зроби **новий** словник `підсумкові`, у якому пріоритет зростає в порядку
типові → командні → особисті. Вихідні три словники мають лишитися незмінними.

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

```python
assert підсумкові == {"тема": "темна", "мова": "en", "шрифт": 13, "автозбереження": True}
assert типові["тема"] == "світла"
assert командні == {"мова": "en", "шрифт": 13}
assert len(підсумкові) == 4
```

і ти пояснив у коментарі одним реченням, чому саме `особисті` мають стояти справа.

### 2.2 · 🔁 Частоти літер і перевірка себе

Візьми довільний рядок щонайменше з 40 символів (наприклад, перше речення лекції).
Порахуй, скільки разів трапляється кожна літера, використовуючи **тільки**
ідіому `лічильник[символ] = лічильник.get(символ, 0) + 1`.

Пробіли не рахуй: прибери їх заздалегідь через `рядок.replace(" ", "")`.

Потім порівняй свій результат із `collections.Counter` по тому самому рядку.

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

```python
from collections import Counter
assert мій_лічильник == dict(Counter(текст_без_пробілів)), "розійшлося з Counter"
```

і ти надрукував три найчастіші літери разом із їхньою кількістю (підказка:
`Counter(...).most_common(3)` — але спершу дістань їх зі свого словника).

### 2.3 · Де ламається порядок

Створи словник із чотирьох ключів. Надрукуй `list(словник)`. Потім:

1. зміни **значення** середнього ключа — надрукуй порядок знову;
2. видали цей ключ і додай його заново з тим самим значенням — надрукуй порядок знову.

**Зроблено, якщо:** ти показав кодом і `assert`-ами, що в першому випадку порядок
не змінився, а в другому ключ поїхав у кінець, і пояснив словами (2–3 речення), чому
ці два випадки різні з точки зору хеш-таблиці.

---

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

### 3.1 · Своя міні-хеш-таблиця

Реалізуй хеш-таблицю на **списку з 8 комірок**, не використовуючи `dict` узагалі.
Потрібні три функції:

- `хеш(ключ)` — повертає ціле число з рядка. Візьми ту саму формулу, що в лекції:
  починаєш з нуля й на кожному символі робиш `v = (v * 31 + ord(символ)) % 2**31`;
- `покласти(таблиця, ключ, значення)` — знаходить комірку за `хеш(ключ) % 8`, а якщо
  вона зайнята **іншим** ключем, шукає наступного кандидата за правилом CPython:
  `j = (5 * j + 1 + збурення) % 8`, де `збурення` спершу дорівнює хешу і на кожному
  кроці зсувається вправо на 5 біт (`збурення >>= 5`);
- `взяти(таблиця, ключ, за_замовчуванням=None)` — іде **тим самим маршрутом** і повертає
  значення або запасний варіант.

Кожна комірка — або `None`, або пара `[ключ, значення]`. Цикли тут дозволені.

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

```python
таблиця = [None] * 8
покласти(таблиця, "Аня", "067")
покласти(таблиця, "Богдан", "050")
покласти(таблиця, "Галя", "063")
покласти(таблиця, "Оля", "095")        # хеш 1047570, цілиться в комірку 2 — колізія

assert хеш("Аня") == 1034178
assert хеш("Оля") == 1047570
assert хеш("Оля") % 8 == 2             # та сама комірка, що в «Аня»
assert таблиця[2][0] == "Аня"          # «Аня» лишилась на місці
assert таблиця[5][0] == "Оля"          # «Оля» переїхала в комірку 5
assert взяти(таблиця, "Оля") == "095"  # і все одно знаходиться
assert взяти(таблиця, "Петро", "—") == "—"
```

Числа тут не випадкові: це рівно те, що показує інтерактив 4 у лекції. Якщо твої
не збігаються — шукай різницю у формулі хеша.

### 3.2 · Скільки коштує колізія

Спираючись на 3.1, додай у `покласти` й `взяти` підрахунок **спроб**: скільки комірок
довелося оглянути, перш ніж знайшлася потрібна.

Зроби таблицю на 8 комірок і заповнюй її ключами `"к1"`, `"к2"`, … по одному, щоразу
друкуючи, скільки спроб пішло на вставку та яке зараз заповнення у відсотках.

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

1. чому Python не дозволяє заповнювати таблицю більш ніж на дві третини;
2. що станеться з `взяти`, якщо таблиця заповниться повністю, а шуканого ключа в ній
   немає (спробуй це відтворити — і полагодь так, щоб функція не зациклилась).

---

## Підказки

- **`.get()` не змінює словник, `setdefault` змінює.** У Рівні 2.2 потрібен саме `.get()`:
  якщо випадково взяти `setdefault`, лічильник усе одно порахується правильно, але
  код стане важчим для читання — і на співбесіді це помітять.
- **Об'єднання через `|` не змінює операнди.** Тому в 2.1 достатньо одного рядка
  без жодного `dict(...)`-копіювання: `типові | командні | особисті`. Обчислюється
  зліва направо, отже правий завжди переважує.
- **У 3.1 не забудь про випадок «ключ уже є».** Якщо в комірці лежить пара з тим самим
  ключем, треба замінити значення, а не шукати далі. Інакше один ключ опиниться
  в таблиці двічі — і `взяти` поверне те, що трапилось першим.
- **Зсув `>>= 5` на цілих числах Python безпечний** — вони необмежені, і рано чи пізно
  збурення стане нулем. Саме тоді маршрут вироджується в просте `j = (5 * j + 1) % 8`,
  яке гарантовано обходить усі 8 комірок.
- **Перевіряй на маленькому.** Перш ніж запускати всі чотири вставки, переконайся,
  що `хеш("Аня")` дає рівно `1034178`. Якщо ні — помилка у формулі, і далі шукати
  колізії немає сенсу.