[HaBo]

/** Die Klasse räpresentiert die Beschreibung eines Computerteils */
class PartInfo
{
    String type             // Name des Teils
    
    List succs = []         // Nachvolger im Abhängigkeits-Graphen
    List prevs = []         // Vorgänger im Abhängigkeits-Graphen

    Integer deps = 0        // Anzahl Vorgänger von denen wir noch abhängen
    
    /** Fügt Nachfolger zu diesem Teil ein */
    void addSuccs(List succs) {
        this.succs.addAll(succs)
        succs.each { it.prevs.add(this); it.deps++ }
    }
    
    /** Sammelt rekursiv alle Vorgänger dieses Teils in einem Set */
    void collectPrevs(Set set) {
        set.addAll(prevs)
        prevs.each { it.collectPrevs(set) }
    }
    
    /** Befreit die Nachvolger von der Abhängigkeit */
    void releaseSuccs() {
        succs.each { it.deps-- }
    }
    
    String toString() { return type }
}

/** Hier wird die Konfiguration festgelegt */
Map readConfiguration() 
{
    PartInfo a = new PartInfo(type:"Gehäuselüfter")
    PartInfo b = new PartInfo(type:"Grafikkarte")
    PartInfo c = new PartInfo(type:"Soundkarte")
    PartInfo d = new PartInfo(type:"Netzwerkkarte")
    PartInfo e = new PartInfo(type:"CPU-Kühler")
    PartInfo f = new PartInfo(type:"CPU")
    PartInfo g = new PartInfo(type:"S-ATA-Kabel")
    PartInfo h = new PartInfo(type:"Audiokabel")
    PartInfo i = new PartInfo(type:"Mainboard")
    PartInfo j = new PartInfo(type:"Festplatte")
    PartInfo k = new PartInfo(type:"DVD-Laufwerk")
    PartInfo l = new PartInfo(type:"SLI-Kabel")
    PartInfo m = new PartInfo(type:"RAM")  
    
    a.addSuccs([b, c, d])
    e.addSuccs([g, h])
    f.addSuccs([e, g, h])
    i.addSuccs([b, c, d, e, f, g, h, j, k, l, m])
    j.addSuccs([g])
    k.addSuccs([g, h])
    b.addSuccs([l])
    c.addSuccs([h])
    m.addSuccs([f])
    
    return [(a.type):a, (b.type):b, (c.type):c, (d.type):d, (e.type):e,
            (f.type):f, (g.type):g, (h.type):h, (i.type):i, (j.type):j,
            (k.type):k, (l.type):l, (m.type):m]
}

/** Hier wird die Eingabe eingelesen */
List readInput() 
{
    return ["Grafikkarte", "Mainboard", "CPU", "CPU-Kühler", "Festplatte", 
            "DVD-Laufwerk", "Gehäuselüfter", "SLI-Kabel", "S-ATA-Kabel",
            "Audiokabel", "Soundkarte", "Netzwerkkarte", "RAM"]
}

// *** Das Programm startet hier ***

// Konfiguration und Input auslesen
Map config = readConfiguration()
List input = readInput()

// Input-Liste von String-Objekte nach PartInfo-Objekte konvertieren
input = input.collect { config.get(it) }

// Input-Liste vervollständigen (nicht-eingegebene Teile dazunehmen)
Set set = new HashSet(input)
input.each { it.collectPrevs(set) }
input = set.toList()

// Der Algorithmus: Abhängigkeits-Graph topologisch sortieren
// Solange der Graph Knoten hat:
// 1) die freien Knoten ermitteln
// 2) die freien Knoten ausgeben
// 3) die freien Knoten aus Graph entfernen
while (!input.isEmpty()) {
    List free = input.findAll { it.deps == 0 }
    println "Einbauen: ${free}"
    free.each { it.releaseSuccs() }
    input -= free
}

Einbauen: [Mainboard, Gehäuselüfter]
Einbauen: [RAM, Grafikkarte, Netzwerkkarte, Festplatte, DVD-Laufwerk, Soundkarte]
Einbauen: [SLI-Kabel, CPU]
Einbauen: [CPU-Kühler]
Einbauen: [S-ATA-Kabel, Audiokabel]

class Componente(object):
   def __init__(self, comp, name):
      self.comp = comp
      self.name = name
      self.before = []
      self.after = []
	
   def addbefore(self, part):
      self.before.append(part)
      self.before[-1].after.append(self)

def doIt():
   parts = []
   for line in open("PC.txt", "r"):
      line = line[:-1]
      if line != "":
         if "vor" not in line:
            parts.append(Componente(line.split("#")[0], line.split("#")[1]))
         else:
            for part1 in parts:
               for part2 in parts:
                  if part1.comp == line.split(" vor ")[1] and part2.comp == line.split(" vor ")[0]:
                     part1.addbefore(part2)
   return evaluate(parts)

def evaluate(parts, output="Reihenfolge:\n"):
   while len(parts) > 0:
      comps = filter(lambda p: len(p.before) == 0, parts)
      output += ", ".join([ c.name for c in comps ]) +"\n"
      for comp in comps:
         for p in comp.after:
            p.before.remove(comp)
      parts = filter(lambda part: part not in comps, parts)
   return output

if __name__ == "__main__":	
   print doIt()