Hacker News Reader

Comment by OskarS | Hacker News Reader

If you wanna do this bad boy for real, you depend on this one and the next 999 packages.

Actually, this can become a fun optimization problem. Which 1000 packages do you depend on to cover as much of NPM as possible?

View on HN

I thought that's what this was.

Many of these packages have no dependencies.

A new package that depends on this and anything not already downstream would have more dependencies.

Might get you close:

    Until you have 1000
        Find the package not included that adds the most deps
        If it adds less than everything you have
            Add it
        Else
            Kick out anything that adds less than that

And then make that a package and repeat as desired.

Yeah, that's the greedy algorithm and it will probably take you pretty far, but there's no guarantee that it's optimal. What if the package has lots of dependencies, but they are already covered by other packages. Do you kick other packages out? Which ones? Or is it better to keep them in and add some other packages?

This problem is almost certainly NP-complete (it's basically the the "set cover" problem from Karp's 21 NP-complete problems), so for something the size of NPM it's almost certainly infeasible. Your greedy version would probably get you a pretty nice result, though.

I don't think it's optimal, but I tried to account for some of what you're saying. I'd take in whatever adds the most new dependencies if the amount it would add is lower or equal to the least contributing package I have. Otherwise, kick stuff out and recalculate.

If you wanna feel bad boy for real create a B+ tree of order 1000 which contains all npm packages in leaf nodes and create meta package for internal nodes. The root metapackage posted to HN.

Reply on news.ycombinator.com