🍕 Разбор задачки о доставке пиццы

Всем привет! Время разбирать задачку про курьеров и заказы. Задачка имеет очень лаконичное решение.

Ключевая идея для решения большинства подобных задач — сначала посчитать все возможные варианты без ограничений, а затем "отсечь" те, которые нарушают наши правила.

Самый математически красивый подход выглядит так:

import math

def count_valid_orders(n: int) -> int:
    return math.factorial(2 * n) // (2**n)

🤔 Как это работает?

Давайте рассуждать по шагам.

1️⃣ Шаг 1: Все возможные перестановки.
Представим, что у нас есть 2n уникальных событий (P1, D1, P2, D2, ..., Pn, Dn). Сколько всего существует способов расставить их в линию? Правильно, это просто перестановки, то есть (2n)!.

2️⃣ Шаг 2: Учитываем наше правило.
Главное правило: Pi всегда должно стоять раньше Di.
Возьмём любую пару, например, (P1, D1). В общем числе перестановок (2n)! ровно в половине случаев P1 будет стоять раньше D1, а в другой половине — D1 раньше P1. Нас устраивает только первый вариант. Значит, чтобы отсечь все неподходящие варианты для пары (P1, D1), нужно поделить общее число перестановок на 2.

3️⃣ Шаг 3: Обобщаем на все пары.
У нас n таких независимых пар! Для каждой из них мы должны отсечь половину невалидных последовательностей. Поэтому мы делим общее число перестановок на 2 n раз.

Получаем финальную формулу: (2n)! / 2^n.

- Сложность по времени: O(N), так как вычисление факториала (2n)! занимает линейное время от его аргумента.
- Сложность по памяти: O(1).

🍉 Как выбрать арбуз с помощью Python

Сезон арбузов в самом разгаре! Уже кушали? Если да, то точно столкнулись с извечной проблемой оптимизация процесса выбора арбуза.

Забываем дедовские методы, мы же не хотим полагаться на какую-то интуицию и субъективщину? В 21 веке такие важные решения должны приниматься исключительно на основе данных. Нам нужны метрики, пайплайны и воспроизводимые результаты!

Итак, представляю вам фреймворк Watermelon Driven Development (WDD).

Этап 1: Сбор данных

Подходим к арбузному развалу. Наша задача — собрать первичный датасет. Для каждого экземпляра (candidate) нам нужны следующие фичи:

- weight (float): Масса. Взвешиваем на местных весах. Если их нет — используем безмен или оцениваем на глаз, предварительно откалибровав руку на известном весе (например, на своем макбуке).
- volume (float): Объем. Определяется методом погружения в таз с водой, но на рынке это может вызвать подозрения. Поэтому аппроксимируем до эллипсоида и считаем по формуле. Замеры делаем рулеткой.
- acoustic_response (dict): Акустический отклик. Стучим по арбузу костяшкой пальца в трех разных точках (экватор, полюс №1, полюс №2). Записываем звук на диктофон. Позже прогоним через FFT-анализ для поиска резонансных частот.
- surface_pattern_complexity (float): Сложность паттерна полосок. Фотографируем и прогоняем через простенькую CV-модель для оценки энтропии изображения. Чем контрастнее и четче полоски — тем выше метрика.
- peduncle_dryness_coefficient (float): Коэффициент сухости хвостика. Значения от 0.0 (свежесрезанный, зеленый) до 1.0 (засохший, ломкий).
- stain_yellowness_index (int): Индекс желтизны земляного пятна. Используем цветовую палитру Pantone для точной оценки. Градация от 1 (белый) до 10 (насыщенно-желтый).

Этап 2: Препроцессинг и Feature Engineering

Сырые данные — мусор. Нам нужны производные признаки, которые действительно коррелируют с целевой переменной sweetness_score.

def preprocess_watermelon_data(candidates: list) -> pd.DataFrame:
    processed_data = []
    for candidate in candidates:
        # Плотность - ключевой показатель!
        candidate['density'] = candidate['weight'] / candidate['volume']

        # Анализируем звук: "звонкий" звук имеет пик в определенном диапазоне частот
        fft_peaks = analyze_fft(candidate['acoustic_response'])
        candidate['is_sound_ringing'] = 500 < fft_peaks.main_freq < 800

        # Нормализуем остальные фичи
        # ... (тут сложная математика)

        processed_data.append(candidate)
    
    return pd.DataFrame(processed_data)

Этап 3: Модель принятия решений (Decision Model)

Никаких if-else! Это слишком примитивно. Мы будем использовать взвешенную скоринговую модель. Веса подобраны на основе анализа тысяч арбузов (нет).

# Веса фичей, подобранные экспертным путем в ходе A/B-теста
WEIGHTS = {
    'density': 0.4,
    'is_sound_ringing': 0.3,
    'peduncle_dryness_coefficient': 0.15,
    'stain_yellowness_index': 0.1,
    'surface_pattern_complexity': 0.05,
}

def get_watermelon_score(candidate: pd.Series) -> float:
    """Рассчитывает итоговый скор для кандидата."""
    score = 0
    score += candidate['density'] * WEIGHTS['density']
    score += candidate['is_sound_ringing'] * WEIGHTS['is_sound_ringing']
    # ... и так далее для всех фичей
    return score

# Выбираем арбуз с максимальным скором
best_watermelon = candidates_df.loc[candidates_df['score'].idxmax()]

Итоговый алгоритм:
1. Подходите к развалу.
2. Достаете ноутбук, весы, рулетку, диктофон и палитру Pantone.
3. На недоумевающие взгляды продавца и других покупателей отвечаете: "Спокойно, я шарю".
4. Скрупулезно собираете датасет по 5-10 кандидатам.
5. Запускаете Jupyter-ноутбук, выполняете все ячейки.
6. Модель выдает вам id лучшего арбуза.
7. Покупаете его.
8. Дома разрезаете... а он неспелый.

Потому что ваша модель переобучилась на локальных данных, не учла сезонные дрифты и аномалии в поставке! Нужна MLOps-инфраструктура, постоянный мониторинг и версионирование моделей. В следующем году построим.

#хих