Erweiterte Arrays und Schleifen in Javascript

Question

Ich versuche, eine komplexe Funktion zu schreiben, die Arrays beinhaltet. Das Problem betrifft ein (imaginäres) Paketinstallationsprogramm, wobei jedes Paket entweder 0 oder 1 Abhängigkeiten enthält. Die Aufgabe besteht darin, die Pakete und Abhängigkeiten in Reihenfolge zu ordnen, damit die Installation erfolgreich ist.

Die Funktion sollte ein Array von Zeichenfolgen akzeptieren, die Abhängigkeiten definieren. Jede Zeichenfolge enthält den Namen eines Pakets, gefolgt von einem Doppelpunkt und einem Leerzeichen, sowie alle Abhängigkeiten, die von diesem Paket benötigt werden. Das Programm sollte eine kommagetrennte Liste von Paketnamen in der Reihenfolge der Installation ausgeben, so dass die Abhängigkeit eines Pakets immer diesem Paket vorangeht.

Zum Beispiel kann eine Eingabe von

['KittenService: ','Leetmeme: Cyberportal','Cyberportal: Ice','CamelCaser: KittenService','Fraudstream: Leetmeme','Ice: '] 

sollte eine Ausgabe

'KittenService, Ice, Cyberportal, Leetmeme, CamelCaser, Fraudstream' 

Ich habe die grundlegenden Schritte der Funktion bekam nach unten wie die Reihenfolge des Pakets und die Abhängigkeit Umkehr und die Beseitigung der Doppelpunkt . Wenn es jedoch zu einem komplexeren System wie dem obigen kommt, habe ich Probleme. Kann mir jemand helfen?

Answer 1

Die Idee ist, eine directed acyclic graph (DAG) bilden dann führen Sie eine topological sorting auf der Grafik. Meine Lösung unten bildet nicht wirklich eine richtige DAG, aber sie führt eine topologische Sortierung unter Verwendung von durch. Es funktioniert für Ihren Fall. Dies funktioniert jedoch nicht in allen Fällen, aber Sie können die beiden obigen Ideen verwenden, um Ihre eigene perfekte Version zu erstellen.

var input = [ 
 
    'KittenService: ', 
 
    'Leetmeme: Cyberportal', 
 
    'Cyberportal: Ice', 
 
    'CamelCaser: KittenService', 
 
    'Fraudstream: Leetmeme', 
 
    'Ice: ' 
 
]; 
 
var dependencies = {}; 
 
var result = []; 
 

 
// Form the dependency graph 
 
for (var i = 0; i < input.length; i += 1) { 
 
    var inputSplit = input[i].split(':'); 
 
    var key = inputSplit[0].trim(); 
 
    var value = inputSplit[1].trim(); 
 
    dependencies[key] = value; 
 
} 
 

 
// Depth-first search 
 
for (var key in dependencies) { 
 
    if (dependencies.hasOwnProperty(key)) { 
 
    visit(key); 
 
    } 
 
} 
 

 
function visit(key) { 
 
    if (!dependencies.hasOwnProperty(key)) { 
 
    return; 
 
    } 
 

 
    if (dependencies[key] !== '') { 
 
    visit(dependencies[key]); 
 
    } 
 

 
    result.push(key); 
 
    delete dependencies[key]; 
 
} 
 

 
console.log(result);

Answer 2

Hier ist mein Weg, es zu lösen, war meine Idee, die Abhängigkeiten mit Iterationen zu finden. Werfen Sie einen Blick auf die Kommentare im Code

function dependencies(inputPackages){ 
 
    // the final list of packages 
 
    var packages = [] 
 

 
    // list of packages there having a dependency 
 
    var packagesWithDependency = []; 
 

 
    inputPackages.forEach(function(package){ 
 
     package = package.split(": "); // seperate package and dependency 
 
     if(package[1] === ""){ // package has no dependencies, append it directly to list of packages 
 
      packages.push(package[0]) 
 
     }else{ // package has a dependency, save it for later 
 
      packagesWithDependency.push({ 
 
       package: package[0], 
 
       dependencie: package[1] 
 
      }) 
 
     } 
 
    }) 
 

 
    // while there are unresolved packages 
 
    while(packagesWithDependency.length > 0){ 
 
     // we need this to check if there was found a package in this iteration 
 
     var packageWithDependencyCount = packagesWithDependency.length; 
 

 
     packagesWithDependency.forEach(function(packageWithDependency, index, object){ 
 
      // if the dependencies for a package is found in the packages list, then add the new package, and remove it from the packagesWithDependency list 
 
      if(packages.indexOf(packageWithDependency.dependencie) >= 0){ 
 
       packages.push(packageWithDependency.package); 
 
       object.splice(index, 1); 
 
      } 
 
     }) 
 
     
 
     // if no package was resolved in this iteration, then return false, the input requires a package there wasn't specified 
 
     if(packagesWithDependency.length == packageWithDependencyCount){ 
 
      return false; 
 
     } 
 
    } 
 

 

 
    // return packages // if you want the array instead 
 
    return packages.join(", ") 
 
} 
 

 
console.log(dependencies(['KittenService: ','Leetmeme: Cyberportal','Cyberportal: Ice','CamelCaser: KittenService','Fraudstream: Leetmeme','Ice: '])) 
 
console.log(dependencies(['KittenService: ','Leetmeme: Unknown package']))

Diese Lösung kann erweitert werden, um mehrere Abhängigkeiten zu behandeln.

Answer 3

Array.sort kann Wunder tun, und es macht den Code viel prägnanter:

function orderByDependency(input) { 
 
    return input.map(function(str, i) { 
 
    return { 
 
     dependency: str.split(': ')[1] ? str.split(': ')[1] : false, 
 
     name: str.split(': ')[0] 
 
    }; 
 
    }).sort(function(a, b) { 
 
    return b.dependency === false || a.dependency == b.name; 
 
    }); 
 
} 
 

 
document.body.innerHTML = orderByDependency([ 
 
    'KittenService: ', 
 
    'Leetmeme: Cyberportal', 
 
    'Cyberportal: Ice', 
 
    'CamelCaser: KittenService', 
 
    'Fraudstream: Leetmeme', 
 
    'Ice: ' 
 
]).map(function(pkg) { 
 
    return '<div> Loading ' + pkg.name + '...<hr></div>'; 
 
}).join('');