Maximize A using digits from B (Python + uv)

Решение алгоритмической задачи на Python: даны два строковых представления чисел A и B. Нужно максимизировать A, выполняя замену цифр в A на цифры из B, при этом каждую цифру из B можно использовать только один раз.

Проект подходит для практики тем: алгоритмы, строки, оптимизация, greedy (жадный алгоритм), обработка краевых случаев. Формат задачи типичен для competitive programming / coding challenge / interview.

Условие

Даны два строковых представления чисел A и B. Нужно максимизировать A, заменив в нём любую цифру на цифру из B. Каждую цифру B можно использовать только один раз.

Уточнения (по твоим требованиям):

• ✅ Отрицательные числа возможны (знак - не является цифрой и не заменяется).
• ✅ Ведущие нули сохраняются (например, "0009", "-0120").
• ✅ Реализация делает несколько замен (пока не закончатся цифры в B).

Алгоритм (как работает текущая реализация)

Функция main(numA: str, numB: str) -> str проходит по A слева направо и жадно делает замену, если это увеличивает результат:

• Для положительного A:

  • сортирует цифры B по возрастанию и держит «самую большую доступную» в конце списка;
  • если текущая цифра A[i] меньше максимальной доступной цифры из B, то заменяет на неё.

• Для отрицательного A:

  • сортирует цифры B по убыванию, и берёт «самую маленькую доступную» из конца списка;
  • если можно уменьшить текущую цифру (сделать её меньше), то выполняет замену — это делает число менее отрицательным (ближе к нулю).

Дополнительно:

• если после замен все цифры стали '0', знак - не добавляется (получается "0000", а не "-0000").

Сложность

Пусть n = len(A), m = len(B).

• Время: O(m log m + n) из‑за сортировки B и одного прохода по A.
• Память: O(m + n) (списки цифр B и результат).

Возможная оптимизация: так как цифр всего 10 (0..9), можно заменить сортировку на подсчёт частот (аналог Counter) и получить O(n + m).

Структура проекта

.
├── src/
│   └── main.py
├── tests/
│   └── test_main.py
├── .gitignore
├── .python-version
├── pyproject.toml
├── uv.lock
└── README.md

Требования

• Python 3.12+
• uv (устанавливается глобально)

---

Установка uv (глобально) — основной способ ✅

Рекомендуемый путь — официальный installer от Astral (ставит uv в пользовательский PATH).

Windows (PowerShell)

Вариант A — официальный installer (рекомендуется)

powershell -ExecutionPolicy ByPass -c "irm https://astral.sh/uv/install.ps1 | iex"

Проверка:

uv --version

Вариант B — WinGet

winget install --id=astral-sh.uv -e

Вариант C — Scoop

scoop install main/uv

Linux (bash/zsh)

Вариант A — официальный installer (рекомендуется)

curl -LsSf https://astral.sh/uv/install.sh | sh

Если curl нет:

wget -qO- https://astral.sh/uv/install.sh | sh

Проверка:

uv --version

Альтернативы (когда нельзя запускать install-скрипты)

pipx (глобально, изолированно)

pipx install uv

pip (глобально, менее предпочтительно)

python -m pip install -U uv

---

Запуск проекта (uv)

1) Установка зависимостей

В корне репозитория:

uv sync

2) Запуск приложения

Linux

uv run python src/main.py

Windows (PowerShell)

uv run python .\src\main.py

3) Запуск тестов

uv run pytest -q

---

Примеры

Положительное число

from src.main import main

print(main("8350", "0129"))  # -> "9352"

Отрицательное число

from src.main import main

print(main("-8350", "0129"))  # -> "-0120"

---

GitHub Topics (тэги)

Рекомендуемые темы (10–20 шт.) для поля Topics на GitHub:

• python
• uv
• algorithms
• greedy-algorithm
• strings
• digit-replacement
• maximize-number
• optimization
• competitive-programming
• coding-challenge
• interview-problem
• pytest
• unit-testing
• edge-cases
• leading-zeros
• negative-numbers