Reihenfolge der Komponenten beim PC Zusammenbau

[CDW]

Da die Aufgabe Charminator anscheindend zu einfach war, kommt mal eine ohne solche Hilfestellungen .

Wir haben uns eine Maschine gebaut, die Rechner zusammenschrauben kann. Die Unterprogramme zum Einbau einzelner Komponenten wie: Mainboard einbauen, RAM, Grafikkarte, S-ATA-Kabel etc einstecken sind schon fertig.

Allerdings wollen wir Rechner nach Kundenwünschen zusammenbauen und die Maschine sollte dies vollautomatisch machen. Jedoch muss man zuerst das Mainboard einbauen, bevor die Grafikkarte eingesteckt wird und der CPU-Kühler sollte erst nach dem Einbau der CPU angebracht werden. Deshalb wollen wir uns ein Programm schreiben, welches die eingegebenen Komponenten in die richtige Reihenfolge bringt, damit unsere Machine nach dieser Liste den Rechner zusammenbauen kann.

Berücksichtige folgendes:
- Gehäuselüfter müssen vor Grafik-,Sound-,Netwerkkarten angebracht werden.
- CPU-Kühler kann erst nach der CPU Montage platziert werden, aber unbedingt vor S-ATA und Audiokabel.
- CPU muss vor CPU-Kühler, S-ATA und Audiokabel rein.
- Mainboard muss vor allen anderen Komponenten (außer dem Gehäuselufter) montiert werden.
- Festplatte und DVD-Laufwerk kommen vor S-ATA Kabel
- SLI Kabel kann erst nach Grafikkarteneinbau eingesteckt werden
- Audiokabel kann erst nach Soundkarte und DVD-Laufwerk Einbau hinein.

Das Programm soll nicht irgendeine logische Überpfürung anstellen (z.B SLI Kabel für nur einge Grafikkarte oder CPU-Kühler ohne CPU), sondern nur eine Reihenfolge zum Montieren ausgeben.

Und da wir das Programm später für viel viel Geld an eine große Firma verkaufen wollen,sollte es auf für andere Probleme anwendbar sein .
Idealerweise sollte man zuerst die Konfiguration:
Elemente: A,B,C,D
A vor: B,C
C vor D
B vor C
eingeben können
und dann zu einer Eingabe die richtige Reihenfolge herausbekommen:
Eingabe: C,D,A
Ausgabe: A,C,D

Diesen Schritt mit Benutzereingabe könnt ihr bei eurem Demo-Code fürs Habo natürlich auslassen und die Eingabe schon im Source festkodieren.

Eingabe für diese Aufgabe:
Kundenwunsch: 2x "InVidia GeForce 80808" Grafikkarte, Ausus Mainboard, "Indel Core5 80Ghz" CPU, Super-silent-CPU Kühler, "LeechersChoice200TB"-Festplatte,DVD-Laufwerk, Gehäuselüfter,SLI-Kabel,S-ATA Kabel, Audiokabel,Soundkarte, Netzwerkkarte, 4x "Infeoneon 128 GB" RAM Riegel

 

[Ivan Dolvich]

Hi Hackers, hier ist meine Lösung in Groovy. Im Prinzip haben wir einen Abhängigkeits-Graphen hier, der dann in topologischer Reihenfolge traversiert wird.

/** 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
}

Die Ausgabe:

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]

Grüße, Ivan

 

[Ook!]

Eine Python Lösung - Quick & Dirty:
Die "Regeln" der Konfiguration können über eine Textdatei gesteuert werden.

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()

Gruß
Felix