高度な配列とJavascriptのループ

Question

配列を含む複雑な関数を記述しようとしています。この問題には、（虚偽の）パッケージインストーラが含まれ、各パッケージに0または1の依存関係が含まれています。タスクは、パッケージと依存関係を順番に並べて、インストールが成功するようにすることです。

この関数は、依存関係を定義する文字列の配列を受け入れる必要があります。各文字列には、パッケージの名前、コロンとスペース、パッケージに必要な依存関係が含まれています。プログラムは、パッケージの依存関係が常にそのパッケージに先行するように、インストール順にコンマで区切られたパッケージ名のリストを出力する必要があります。例えば

、

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

の入力すべき出力

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

私はパッケージと依存関係の順序を逆にし、コロンを排除するように機能の基本的な手順を下に持っています。しかし、上記のようなより複雑なシステムになると、私は問題を抱えています。誰でも助けてくれますか？

Answer 1

directed acyclic graph (DAG)を作成し、次にグラフにtopological sortingを実行することです。以下の私のソリューションは実際には適切なDAGを形成しませんが、depth-first searchを使用してトポロジカルソートを行います。それはあなたのケースで動作します。しかし、これはすべてのケースでうまくいくわけではありませんが、上の2つのアイデアを使って完全な独自のバージョンを作成することができます。ここで

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

私の考えは、反復を使用して依存関係を見つけることだった、それを解決するための私の方法です。このソリューションは、複数の依存関係を処理するために拡張することができるコード

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']))

にコメントを見てみましょう。

Answer 3

Array.sortはあまりにも驚異を行うことができ、そしてそれはあなたのコードははるかに簡潔になります：

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