Advanced arrays and loops in Javascript

Question

I am trying to write a complex function that involves arrays. The problem involves an (imaginary) package installer, with each package containing either 0 or 1 dependencies. The task is to order the packages and dependencies in order so that the install is successful.

The function should accept an array of strings defining dependencies. Each string contains the name of a package followed by a colon and space, then any dependencies required by that package. The program should output a comma separated list of package names in the order of install, such that a package’s dependency will always precede that package.

For example, an input of

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

should output

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

I've got the basic steps of the function down like reversing the order of the package and dependency and eliminating the colon. However, when it comes to a more complex system like the one above, I am having trouble. Can anyone help me?

Answer 1

Array.sort can do wonders too, and it makes your code much more concise:

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

Answer 2

Here is my way to solve it, my idea was to find the dependencies using iterations. Take a look at the comments in the 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']))

This solution can be extended to handle multiple dependencies.

Answer 3

The idea is to form a directed acyclic graph (DAG) then perform a topological sorting on the graph. My solution below doesn't really form a proper DAG but it does a topological sorting using depth-first search. It works for your case. However, this won't work for all cases but you can use the two ideas above to create your own perfect version.

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