Дървото на технологиите в Python

Проблем

Дванайсет технологии до Звездната врата

В Epic Cosmos победата по наука е технологията Звездна врата. Тя не се проучва от нулата: иска Дредноути и Търговски пътища, Дредноутите искат плазмени оръдия и наноброня, а те искат термоядрен синтез и още. Играчът си задава три въпроса:

Какво мога да проучвам сега? Не всичко: технология е заключена, докато не са известни всичките ѝ предпоставки.
В какъв ред да стигна до целта? И колко наука ще струва пътят.
Може ли таблицата да е сгрешена? Ако две технологии се чакат взаимно, нищо не може да започне.

Ето екран tech от играта (от минаването, с което се проверява играта). + е известна, > се проучва сега, * може да се проучи, . е заключена; последният ред смята пътя до Звездната врата:

Ход 24/150  Земна империя (A)                           точки 93
M25+16 G173+30 C0+16 U47+3  наука +10
Проучава: Орбитални крепости 13/42
Технологии по ред (+ има, > сега, * може, . заключена)
+  1 drill    Дълбок добив            17  -
+  2 weapons1 Лазери                  21  -
+  3 hulls1   Леки брони              21  -
+  4 lab2     Квантови лаборатории    35  drill
*  5 fusion   Термоядрен синтез       49  lab2,weapons1
*  6 torpedo  Торпеда                 31  weapons1
*  7 cruiser  Крайцерски корпуси      31  hulls1
*  8 trade    Търговски пътища        35  drill
>  9 fortress Орбитални крепости      42  hulls1,drill
. 10 weapons2 Плазмени оръдия         71  fusion,torpedo
. 11 hulls2   Наноброня               71  fusion,cruiser
. 12 dread    Дредноути              107  weapons2,hulls2
. 13 stargate Звездна врата          249  dread,trade
До Звездната врата: 8 технологии, 644 наука, натрупана 13.
Колони: номер, име, цена, предпоставки.

Урокът строи тези три отговора с малки програми върху същата таблица, а накрая показва същото в играта. Че данните са таблица от текст, а не код, е показано в урока за съществата в Арканум; тук важното е какво е таблицата като структура.

Идеята

Таблица с предпоставки

Технологията е ред в таблица: номер, име, цена в точки наука и предпоставки, списък от други номера. Играта пази таблицата като текст и я чете при старт, затова нова технология е нов ред, не нов код. Ето същата таблица, както я зареждат програмите на урока (в играта има още колони: имената на другите езици, ефектът и стойността му):

# id|име|цена|предпоставки
drill|Дълбок добив|17|-
weapons1|Лазери|21|-
hulls1|Леки брони|21|-
lab2|Квантови лаборатории|35|drill
fusion|Термоядрен синтез|49|lab2,weapons1
torpedo|Торпеда|31|weapons1
cruiser|Крайцерски корпуси|31|hulls1
trade|Търговски пътища|35|drill
fortress|Орбитални крепости|42|hulls1,drill
weapons2|Плазмени оръдия|71|fusion,torpedo
hulls2|Наноброня|71|fusion,cruiser
dread|Дредноути|107|weapons2,hulls2
stargate|Звездна врата|249|dread,trade

Три от тринайсетте (drill, weapons1, hulls1) са без предпоставки (-), а stargate иска две. Редовете с # са бележка. Един ред става обект:

class Tech:
    def __init__(self, id, name, cost, prereqs):
        self.id = id
        self.name = name
        self.cost = cost
        self.prereqs = prereqs


def load(text):
    techs = {}
    for line in text.split("\n"):
        if line.strip() == "" or line.startswith("#"):
            continue
        c = line.split("|")
        prereqs = [] if c[3] == "-" else c[3].split(",")
        techs[c[0]] = Tech(c[0], c[1], int(c[2]), prereqs)
    return techs

load минава през редовете, пропуска празните и бележките, реже на | и пази технологиите по реда на таблицата. Редът е важен: затова колекцията е подредена (LinkedHashMap в Java, Dictionary в C#, dict в Python, Map в JavaScript), за да печатат програмите на четирите езика едно и също.

dict в Python пази реда на вмъкване по спецификация от версия 3.7.

Идеята

Граф без цикли

Нарисувай всяка технология като възел, а всяка предпоставка като стрелка от предпоставката към технологията: drill → lab2, lab2 → fusion. Таблицата става ориентиран граф: стрелките имат посока. В нашата са 13 възела и 16 стрелки.

Графът на технологиите има още едно свойство: няма цикъл. Ако тръгнеш по стрелките, никога не се връщаш там, откъдето си тръгнал. Такъв граф се казва ориентиран граф без цикли (на английски DAG, directed acyclic graph) и е точно формата на „първо това, после онова“: задачи със зависимости, модули на проект, дървото на уменията в RPG.

Цикълът е взаимно чакане. Нека оптиката иска лазери, лазерите искат радар, радарът иска оптика:

# id|име|цена|предпоставки
optics|Оптика|10|lasers
lasers|Лазери|10|radar
radar|Радар|10|optics

Никоя от трите не може да е първа: всяка чака друга. Играта не бива да стартира с такава таблица, затова проверява два пъти. Първо при зареждането: всяка предпоставка трябва да е технология, която съществува.

for tech in TECHS.values():
    for need in tech.prereqs:
        if need not in TECHS:
            raise RuntimeError('techs: unknown prerequisite ' + need)

После в main, преди да започне играта: ако топологичният ред (следващите карти) не излиза, дървото има цикъл.

if topo_order() is None:
    raise RuntimeError('the tech tree has a cycle')

Идеята

Какво може да се проучи сега

Играчът знае някои технологии. Технология е свободна, ако още не е известна и всичките ѝ предпоставки са известни. Кодът казва същото с един цикъл и ранно връщане:

def knows(known, tech_id):
    return tech_id in known


def can_research(known, tech):
    if knows(known, tech.id):
        return False
    for need in tech.prereqs:
        if not knows(known, need):
            return False
    return True


def available_techs(techs, known):
    result = []
    for tech in techs.values():
        if can_research(known, tech):
            result.append(tech)
    return result

canResearch връща false веднага щом види неизвестна предпоставка, а ако стигне до края на цикъла, true. Технология без предпоставки има празен цикъл, затова е свободна още в началото. availableTechs пита за всяка технология в таблицата. Програмата проучва drill, weapons1 и lab2 една по една и след всяка стъпка печата какво се отваря:

techs = load(TABLE)
known = []
for learn in ["", "drill", "weapons1", "lab2"]:
    if learn != "":
        known.append(learn)
    print("Знаеш: " + show(known))
    print("Можеш да проучиш: " + show(ids_of(available_techs(techs, known))))

Знаеш: -
Можеш да проучиш: drill, weapons1, hulls1
Знаеш: drill
Можеш да проучиш: weapons1, hulls1, lab2, trade
Знаеш: drill, weapons1
Можеш да проучиш: hulls1, lab2, torpedo, trade
Знаеш: drill, weapons1, lab2
Можеш да проучиш: hulls1, fusion, torpedo, trade

Забележи, че fusion се появява едва в края: иска и lab2, и weapons1. А drill изчезва от списъка веднага щом е известна, защото canResearch започва с проверката дали вече я знаеш.

def can_research(known, tech):
    if knows(known, tech.id):
        return False
    for need in tech.prereqs:
        if not knows(known, need):
            return 
    return True

Ето същите функции от играта. Знанията са списъкът empire.techs, а не отделен аргумент, и всичко е същото:

# Технологиите са ориентиран граф без цикли: ребро от предпоставката към технологията. Знанията на
# империята са списък с номера; „какво може да се проучи сега“ са неизвестните, на които всички
# предпоставки вече са известни.
def knows(empire, tech_id):
    return tech_id in empire.techs


def can_research(empire, tech):
    if knows(empire, tech.id):
        return False
    for need in tech.prereqs:
        if not knows(empire, need):
            return False
    return True


def available_techs(empire):
    result = []
    for tech in TECHS.values():
        if can_research(empire, tech):
            result.append(tech)
    return result

По-точно, за любопитните

Готовите функции там са на два нива: canResearch отговаря за една технология, availableTechs събира отговорите за всички. Така същият canResearch служи на startResearch (проучването може ли да започне) и на изкуствения интелект, който избира измежду свободните (урока за съперниците).

Идеята

Топологичен ред

Кой ред на проучване е допустим? Такъв, в който всяка технология е след предпоставките си. Наричат го топологичен ред и за всеки граф без цикли има поне един. Алгоритъмът е прост: докато има неподредени, вземи първата технология, на която всичките предпоставки вече са подредени, дай ѝ следващия номер и започни отначало.

def topo_order(techs):
    placed = []
    done = set()
    while len(placed) < len(techs):
        pick = None
        for tech in techs.values():
            if tech.id in done:
                continue
            ready = True
            for need in tech.prereqs:
                if need not in done:
                    ready = False
            if ready:
                pick = tech
                break
        if pick is None:
            return None  # цикъл: няма готова технология
        placed.append(pick.id)
        done.add(pick.id)
    return placed

Ако на някоя стъпка няма такава технология, а още има неподредени, значи те се чакат взаимно: функцията връща null. Така същият алгоритъм е и проверка за цикъл.

Програмата подрежда таблицата наобратно (stargate е първа), за да се види, че редът не идва от нея, и после опитва таблицата с цикъл:

techs = load(REVERSED)  # таблицата е наобратно, но редът не зависи от нея
order = topo_order(techs)
for i in range(len(order)):
    print(i + 1, order[i])

if topo_order(load(CYCLE)) is None:
    print("Цикъл: няма технология, на която всички предпоставки да са готови.")

1 hulls1
2 cruiser
3 weapons1
4 torpedo
5 drill
6 fortress
7 trade
8 lab2
9 fusion
10 hulls2
11 weapons2
12 dread
13 stargate
Цикъл: няма технология, на която всички предпоставки да са готови.

Първа излиза hulls1: всички отпред чакат нещо. После cruiser, защото hulls1 вече е подредена. Всяка стрелка в дървото сочи от по-малък номер към по-голям, а таблицата с цикъл връща null. При няколко готови печели първата в таблицата, затова редът е един и същ навсякъде. Такова е и правилото в играта:

# Топологичен ред (Kahn): технология излиза, когато всичките ѝ предпоставки вече са излезли. При
# няколко готови печели тази с по-малък номер в таблицата, затова редът е един и същ навсякъде.
def topo_order():
    placed = []
    done = set()
    total = len(TECHS)
    while len(placed) < total:
        pick = None
        for tech in TECHS.values():
            if tech.id in done:
                continue
            ready = True
            for need in tech.prereqs:
                if need not in done:
                    ready = False
            if ready:
                pick = tech
                break
        if pick is None:
            # Цикъл: няма технология с готови предпоставки.
            return None
        placed.append(pick.id)
        done.add(pick.id)
    return placed

Идеята

План до целта

Играчът избира цел, например stargate, и иска списък: какво още трябва да се проучи и в какъв ред. Две стъпки.

Какво е нужно. Тръгваме от целта и вървим назад по стрелките със стек: вадим технология, а ако не е известна, я записваме в need и слагаме предпоставките ѝ в стека. Известните се прескачат, така че вече проучената част не се плаща пак.
В какъв ред. need е множество, без ред. Редът идва от топологичния: минаваме през topoOrder и оставяме само нужните.

def plan_to(techs, known, target_id):
    need = set()
    stack = [target_id]
    while len(stack) > 0:
        tech_id = stack.pop()
        if tech_id in need or knows(known, tech_id):
            continue
        need.add(tech_id)
        for pre in techs[tech_id].prereqs:
            stack.append(pre)
    plan = []
    for tech_id in topo_order(techs):
        if tech_id in need:
            plan.append(tech_id)
    return plan


def plan_cost(techs, plan):
    total = 0
    for tech_id in plan:
        total += techs[tech_id].cost
    return total

Програмата планира пътя до Звездната врата при празно знание и после при известни drill, weapons1, hulls1 и lab2:

techs = load(TABLE)
for known in [[], ["drill", "weapons1", "hulls1", "lab2"]]:
    plan = plan_to(techs, known, "stargate")
    print("Знаеш: " + show(known))
    print("План: " + show(plan))
    print(str(len(plan)) + " технологии, " + str(plan_cost(techs, plan)) + " наука")

Знаеш: -
План: drill, weapons1, hulls1, lab2, fusion, torpedo, cruiser, trade, weapons2, hulls2, dread, stargate
12 технологии, 738 наука
Знаеш: drill, weapons1, hulls1, lab2
План: fusion, torpedo, cruiser, trade, weapons2, hulls2, dread, stargate
8 технологии, 644 наука

Планът без знания е 12 технологии, а не 13: fortress никой по пътя не иска. Сборът 738 е това, което екранът в началото на урока показва като „до Звездната врата“, а с четири известни остават 8 технологии за 644. Така е и в канона:

# Всичко, което още трябва да се проучи, за да стигнем до целта, в топологичен ред.
def plan_to(empire, target_id):
    need = set()
    stack = [target_id]
    while len(stack) > 0:
        tech_id = stack.pop()
        if tech_id in need or knows(empire, tech_id):
            continue
        need.add(tech_id)
        for pre in TECHS[tech_id].prereqs:
            stack.append(pre)
    plan = []
    for tech_id in topo_order():
        if tech_id in need:
            plan.append(tech_id)
    return plan


def plan_cost(plan):
    total = 0
    for tech_id in plan:
        total += TECHS[tech_id].cost
    return total

Виж го

Дървото в движение

Сцената минава през трите отговора: какво се отваря след всяка проучена технология, редът за таблицата наобратно и обхождането назад от Звездната врата. Следи цвета на рамките (зелено е свободна, синьо е известна, оранжево е нужна) и номерата на значките:

def plan_to(techs, known, target_id):
    need = set()
    stack = [target_id]
    while len(stack) > 0:
        tech_id = stack.pop()
        if tech_id in need or knows(known, tech_id):
            continue
        need.add(tech_id)
        for pre in techs[tech_id].prereqs:
            stack.append(pre)
    plan = []
    for tech_id in topo_order(techs):
        if tech_id in need:
            plan.append(tech_id)
    return plan

def knows(known, tech_id):
    return tech_id in known


def can_research(known, tech):
    if knows(known, tech.id):
        return False
    for need in tech.prereqs:
        if not knows(known, need):
            return False
    return True


def available_techs(techs, known):
    result = []
    for tech in techs.values():
        if can_research(known, tech):
            result.append(tech)
    return result

def topo_order(techs):
    placed = []
    done = set()
    while len(placed) < len(techs):
        pick = None
        for tech in techs.values():
            if tech.id in done:
                continue
            ready = True
            for need in tech.prereqs:
                if need not in done:
                    ready = False
            if ready:
                pick = tech
                break
        if pick is None:
            return None  # цикъл: няма готова технология
        placed.append(pick.id)
        done.add(pick.id)
    return placed

def plan_to(techs, known, target_id):
    need = set()
    stack = [target_id]
    while len(stack) > 0:
        tech_id = stack.pop()
        if tech_id in need or knows(known, tech_id):
            continue
        need.add(tech_id)
        for pre in techs[tech_id].prereqs:
            stack.append(pre)
    plan = []
    for tech_id in topo_order(techs):
        if tech_id in need:
            plan.append(tech_id)
    return plan

Стъпка по стъпка, с думи

Тринайсет технологии. Стрелката отива от предпоставката към технологията: lab2 иска drill, fusion иска lab2 и weapons1. Числото под името е цената.
Нищо не е проучено. drill, weapons1 и hulls1 нямат предпоставки: цикълът не намира неизвестна и canResearch връща true. Само те са свободни (зелени).
Проучваш drill (синя). Сега lab2 и trade искат само drill и са свободни. fortress иска още hulls1, затова чака. drill вече не е в списъка: вече е известна.
Проучваш weapons1: torpedo се отключва. fusion иска и lab2, и weapons1: weapons1 вече е известна, lab2 още не, затова цикълът връща false още на нея.
Проучваш lab2: сега fusion има и двете предпоставки и е свободна. Една липсваща предпоставка държи технологията заключена, всичките готови я отварят.
Друг въпрос: в какъв ред да проучим всичко? Таблицата е наобратно (stargate е първа), но редът не идва от нея. topoOrder минава по таблицата и взема първата технология, на която всичките предпоставки са подредени.
stargate, dread и другите отпред чакат предпоставки. Първата готова е hulls1 (без предпоставки): получава номер 1.
След всеки номер търсенето започва отначало: сега cruiser е готова, защото hulls1 вече е подредена. Подредените се прескачат.
Последна е stargate, номер 13: чакаше dread и trade. Всяка стрелка сочи от по-малък номер към по-голям: това е топологичният ред. Ако на някой ход няма готова технология, значи има цикъл и функцията връща null.
План до stargate. Тръгваме от целта и вървим назад по стрелките със стек: вадим технология, слагаме предпоставките ѝ. Всяка достигната влиза в need (оранжево).
fortress не е достигната: никоя технология по пътя до stargate не я иска. Тя не влиза в плана. Известните се прескачат, затова проучената част не се плаща пак.
Обхождането казва само какво е нужно. Редът идва от топологичния: planTo минава през topoOrder и оставя нужните. Така планът има 12 технологии в ред, в който всяка е след предпоставките си.
12 технологии, 738 наука: сборът от цените. fortress (42) не е нужна. Същото число показва играта на екрана tech, като „до Звездната врата“.

Графът е същият във всичките три части. Променя се само въпросът към него: какво е свободно (поглед напред от известните), в какъв ред (подреждане на всичко) и докъде (поглед назад от целта).

Пробвай

Предвиди изхода

Малка таблица: sensors няма предпоставки, engines и shields искат sensors, warp иска и двете, beacon иска warp. Известни са sensors и engines. Какво печата програмата?

SMALL = """
# id|име|цена|предпоставки
sensors|Сензори|10|-
engines|Двигатели|12|sensors
shields|Щитове|12|sensors
warp|Варп|20|engines,shields
beacon|Маяк|25|warp
"""

techs = load(SMALL)
known = ["sensors", "engines"]
print(show(ids_of(available_techs(techs, known))))

Отговор

shields, warp

engines, shields

shields

Пробвай

Намери грешката

Колега копира canResearch и в проверката на предпоставките сложи не това име. Ето какво печата програмата за известна само drill; ако е вярна, тук трябва да са и lab2, и trade:

def can_research(known, tech):
    if knows(known, tech.id):
        return False
    for need in tech.prereqs:
        if not knows(known, tech.id):
            return False
    return True


techs = load(TABLE)
known = ["drill"]
print("Знаеш: " + show(known))
print("Можеш да проучиш: " + show(ids_of(available_techs(techs, known))))

Знаеш: drill
Можеш да проучиш: weapons1, hulls1

Кой ред е виновен?

Избери реда с грешката.

По-точно

Какво не е в тази система

Дървото в играта има малко правила и зад тях стоят избори.

Всички предпоставки, не „някоя от“. canResearch връща false при първата неизвестна. Някои игри позволяват „или това, или онова“: тогава предпоставката е група, а технологията се отваря, когато една от групите е изпълнена. Това е друг граф (с две вида стрелки), а не друга функция.

Редът за равенство е част от правилото. Много технологии могат да са готови едновременно и всяка подредба е вярна. Канонът взема първата в таблицата, за да излиза един и същ ред на всички езици и при всяко пускане. Ако редът зависи от реда на вмъкване в хеш таблица, програмите на два езика могат да се различават.

Топологичният алгоритъм тук е най-простият, не най-бързият. topoOrder отначало обхожда таблицата при всеки номер: за n технологии това са около n² проверки. За тринайсет е нищо. За хиляди (зависимости на пакети) се ползва алгоритъмът на Kahn с брояч на чакащите предпоставки на всяка технология и опашка с готовите: O(V + E). Това е урокът за топологично сортиране, а обхождането на графа с стек е в урока за DFS.

Ефектът на технологията е отделна работа. Тук технологията е само възел с цена. Какво дава (повече добив, нападение, нов кораб) е в други колони на таблицата, а techMods събира ефектите на всички известни; кой кораб какво иска, е в урока за флотите.

Цикълът се хваща при старт, не по време на игра. Таблицата е част от кода на играта, а не вход на играча. Затова проверката е едно извикване на topoOrder в main. Ако таблицата идваше от потребител (мод), същата проверка би била съобщение за грешка към него, не пад на играта.

Упражнение

План по зададена таблица

Реши задачата в редактора си.

План по зададена таблица. Програмата чете от входа три неща: на първия ред целта, на втория известните технологии, разделени със запетая (или -, ако няма), а на всеки следващ ред по една технология във вида id цена предпоставки (предпоставките са разделени със запетая, - е без). Таблицата е в топологичен ред, но програмата не трябва да разчита на това. Печата плана (само нужните неподредени технологии в топологичен ред) и сбора на цените.

План: engines, shields, warp
Цена: 44

Внимавай: sensors е известна, затова не е в плана и не се плаща; warp е целта и влиза в плана последна.

Още задачи

Цикъл в таблицата. Подай таблица, в която a иска b, а b иска a. Какво прави planTo с topoOrder, която връща null? Накарай програмата да каже, че има цикъл, вместо да пада.
Непозната предпоставка. Добави ред с предпоставка, която я няма в таблицата. Хвани я при зареждането, както го прави loadData.
Кои технологии отключва тази? Напиши unlocks(techs, id), която връща технологиите, които иска id като предпоставка. Това е обхождане на стрелките напред.
Най-евтиният начален ход. От свободните технологии избери тази с най-малка цена. Какво се случва, ако две струват колкото?

Тест

Провери се

1. Защо таблицата с технологии не бива да има цикъл, например optics иска lasers, lasers иска radar, radar иска optics?Защото технология може да иска най-много една предпоставкаВсяка от трите чака друга от тях, затова никоя не може да е първа и нито една не стига до „свободна“. Играта проверява това още при старт и не тръгва с такава таблицаЗащото цикълът прави таблицата по-бавна за четене

2. fusion иска lab2 и weapons1. Известни са drill и weapons1. Може ли да се проучи fusion?Не: lab2 още не е известна, а се изискват всички предпоставкиДа: weapons1 е известна, а една предпоставка стигаДа: drill води до lab2

3. В програмата topo таблицата е наобратно (stargate е първа). Защо topoOrder пак дава правилен ред?Той не следва реда на таблицата, а взема първата технология, на която всичките предпоставки вече са подредени, и започва отначало. Таблицата решава само коя печели, когато са готови няколкоНе дава: правилен ред има само ако таблицата е вече подреденаТой първо сортира таблицата по цена

4. Защо fortress не влиза в плана до stargate?Защото има две предпоставкиНикоя технология по пътищата назад от stargate не я иска: тя е листо, до което обхождането не стигаЗащото е най-евтината технология

5. topoOrder върна null. Какво значи това за таблицата?Някоя технология иска предпоставка, която не съществуваИма цикъл: на някоя стъпка няма нито една неподредена технология, на която всички предпоставки са подредениТаблицата е празна

Дървото на технологиите

Бисквитки