Условие

Фабрика производит слова из первого четверостишия А.С. Пушкина «Во глубине сибирских руд»:

Во глубине сибирских руд
Храните гордое терпенье,
Не пропадет ваш скорбный труд
И дум высокое стремленье.

Каждый день поступает заказ на одно из слов из четверостишия (равновероятно). Бизнес-правила:

Каждое проданное слово приносит +40 рублей.
Если слово невозможно собрать — −10 рублей неустойки.
Если для сборки слова не хватает только одной буквы — её можно доставить экспресс-доставкой за +2 рубля (то есть собрать всё-таки можно, но прибыль уменьшается).
Хранение одной буквы на складе: 1 рубль за день.
В конце дня запасы букв возобновляются (то есть мы не «расходуем» — это число, которое держим каждый день).
Регистр и пунктуация не учитываются.

Цель: подобрать оптимальный набор букв на складе (словарь буква → количество), максимизирующий среднюю дневную прибыль.

Решение

Шаг 1. Препроцессинг текста

Считаем «слова» — последовательности букв без пунктуации. Получаем список из 16 слов. Для каждого слова — мультимножество его букв (по сути, Counter).

import re
from collections import Counter
 
text = """Во глубине сибирских руд
Храните гордое терпенье,
Не пропадет ваш скорбный труд
И дум высокое стремленье."""
 
words = re.findall(r"[А-Яа-яЁё]+", text)
words = [w.lower() for w in words]
word_counters = [Counter(w) for w in words]

Шаг 2. Прибыль за день при заданном складе

Заказ — равновероятное слово из 16. Для фиксированного склада S (мультимножество) и слова w_i:

Пусть missing(S, w_i) — суммарное число «недостающих» букв = sum(max(0, w_i[c] - S[c])) for c in alphabet.

missing == 0 → продажа: +40.
missing == 1 → экспресс: +38 (40 − 2).
missing >= 2 → провал: −10.

Плюс ежедневные расходы на хранение: −sum(S.values()).

def daily_profit(S: Counter, word_counters):
    storage_cost = sum(S.values())
    profits = []
    for wc in word_counters:
        miss = sum(max(0, wc[c] - S[c]) for c in wc)
        if miss == 0:    profits.append(40)
        elif miss == 1:  profits.append(38)
        else:            profits.append(-10)
    expected = sum(profits) / len(profits)
    return expected - storage_cost

Шаг 3. Поиск оптимального склада

Пространство решений: словарь буква → 0..max_count, где max_count — максимальное число вхождений буквы в самом длинном слове (≈ 3–4). Букв в алфавите задействовано порядка 25 — комбинаций ~5^25 ≈ непосильно.

Несколько практичных подходов:

(а) Жадный + локальный поиск: стартовать с пустого склада, на каждой итерации пробовать +1 к одной букве и −1 к одной — выбираем шаг, увеличивающий ожидаемую прибыль. Останавливаемся, когда ни один шаг не улучшает.

(б) Hill climbing с рестартами (snowball): много раз стартуем из разных рандомных конфигураций.

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

(г) Симуляция + глобальная оптимизация: scipy.optimize.differential_evolution на целых.

Простейший — пункт (а). Код:

def neighbors(S, alphabet):
    out = []
    for c in alphabet:
        S2 = S.copy(); S2[c] += 1; out.append(S2)
        if S[c] > 0:
            S2 = S.copy(); S2[c] -= 1; out.append(S2)
    return out
 
def optimize(word_counters, max_iter=2000):
    alphabet = set("".join(words))
    S = Counter()
    best = daily_profit(S, word_counters)
    for _ in range(max_iter):
        improved = False
        for cand in neighbors(S, alphabet):
            v = daily_profit(cand, word_counters)
            if v > best:
                best = v; S = cand; improved = True
                break
        if not improved: break
    return S, best

Шаг 4. Интуитивные ожидания

В четверостишии много букв е, р, н — их вероятно нужно держать в большем количестве.
Самые длинные слова: «стремленье», «терпенье» (8 букв) — определяют пиковые потребности.
Если все 16 слов — короткие 4–5 букв, держать «хватает на самое длинное» дороже, чем платить неустойку за редкие длинные.

Шаг 5. Что отдавать

Возвращаем словарь S и daily_profit(S, ...).

Эталонный ответ

Скрипт + словарь оптимального склада. Главные шаги: парсинг → подсчёт Counter для каждого слова → функция daily_profit(S) с правильной обработкой трёх ситуаций («продано», «экспресс», «провал») → жадный/локальный поиск по соседним конфигурациям. Точная асимптотика — O(words * alphabet * iterations).

Подводные камни и обсуждение

«Регистр не учитывается» — обязательно .lower() после парсинга, иначе у первой буквы каждого слова будут отдельные буквы.
Пунктуация и Ё. re.findall(r"[А-Яа-яЁё]+", text) ловит и Ё.
Слово «Во» — два символа. С пустым складом получим −10, что тянет среднюю прибыль вниз. Часто оптимально иметь хотя бы по одному «в» и «о».
Считать прибыль вероятностно. Так как заказ равновероятен, ожидаемая прибыль — это средняя по 16 словам, не интеграл.
Стохастика. Если бы заказы были не равновероятны, распределение нужно учитывать в expected.
Локальный максимум. Жадный поиск может застрять. Сделайте 10–20 рестартов из случайных стартов.
Граница missing == 1. Часто ошибаются и считают экспресс при missing >= 1 всегда — но условие говорит «только если не хватает ровно одной».

Оптимизация склада букв «Фабрика слов» (DS / геоданные)