Der Technologiebaum in Python

Problem

Zwölf Technologien bis zum Sternentor

In Epic Cosmos ist der Sieg durch Wissenschaft die Technologie Sternentor. Sie lässt sich nicht von null erforschen: Sie braucht Schlachtschiffe und Handelsrouten, die Schlachtschiffe brauchen Plasmakanonen und Nanopanzerung, und diese brauchen Kernfusion und mehr. Der Spieler stellt drei Fragen:

Was kann ich jetzt erforschen? Nicht alles: Eine Technologie ist gesperrt, bis alle ihre Voraussetzungen bekannt sind.
In welcher Reihenfolge erreiche ich das Ziel? Und wie viel Forschung kostet der Weg.
Kann die Tabelle falsch sein? Wenn zwei Technologien aufeinander warten, kann nichts anfangen.

Hier ist der Bildschirm tech aus dem Spiel (aus dem Durchlauf, an dem das Spiel geprüft wird). + ist bekannt, > wird gerade erforscht, * kann erforscht werden, . ist gesperrt; die letzte Zeile zählt den Weg bis zum Sternentor:

Runde 24/150  Terranisches Reich (A)                   Punkte 93
M25+16 G173+30 C0+16 U47+3  Forschung +10
Forscht: Orbitalfestungen 13/42
Technologien (+ bekannt, > jetzt, * möglich, . gesperrt)
+  1 drill    Tiefbohrung             17  -
+  2 weapons1 Laser                   21  -
+  3 hulls1   Leichte Panzerung       21  -
+  4 lab2     Quantenlabore           35  drill
*  5 fusion   Kernfusion              49  lab2,weapons1
*  6 torpedo  Torpedos                31  weapons1
*  7 cruiser  Kreuzerrümpfe           31  hulls1
*  8 trade    Handelsrouten           35  drill
>  9 fortress Orbitalfestungen        42  hulls1,drill
. 10 weapons2 Plasmakanonen           71  fusion,torpedo
. 11 hulls2   Nanopanzerung           71  fusion,cruiser
. 12 dread    Schlachtschiffe        107  weapons2,hulls2
. 13 stargate Sternentor             249  dread,trade
Bis zum Sternentor: 8 Technologien, 644 Forschung, gespart 13.
Spalten: Nummer, Name, Preis, Voraussetzungen.

Die Lektion baut diese drei Antworten mit kleinen Programmen über dieselbe Tabelle und zeigt am Ende dasselbe im Spiel. Dass die Daten eine Texttabelle sind und kein Code, zeigt die Lektion über die Wesen in Arkanum; hier zählt, was die Tabelle als Struktur ist.

Die Idee

Eine Tabelle mit Voraussetzungen

Eine Technologie ist eine Zeile einer Tabelle: eine Nummer, ein Name, ein Preis in Forschungspunkten und Voraussetzungen, eine Liste anderer Nummern. Das Spiel hält die Tabelle als Text und liest sie beim Start, also ist eine neue Technologie eine neue Zeile, kein neuer Code. Hier ist dieselbe Tabelle, wie die Programme der Lektion sie laden (das Spiel hat mehr Spalten: die Namen in den anderen Sprachen, den Effekt und seinen Wert):

# id|Name|Preis|Voraussetzungen
drill|Tiefbohrung|17|-
weapons1|Laser|21|-
hulls1|Leichte Panzerung|21|-
lab2|Quantenlabore|35|drill
fusion|Kernfusion|49|lab2,weapons1
torpedo|Torpedos|31|weapons1
cruiser|Kreuzerrümpfe|31|hulls1
trade|Handelsrouten|35|drill
fortress|Orbitalfestungen|42|hulls1,drill
weapons2|Plasmakanonen|71|fusion,torpedo
hulls2|Nanopanzerung|71|fusion,cruiser
dread|Schlachtschiffe|107|weapons2,hulls2
stargate|Sternentor|249|dread,trade

Drei der dreizehn (drill, weapons1, hulls1) haben keine Voraussetzungen (-), und stargate braucht zwei. Zeilen mit # sind Notizen. Eine Zeile wird zu einem Objekt:

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 geht die Zeilen durch, überspringt die leeren und die Notizen, schneidet bei | und hält die Technologien in der Reihenfolge der Tabelle. Die Reihenfolge zählt: Deshalb ist die Sammlung geordnet (LinkedHashMap in Java, Dictionary in C#, dict in Python, Map in JavaScript), damit die Programme in den vier Sprachen dasselbe ausgeben.

dict in Python behält die Einfügereihenfolge seit Version 3.7 laut Spezifikation.

Die Idee

Ein Graph ohne Zyklen

Zeichne jede Technologie als Knoten und jede Voraussetzung als Pfeil von der Voraussetzung zur Technologie: drill → lab2, lab2 → fusion. Die Tabelle wird zu einem gerichteten Graphen: Die Pfeile haben eine Richtung. Unserer hat 13 Knoten und 16 Pfeile.

Der Technologiegraph hat noch eine Eigenschaft: Er hat keinen Zyklus. Folgst du den Pfeilen, kommst du nie dorthin zurück, wo du gestartet bist. Ein solcher Graph heißt gerichteter azyklischer Graph (DAG, directed acyclic graph) und ist genau die Form von „erst das, dann jenes“: Aufgaben mit Abhängigkeiten, die Module eines Projekts, der Fähigkeitenbaum in einem RPG.

Ein Zyklus ist gegenseitiges Warten. Sagen wir, optics braucht lasers, lasers brauchen radar, radar braucht optics:

# id|Name|Preis|Voraussetzungen
optics|Optik|10|lasers
lasers|Laser|10|radar
radar|Radar|10|optics

Keine der drei kann die erste sein: Jede wartet auf eine andere. Das Spiel darf mit so einer Tabelle nicht starten, also prüft es zweimal. Erst beim Laden: Jede Voraussetzung muss eine Technologie sein, die es gibt.

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

Dann in main, bevor das Spiel beginnt: Kommt die topologische Reihenfolge (die nächsten Karten) nicht heraus, hat der Baum einen Zyklus.

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

Die Idee

Was jetzt erforschbar ist

Der Spieler kennt einige Technologien. Eine Technologie ist frei, wenn sie noch nicht bekannt ist und alle ihre Voraussetzungen bekannt sind. Der Code sagt dasselbe mit einer Schleife und einer frühen Rückgabe:

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 gibt false zurück, sobald es eine unbekannte Voraussetzung sieht, und wenn es das Ende der Schleife erreicht, true. Eine Technologie ohne Voraussetzungen hat eine leere Schleife, also ist sie von Anfang an frei. availableTechs fragt für jede Technologie der Tabelle. Das Programm erforscht drill, weapons1 und lab2 nacheinander und gibt nach jedem Schritt aus, was sich öffnet:

techs = load(TABLE)
known = []
for learn in ["", "drill", "weapons1", "lab2"]:
    if learn != "":
        known.append(learn)
    print("Bekannt: " + show(known))
    print("Erforschbar: " + show(ids_of(available_techs(techs, known))))

Bekannt: -
Erforschbar: drill, weapons1, hulls1
Bekannt: drill
Erforschbar: weapons1, hulls1, lab2, trade
Bekannt: drill, weapons1
Erforschbar: hulls1, lab2, torpedo, trade
Bekannt: drill, weapons1, lab2
Erforschbar: hulls1, fusion, torpedo, trade

Beachte, dass fusion erst am Ende erscheint: Sie braucht lab2 und weapons1. Und drill verschwindet aus der Liste, sobald sie bekannt ist, weil canResearch damit beginnt zu prüfen, ob du sie schon kennst.

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

Hier sind dieselben Funktionen aus dem Spiel. Das Wissen ist die Liste empire.techs, kein eigenes Argument, und alles andere ist gleich:

# Die Technologien sind ein gerichteter Graph ohne Zyklen: eine Kante von der Voraussetzung zur Technologie. Das Wissen des
# Reiches ist eine Liste von Nummern; „was jetzt erforscht werden kann“ sind die unbekannten, deren Voraussetzungen
# alle schon bekannt sind.
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

Genauer, für Neugierige

Die fertigen Funktionen dort arbeiten auf zwei Ebenen: canResearch antwortet für eine Technologie, availableTechs sammelt die Antworten für alle. So dient dasselbe canResearch dem startResearch (kann die Forschung beginnen) und der künstlichen Intelligenz, die unter den freien wählt (die Lektion über die Rivalen).

Die Idee

Topologische Reihenfolge

Welche Forschungsreihenfolge ist erlaubt? Eine, in der jede Technologie nach ihren Voraussetzungen kommt. Sie heißt topologische Reihenfolge, und jeder Graph ohne Zyklen hat mindestens eine. Der Algorithmus ist einfach: Solange es nicht eingeordnete gibt, nimm die erste Technologie, deren Voraussetzungen alle schon eingeordnet sind, gib ihr die nächste Nummer und fang von vorn an.

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  # Zyklus: keine bereite Technologie
        placed.append(pick.id)
        done.add(pick.id)
    return placed

Gibt es in einem Schritt keine solche Technologie, und es gibt noch nicht eingeordnete, dann warten sie aufeinander: Die Funktion gibt null zurück. So ist derselbe Algorithmus auch eine Prüfung auf Zyklen.

Das Programm legt die Tabelle verkehrt herum hin (stargate steht vorn), um zu zeigen, dass die Reihenfolge nicht von ihr kommt, und probiert dann die Tabelle mit dem Zyklus:

techs = load(REVERSED)  # die Tabelle steht verkehrt herum, aber die Reihenfolge hängt nicht von ihr ab
order = topo_order(techs)
for i in range(len(order)):
    print(i + 1, order[i])

if topo_order(load(CYCLE)) is None:
    print("Zyklus: Keine Technologie hat alle Voraussetzungen bereit.")

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
Zyklus: Keine Technologie hat alle Voraussetzungen bereit.

Zuerst kommt hulls1: Alle davor warten auf etwas. Dann cruiser, weil hulls1 schon eingeordnet ist. Jeder Pfeil im Baum zeigt von einer kleineren zu einer größeren Nummer, und die Tabelle mit dem Zyklus gibt null zurück. Sind mehrere bereit, gewinnt die erste in der Tabelle, also ist die Reihenfolge überall gleich. Das ist auch die Regel im Spiel:

# Topologische Ordnung (Kahn): eine Technologie kommt heraus, wenn alle ihre Voraussetzungen herausgekommen sind. Bei
# mehreren bereiten gewinnt die mit der kleineren Nummer in der Tabelle, darum ist die Reihenfolge überall gleich.
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:
            # Ein Zyklus: Keine Technologie hat ihre Voraussetzungen erfüllt.
            return None
        placed.append(pick.id)
        done.add(pick.id)
    return placed

Die Idee

Ein Plan bis zum Ziel

Der Spieler wählt ein Ziel, etwa stargate, und will eine Liste: was noch erforscht werden muss und in welcher Reihenfolge. Zwei Schritte.

Was gebraucht wird. Wir beginnen beim Ziel und gehen mit einem Stapel rückwärts an den Pfeilen entlang: eine Technologie herausnehmen, und wenn sie nicht bekannt ist, in need eintragen und ihre Voraussetzungen auf den Stapel legen. Bekannte werden übersprungen, also wird der schon erforschte Teil nicht noch einmal bezahlt.
In welcher Reihenfolge. need ist eine Menge, ohne Reihenfolge. Die Reihenfolge kommt von der topologischen: Wir gehen durch topoOrder und behalten nur die nötigen.

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

Das Programm plant den Weg zum Sternentor ohne Wissen und dann mit bekannten drill, weapons1, hulls1 und lab2:

techs = load(TABLE)
for known in [[], ["drill", "weapons1", "hulls1", "lab2"]]:
    plan = plan_to(techs, known, "stargate")
    print("Bekannt: " + show(known))
    print("Plan: " + show(plan))
    print(str(len(plan)) + " Technologien, " + str(plan_cost(techs, plan)) + " Forschung")

Bekannt: -
Plan: drill, weapons1, hulls1, lab2, fusion, torpedo, cruiser, trade, weapons2, hulls2, dread, stargate
12 Technologien, 738 Forschung
Bekannt: drill, weapons1, hulls1, lab2
Plan: fusion, torpedo, cruiser, trade, weapons2, hulls2, dread, stargate
8 Technologien, 644 Forschung

Der Plan ohne Wissen hat 12 Technologien, nicht 13: fortress braucht auf dem Weg niemand. Die Summe 738 ist das, was der Bildschirm am Anfang der Lektion als „Bis zum Sternentor“ zeigt, und mit vier bekannten bleiben 8 Technologien für 644. Im Kanon ist es genauso:

# Alles, was noch erforscht werden muss, um das Ziel zu erreichen, in topologischer Reihenfolge.
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

Sieh es dir an

Der Baum in Bewegung

Die Szene geht durch die drei Antworten: was sich nach jeder erforschten Technologie öffnet, die Reihenfolge für die verkehrte Tabelle und den Gang rückwärts vom Sternentor. Achte auf die Farbe der Rahmen (grün ist frei, blau ist bekannt, orange ist nötig) und auf die Nummern der Plaketten:

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  # Zyklus: keine bereite Technologie
        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

Schritt für Schritt, in Worten

Dreizehn Technologien. Ein Pfeil geht von der Voraussetzung zur Technologie: lab2 braucht drill, fusion braucht lab2 und weapons1. Die Zahl unter dem Namen ist der Preis.
Nichts ist erforscht. drill, weapons1 und hulls1 haben keine Voraussetzungen: Die Schleife findet keine unbekannte, und canResearch gibt true zurück. Nur sie sind frei (grün).
Du erforschst drill (blau). Jetzt brauchen lab2 und trade nur drill und sind frei. fortress braucht auch hulls1 und wartet. drill steht nicht mehr in der Liste: Sie ist schon bekannt.
Du erforschst weapons1: torpedo wird freigeschaltet. fusion braucht lab2 und weapons1: weapons1 ist bekannt, lab2 noch nicht, deshalb gibt die Schleife dort false zurück.
Du erforschst lab2: Jetzt hat fusion beide Voraussetzungen und ist frei. Eine fehlende Voraussetzung hält eine Technologie gesperrt, alle bereiten öffnen sie.
Eine andere Frage: In welcher Reihenfolge erforschen wir alles? Die Tabelle steht verkehrt herum (stargate steht vorn), aber die Reihenfolge kommt nicht von ihr. topoOrder geht die Tabelle durch und nimmt die erste Technologie, deren Voraussetzungen alle eingeordnet sind.
stargate, dread und die anderen davor warten auf Voraussetzungen. Die erste bereite ist hulls1 (ohne Voraussetzungen): Sie bekommt die Nummer 1.
Nach jeder Nummer beginnt die Suche von vorn: Jetzt ist cruiser bereit, weil hulls1 schon eingeordnet ist. Eingeordnete werden übersprungen.
Als Letzte kommt stargate mit Nummer 13: Sie wartete auf dread und trade. Jeder Pfeil zeigt von einer kleineren zu einer größeren Nummer: Das ist die topologische Reihenfolge. Ist in einem Schritt keine Technologie bereit, gibt es einen Zyklus, und die Funktion gibt null zurück.
Ein Plan bis stargate. Wir beginnen beim Ziel und gehen mit einem Stapel rückwärts an den Pfeilen entlang: Technologie herausnehmen, ihre Voraussetzungen hineinlegen. Alles Erreichte kommt in need (orange).
fortress wurde nie erreicht: Keine Technologie auf dem Weg zu stargate braucht sie. Sie kommt nicht in den Plan. Bekannte werden übersprungen, also wird Erforschtes nicht noch einmal bezahlt.
Der Gang sagt nur, was gebraucht wird. Die Reihenfolge kommt von der topologischen: planTo geht durch topoOrder und behält die nötigen. So hat der Plan 12 Technologien in einer Reihenfolge, in der jede nach ihren Voraussetzungen kommt.
12 Technologien, 738 Forschung: die Summe der Preise. fortress (42) wird nicht gebraucht. Dieselbe Zahl zeigt das Spiel auf dem Bildschirm tech als „Bis zum Sternentor“.

Der Graph ist in allen drei Teilen derselbe. Nur die Frage an ihn ändert sich: was ist frei (ein Blick nach vorn von den bekannten), in welcher Reihenfolge (alles ordnen) und wie weit (ein Blick zurück vom Ziel).

Probier es aus

Sage die Ausgabe voraus

Eine kleine Tabelle: sensors hat keine Voraussetzungen, engines und shields brauchen sensors, warp braucht beide, beacon braucht warp. Bekannt sind sensors und engines. Was gibt das Programm aus?

SMALL = """
# id|Name|Preis|Voraussetzungen
sensors|Sensoren|10|-
engines|Triebwerke|12|sensors
shields|Schilde|12|sensors
warp|Warp|20|engines,shields
beacon|Bake|25|warp
"""

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

Antwort

shields, warp

shields

engines, shields

Probier es aus

Finde den Fehler

Ein Kollege hat canResearch kopiert und in der Prüfung der Voraussetzungen den falschen Namen eingesetzt. Hier steht, was das Programm ausgibt, wenn nur drill bekannt ist; wäre es richtig, stünden hier auch lab2 und 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("Bekannt: " + show(known))
print("Erforschbar: " + show(ids_of(available_techs(techs, known))))

Bekannt: drill
Erforschbar: weapons1, hulls1

Welche Zeile ist schuld?

Wähle die Zeile mit dem Fehler.

Genauer

Was dieses System offenlässt

Der Baum im Spiel hat wenige Regeln, und hinter ihnen stehen Entscheidungen.

Alle Voraussetzungen, nicht „eine von“. canResearch gibt bei der ersten unbekannten false zurück. Manche Spiele erlauben „dies oder das“: Dann ist eine Voraussetzung eine Gruppe, und die Technologie öffnet sich, wenn eine der Gruppen erfüllt ist. Das ist ein anderer Graph (mit zwei Arten von Pfeilen), keine andere Funktion.

Die Reihenfolge bei Gleichstand gehört zur Regel. Viele Technologien können gleichzeitig bereit sein, und jede Anordnung ist richtig. Der Kanon nimmt die erste in der Tabelle, damit in allen Sprachen und bei jedem Lauf dieselbe Reihenfolge herauskommt. Hinge die Reihenfolge von der Einfügereihenfolge einer Hash-Tabelle ab, könnten Programme in zwei Sprachen voneinander abweichen.

Der topologische Algorithmus hier ist der einfachste, nicht der schnellste. topoOrder geht für jede Nummer die Tabelle von vorn durch: Bei n Technologien sind das etwa n² Prüfungen. Bei dreizehn ist das nichts. Bei Tausenden (Paketabhängigkeiten) nimmt man den Algorithmus von Kahn mit einem Zähler wartender Voraussetzungen für jede Technologie und einer Warteschlange der bereiten: O(V + E). Das ist die Lektion über topologisches Sortieren, und das Durchlaufen eines Graphen mit einem Stapel steht in der DFS-Lektion.

Der Effekt einer Technologie ist eine eigene Arbeit. Hier ist eine Technologie nur ein Knoten mit einem Preis. Was sie gibt (mehr Ertrag, Angriff, ein neues Schiff), steht in anderen Spalten der Tabelle, und techMods summiert die Effekte aller bekannten; welches Schiff was braucht, steht in der Lektion über die Flotten.

Der Zyklus wird beim Start gefangen, nicht während des Spiels. Die Tabelle ist Teil des Codes des Spiels, keine Eingabe des Spielers. Also ist die Prüfung ein Aufruf von topoOrder in main. Käme die Tabelle von einem Nutzer (ein Mod), wäre dieselbe Prüfung eine Fehlermeldung an ihn, kein Absturz des Spiels.

Übung

Ein Plan für eine gegebene Tabelle

Löse das in deinem Editor.

Ein Plan für eine gegebene Tabelle. Das Programm liest drei Dinge von der Eingabe: in der ersten Zeile das Ziel, in der zweiten die bekannten Technologien, durch Kommas getrennt (oder -, wenn es keine gibt), und in jeder folgenden Zeile eine Technologie in der Form id Preis Voraussetzungen (die Voraussetzungen durch Kommas getrennt, - für keine). Die Tabelle steht in topologischer Reihenfolge, aber das Programm darf sich nicht darauf verlassen. Es gibt den Plan aus (nur die nötigen nicht eingeordneten Technologien in topologischer Reihenfolge) und die Summe der Preise.

Plan: engines, shields, warp
Preis: 44

Achtung: sensors ist bekannt, also steht sie nicht im Plan und wird nicht bezahlt; warp ist das Ziel und kommt im Plan zuletzt.

Weitere Aufgaben

Ein Zyklus in der Tabelle. Gib eine Tabelle, in der a b braucht und b a. Was macht planTo mit einem topoOrder, das null zurückgibt? Bring das Programm dazu, zu sagen, dass es einen Zyklus gibt, statt abzustürzen.
Eine unbekannte Voraussetzung. Füge eine Zeile mit einer Voraussetzung hinzu, die nicht in der Tabelle steht. Fange sie beim Laden, wie es loadData tut.
Was schaltet diese frei? Schreibe unlocks(techs, id), das die Technologien zurückgibt, die id als Voraussetzung brauchen. Das ist ein Gang vorwärts entlang der Pfeile.
Der billigste erste Zug. Wähle unter den freien Technologien die mit dem niedrigsten Preis. Was passiert, wenn zwei gleich viel kosten?

Test

Teste dich

1. Warum darf die Technologietabelle keinen Zyklus haben, zum Beispiel optics braucht lasers, lasers braucht radar, radar braucht optics?Jede der drei wartet auf eine andere von ihnen, also kann keine die erste sein, und keine wird je „frei“. Das Spiel prüft das schon beim Start und läuft mit so einer Tabelle nichtWeil ein Zyklus die Tabelle langsamer lesbar machtWeil eine Technologie höchstens eine Voraussetzung haben kann

2. fusion braucht lab2 und weapons1. Bekannt sind drill und weapons1. Kann fusion erforscht werden?Ja: drill führt zu lab2Nein: lab2 ist noch nicht bekannt, und alle Voraussetzungen sind nötigJa: weapons1 ist bekannt, und eine Voraussetzung genügt

3. Im Programm topo steht die Tabelle verkehrt herum (stargate steht vorn). Warum gibt topoOrder trotzdem eine richtige Reihenfolge?Das tut sie nicht: Eine richtige Reihenfolge gibt es nur, wenn die Tabelle schon geordnet istSie sortiert die Tabelle zuerst nach PreisSie folgt nicht der Reihenfolge der Tabelle, sondern nimmt die erste Technologie, deren Voraussetzungen alle schon eingeordnet sind, und beginnt von vorn. Die Tabelle entscheidet nur, welche gewinnt, wenn mehrere bereit sind

4. Warum kommt fortress nicht in den Plan bis stargate?Weil sie die billigste Technologie istWeil sie zwei Voraussetzungen hatKeine Technologie auf den Wegen zurück von stargate braucht sie: Sie ist ein Blatt, das der Gang nie erreicht

5. topoOrder hat null zurückgegeben. Was heißt das für die Tabelle?Eine Technologie braucht eine Voraussetzung, die es nicht gibtDie Tabelle ist leerEs gibt einen Zyklus: In einem Schritt hat keine nicht eingeordnete Technologie alle Voraussetzungen eingeordnet

Der Technologiebaum

Cookies