🧩 Python‑задача: построить резолвер зависимостей для «мини‑PyPI»

Нужно написать ядро пакетного менеджера — алгоритм, выбирающий набор совместимых версий библиотек под заданные ограничения.
Задача напоминает работу pip, npm или cargo, но в упрощённом формате, достаточном для тренировки графовых алгоритмов, backtracking и оптимизаций.

## 📜 Входные данные

1. catalog.json — «репозиторий» пакетов.

   {
     "pandas": {
       "1.1.0": { "depends": { "numpy": ">=1.17,<1.20" } },
       "1.3.5": { "depends": { "numpy": ">=1.19,<1.22", "python-dateutil": ">=2.7" } }
     },
     "numpy": {
       "1.18.5": { "depends": {} },
       "1.19.2": { "depends": {} },
       "1.21.0": { "depends": {} }
     },
     "python-dateutil": {
       "2.8.0": { "depends": { "six": ">=1.5" } },
       "2.8.2": { "depends": { "six": ">=1.5" } }
     },
     "six": {
       "1.14.0": { "depends": {} },
       "1.16.0": { "depends": {} }
     }
   }
   

*Ключ* — имя пакета; *значения* — версии → словарь зависимостей (`depends`).
У каждой зависимости указан диапазон версий по SemVer‑синтаксису >=a,<b.

2. requirements.txt — то, что хочет пользователь:

   pandas>=1.1,<1.4
   python-dateutil==2.8.2
   

## 🔧 Задача

Написать функцию

resolve(catalog: dict[str, dict[str, dict]],
        requirements: list[str]) -> dict[str, str]

которая возвращает словарь
{package: chosen_version} — единственную консистентную конфигурацию, удовлетворяющую всем ограничениям, *либо* возбуждает UnresolvableError.

### Правила

1. Версия должна лежать в пересечении *всех* диапазонов, навешанных на пакет.
2. Если диапазон пуст — конфликты нельзя игнорировать.
3. Разрешение идёт по принципу «самая новая подходящая версия» (Greedy‑latest), но если она приводит к заведомому конфликту, надо откатиться («backtrack») и попробовать более старую.
4. Каталог может быть большим (≥ 10 000 пакетов), алгоритм должен укладываться в секунды.
5. Допустимо использовать только стандартную библиотеку + packaging.version/packaging.specifiers (pip‑compatible сравнение версий).

## 🏁 Дополнительные челленджи

* Кэшировать результаты проверки диапазонов, чтобы не пересчитывать одно и то же.
* Оптимизировать порядок обхода графа (например, сначала пакеты с меньшим числом разрешимых версий).
* Добавить «экзотики»: опциональные зависимости, extras (`pandas[perf]`) или marker‑выражения (`sys_platform == "linux"`).

---

# ✅ Референс‑решение (однофайловое, python 3.11)

> *Не читайте решение в комментариях, пока не попробуете решить сами!*

@python_job_interview