Рецепты: сырьё с запоминанием и круги от модов

Если ты считаешь ресурсы по графу рецептов с запоминанием и проверяешь его на циклы до расчёта, листай до «Теперь сам».

Как думаешь, сколько раз считается колесо

Караван делают из трёх фургонов и двух телег. Фургон - из телеги, двух ящиков и двух колёс. Телега - из ящика и четырёх колёс. Сколько раз программа, которая честно раскрывает каждый рецепт вглубь, посчитает рецепт колеса для одного каравана?

Ответь себе до чтения. Колесо встречается в каждой телеге и в каждом фургоне, а телеги - и сами по себе, и внутри фургонов. Наивное раскрытие пойдёт в рецепт колеса по каждому пути от каравана до колеса: через фургон, через телегу внутри фургона, через телегу саму по себе - для одного каравана это три захода в рецепт колеса, хотя колёс нужно 26. Но сырьё на одно колесо от пути не зависит - это всегда две доски и четыре гвоздя. Посчитать его можно один раз.

На что это похоже

Смета на ремонт дома с одинаковыми комнатами. Прораб не пересчитывает расход плитки на каждую из шести одинаковых ванных: он считает одну ванную и умножает. Если ванные встречаются и в смете этажа, и в смете подъезда, расход на одну ванную всё равно считается один раз и подставляется везде.

Механизм: граф рецептов, запоминание и цвета

Вещи - вершины, рецепт ящик ← 4 доски - ребро от ящика к доске с весом 4. Граф ориентированный, и общие компоненты делают его не деревом: в колесо ведут рёбра из телеги и фургона, а к каравану оно приходит через них обоих. Сырьё на одну штуку вещи - сумма по компонентам: количество компонента, умноженное на сырьё на одну штуку компонента. Это рекуррентность, и у неё повторяющиеся подзадачи: сырьё на колесо нужно многим. Запоминание (раздел 15) хранит ответ для каждой вещи, и каждая вещь считается один раз - работа пропорциональна числу рецептов, умноженному на число видов сырья в словарях, а не числу путей.

Наивное раскрытие платит числом путей от цели до сырья. В худшем случае оно растёт как степень: если каждый уровень использует предыдущий двумя способами, путей на глубине d - 2ᵈ. Запоминание здесь не украшение, а смена класса алгоритма.

Рекуррентность работает, только пока в графе нет циклов: «бревно рубят киркой, кирку делают из досок, доски из брёвен» - и ответ про бревно зависит от самого себя. Круг ищет обход в глубину из раздела 10 с тремя цветами: белый - не заходили, серый - вершина на текущем пути обхода, чёрный - обойдена целиком. Ребро в серую вершину возвращает на свой же путь - это и есть круг.

Правило

Сырьё по рецептам считают с запоминанием: ответ на одну штуку каждой вещи - один раз, работа - по числу рецептов, умноженному на число видов сырья, а не по числу путей. До расчёта граф рецептов проверяют на круги обходом с тремя цветами: рецепт, который зависит от себя, не раскрывается.

Разбор: сырьё на караван, гильдию и столицу

Восемь уровней рецептов - от доски до столицы, - сырьё - брёвна и руда. Сравниваем наивное раскрытие и запоминание.

# рецепт: вещь -> список [компонент, сколько штук]; у сырья рецепта нет
recepty = {
    "доска": [["бревно", 1]],
    "гвоздь": [["руда", 1]],
    "ящик": [["доска", 4], ["гвоздь", 8]],
    "колесо": [["доска", 2], ["гвоздь", 4]],
    "телега": [["ящик", 1], ["колесо", 4]],
    "фургон": [["телега", 1], ["ящик", 2], ["колесо", 2]],
    "караван": [["фургон", 3], ["телега", 2]],
    "обоз": [["караван", 2], ["фургон", 3], ["телега", 1]],
    "гильдия": [["обоз", 3], ["караван", 2], ["фургон", 4]],
    "столица": [["гильдия", 2], ["обоз", 3], ["караван", 2]],
}
vyzovov = [0]

def syrjo_naivno(vesh, n, itog):
    # раскрываем рецепт вглубь: каждый компонент - заново, сколько бы раз
    # он ни встречался в разных ветках
    vyzovov[0] = vyzovov[0] + 1
    if vesh not in recepty:
        itog[vesh] = itog.get(vesh, 0) + n
        return
    for k in recepty[vesh]:
        syrjo_naivno(k[0], n * k[1], itog)

def syrjo_na_odnu(vesh, pamyat):
    # сырьё на ОДНУ штуку вещи, с запоминанием: каждый рецепт - один раз
    vyzovov[0] = vyzovov[0] + 1
    if vesh in pamyat:
        return pamyat[vesh]
    itog = {}
    if vesh not in recepty:
        itog[vesh] = 1
    else:
        for k in recepty[vesh]:
            pod = syrjo_na_odnu(k[0], pamyat)
            for s in pod:
                itog[s] = itog.get(s, 0) + pod[s] * k[1]
    pamyat[vesh] = itog
    return itog

def pokazat(itog):
    out = []
    for s in sorted(itog.keys()):
        out.append(s + " " + str(itog[s]))
    return ", ".join(out)

for cel in ["караван", "гильдия", "столица"]:
    itog = {}
    vyzovov[0] = 0
    syrjo_naivno(cel, 1, itog)
    v1 = vyzovov[0]
    vyzovov[0] = 0
    print(cel + ":", pokazat(itog))
    syrjo_na_odnu(cel, {})
    print("    вызовов: наивно", v1, "| с запоминанием", vyzovov[0])

караван: бревно 96, руда 192
    вызовов: наивно 34 | с запоминанием 14
гильдия: бревно 1116, руда 2232
    вызовов: наивно 125 | с запоминанием 20
столица: бревно 3252, руда 6504
    вызовов: наивно 228 | с запоминанием 23

Ответы одинаковые, а работа расходится и дальше будет расходиться сильнее. Наивное раскрытие на столице сделало 228 вызовов - по одному на каждый путь от столицы до каждой встреченной вещи, промежуточной или сырья, - запоминание 23: по одному на каждую из 12 вещей и сырья, плюс повторные заходы, которые сразу берут готовый ответ. Каждый новый уровень добавляет запоминанию пару вызовов, а наивному - столько, сколько путей проходит через новый уровень. Граница правила: запоминание хранит словарь сырья для каждой вещи, и если видов сырья сотни, а вещей тысячи, это уже заметная память - тогда считают в обратном порядке, от цели к сырью, накапливая только нужные количества.

Разбор: круг от мода

Мод добавил рецепт «бревно рубят киркой». Кирка делается из железа и досок, железо - из угля, уголь - из досок, доски - из брёвен. Раскрыть бревно теперь нельзя.

# Мод добавил рецепты. Прежде чем считать сырьё, проверяем, что рецепты
# не замыкаются в круг: иначе раскрытие рецепта не закончится никогда.
recepty = {
    "доска": [["бревно", 1]],
    "ящик": [["доска", 4], ["гвоздь", 8]],
    "гвоздь": [["железо", 1]],
    "железо": [["руда", 2], ["уголь", 1]],
    "уголь": [["доска", 3]],
    "кирка": [["железо", 3], ["доска", 2]],
    "бревно": [["кирка", 1]],               # мод: бревно рубят киркой
}
BELYJ = 0                 # ещё не заходили
SERYJ = 1                 # на текущем пути обхода
CHERNYJ = 2               # обойдён целиком, круга через него нет

def najti_krug(vesh, cvet, put):
    # обход в глубину по рецептам; встретить СЕРУЮ вершину - значит
    # вернуться на свой же путь: это круг (раздел 10)
    cvet[vesh] = SERYJ
    put.append(vesh)
    for k in recepty.get(vesh, []):
        c = cvet.get(k[0], BELYJ)
        if c == SERYJ:
            i = len(put) - 1
            while put[i] != k[0]:
                i = i - 1
            return put[i:] + [k[0]]
        if c == BELYJ:
            krug = najti_krug(k[0], cvet, put)
            if len(krug) > 0:
                return krug
    put.pop()
    cvet[vesh] = CHERNYJ
    return []

cvet = {}
for vesh in sorted(recepty.keys()):
    if cvet.get(vesh, BELYJ) == BELYJ:
        krug = najti_krug(vesh, cvet, [])
        if len(krug) > 0:
            print("круг в рецептах:", " -> ".join(krug))
            break
recepty.pop("бревно")                  # мод откатили
cvet = {}
nashli = False
for vesh in sorted(recepty.keys()):
    if cvet.get(vesh, BELYJ) == BELYJ:
        if len(najti_krug(vesh, cvet, [])) > 0:
            nashli = True
print("после отката мода круг есть:", nashli)

круг в рецептах: бревно -> кирка -> железо -> уголь -> доска -> бревно
после отката мода круг есть: False

Обход нашёл круг из пяти рецептов и показал его целиком - это сертификат, который можно отдать автору мода: не «рецепты неверны», а «вот цепочка, которая замыкается». После отката мода кругов нет, и расчёт сырья снова корректен. Граница правила: в настоящих играх круги бывают нарочно - семена растят из урожая, урожай из семян. Такой круг не ошибка, а производственный цикл, и его считают не раскрытием, а уравнением: сколько урожая оставить на семена, чтобы цикл давал прибыль, - это уже линейное программирование из раздела 12.

Что ломается без этого

Расчёт крафта тормозит на сложных вещах. На простых предметах всё мгновенно, на «столице» - заметно дольше: наивное раскрытие платит числом путей, а их с каждым уровнем больше.

Сервер висит после мода. Мод замкнул рецепты, раскрытие ушло в бесконечную рекурсию, и ход не закончился - или упал по переполнению стека.

Цикл, который отклонили по ошибке. Проверка на круги отвергла законный цикл «семена - урожай», и фермерство в игре сломалось.

Зачем это в работе

Спецификация изделия в производстве (сколько болтов на самолёт), разрешение зависимостей пакетов, сборка проекта из модулей, расчёт себестоимости по рецептуре - всё это граф без циклов с общими узлами. Запоминание по узлам и проверка на круги до расчёта - стандартная пара, и сборщики пакетов печатают найденный круг зависимостей ровно так, как программа выше.

Теперь сам

1. Вещь A₀ делается из A₁ и B₁, обе они - из A₂ и B₂, и так до A₂₀ и B₂₀ - это сырьё. Сколько вызовов сделает наивное раскрытие? Сколько с запоминанием?
2. Почему ребро в ЧЁРНУЮ вершину - не круг?
3. Мод добавил рецепт «доска из ящика». Найдёт ли проверка круг, и какой?