mgechev / javascript-algorithms Goto Github PK

Hi all,

Although I know the XSLT (1.0) processing model isn't per se a "classic computer science" algorithm, I was just curious if there'd be any interest for this repo to include a simple, quite minimalistic (yet useful, I believe) JavaScript equivalent? FWIW, it also nicely happens to be purely functional (i.e., side effects-free) -- that is, modulo only a couple String and Array prototype augmentations (helpers) that could be easily moved out into their own scope / namespace, if so wished.

For some working examples, see this SO link:

http://stackoverflow.com/a/35663358/1409653

Let me know, &

Cheers,

You can still use recursion, keep a cache (global or passed down), or do bottom up dynamic programming, e.g., like we did here: https://github.com/epibook/epibook.github.io/blob/master/solutions/cpp/Levenshtein_distance.cc

Hi,

I'm thinking of porting my CNF grammar data structure and CYK parser implementation in C# to JS.

Let me know if interested. You may want to check out the ATIS grammar example / test input, which is the less toy-ish one I've got (working)* so far -- ie, beyond Wikipedia's example, etc.

Cheers,
CJ

* (it parses OK 73% (72 out of 98) of the sample English sentences)

Hi! Javascripter with CSE,
I would like to also contribute but do not see contribute.md.
Please anybody can help me to init guide.

#74

Removed due to not handling collisions - #72

https://github.com/mgechev/javascript-algorithms/blob/master/src/graphs/searching/weightquickunion.js#L52

Currently the sizes of the specified nodes are being used. It should use the root node size. Will send a PR if I have a second

The array should be able to do the following operations:
Access the i-th element.
Insert element at potion i
Remove element from postion i.

All the operations should be strict O(logN);

In example go with dijkstra(0, 4, distMatrix) and get the result 26.

However the correct distance is 20 (path 0->2->5->4)

My fix for #46 explained here #47 was a 'woosh'. If root has children, with that change in place, they just become orphans and are lost in the void (rip).

if (node._parent !== null) {
  if (node._left) {
    this._replaceChild(node._parent, node, node._left);
  } else if (node._right) {
    this._replaceChild(node._parent, node, node._right);
  } else {
    this._replaceChild(node._parent, node, null);
  }
}else {
  this._root = null; // all children of that node lost in void
}

So I've removed the code from #47 and have a new fix that isn't stupid, tested, and works.

  exports.BinaryTree.prototype._replaceChild =
   function (parent, oldChild, newChild) {
    if (!parent) {
      this._root = newChild;
      if(this._root !== null){ //ADDED
        this._root._parent = null;
      } //ADDED
    } else {
      if (parent._left === oldChild) {
        parent._left = newChild;
      } else {
        parent._right = newChild;
      }
      if (newChild) {
        newChild._parent = parent;
      }
    }
  };

The new test - root removal with children:

  it('should remove root and replace with valid child (1)', function () {
    var bTree = new BinaryTree();
    bTree.insert(15);
    bTree.insert(30);
    bTree.insert(45);
    var node = bTree.find(15);
    bTree.remove(node);
    expect(bTree._root.value).toBe(30);
  });

will submit PR after #51 is handled (on same branch again 👯)

I'm going to be adding a bunch of tests to prevent these joys

All algorithms are covered by example, except mergesort (it looks like in mergesort it has been missed after refactoring #39 by @secrettriangle ). https://mgechev.github.io/javascript-algorithms/module-sorting_mergesort.html

Also small enhacements:

• type names of each parameter in all documentation begins from uppercase;
• description of each parameter contains "." in the end.

The following test (that doesn't exist in codebase) fails with the current BST remove()

  it('should insert and remove single node properly', function () {
    var bTree = new BinaryTree();
    bTree.insert(15);
    var node = bTree.find(15);
    bTree.remove(node);
    expect(bTree._root).toBe(null);
  });

Here's the issue explained in comments

// this is called in .remove()
this._replaceChild(node._parent, node, null); // node._parent is null since the node is the root, node is valid
..
..
..
   function (parent, oldChild, newChild) {
    if (!parent) { //parent param is null, enter if
      this._root = newChild; //assigns null to root
      this._root._parent = null; // null._parent throws error
    } else {
      if (parent._left === oldChild) {
        parent._left = newChild;
      } else {
        parent._right = newChild;
      }

      if (newChild) {
        newChild._parent = parent;
      }
    }

I've got a fix in place, a bunch of tests for BST, and will submit a PR once #45 clears (changes are on my local master).

The library source code is now not fully compatible with browser Javascript.

For example, these files

• src/sorting/bubblesort/bubblesort.js
• src/searching/binarysearch/binarysearch.js
• src/data-structures/heap.js
• src/searching/longest-increasing-subsequence/longest-increasing-subsequence.js

use node.js exports keyword, so they can not be used in browser code without changing.

May be use some approach to allow node.js-browser compatibility? (one of the possible approaches offerd by caolan here.

How can I run javascript-algorithms in the browser?

It would be nice if you guys were publishing a single (or several) js files that can run in the browser.

It looks like sorting/radixsort doesn't sort negative numbers.

What wrong with my code? I have an exception "The graph is not a DAG".

var topsort = require('../src/graphs/others/topological-sort').topologicalSort;
var graph = [[0, 1, 0, 0, 1],
             [0, 0, 0, 0, 0],
             [1, 1, 0, 1, 1],
             [0, 0, 0, 0, 0],
             [0, 0, 0, 0, 0]];
var vertices = topsort(graph);

But there is a graph I want to represent:

and it looks directed and acyclic.

Add disallowTrailingSpaces in .jscsrc.

Hey, I'm putting together a coding curriculum, and these algorithms are awesome. I was wondering if there exists a version of the code without the solutions already written?

Looks like it is possible to make graphs module better according to DRY approach.

For example Edge class used in Prism algorithm and in Bellman–Ford algorithm and it was copy/pasted.

Maybe there is reason to make Graph data structure with edges and vertices inside data-structures folder and algorithms inside graphs folder will just process this graph?

Windows 7 - 64 bit
Results in cmder & msysgit

Message:
    Command failed: C:\Windows\system32\cmd.exe /s /c "./node_modules/.bin/jsdoc -c ./doc-config.json"
'.' is not recognized as an internal or external command,
operable program or batch file.

Details:
    killed: false
    code: 1
    signal: null
    cmd: C:\Windows\system32\cmd.exe /s /c "./node_modules/.bin/jsdoc -c ./doc-config.json"
    stdout:
    stderr: '.' is not recognized as an internal or external command,
operable program or batch file.

#54

Add jscsrc and add it to gulp, in gulp build.

.jscrc should be copied from Yeoman's generator.

Inside 'searching' folder we have subfolders with just one js file. Maybe better to make folder structure not so deep like this:

searching/
-- binarysearch.js
-- recursive-binarysearch.js
-- knuth-morris-pratt.js
-- longest-increasing-subsequence.js
-- quickselect.js
-- maximum-subarray-divide-and-conquer.js
-- maximum-subarray.js

?

I'd suggest module name corresponding to the directory name since most of the algorithms are well categorized. May be there's a place for improvement for some (like searching can have sub-categories - strings and lists and sorting may have strings sub-category).

Lomuto's and Hoare's partitioning functions could be reused across different algorithms.

It'll be a good idea to put them in separate files.

First of all, thanks for creating the algorithms. Just tried the bubble sort.
Its working fine but one thing is that first element is ignored.
In line 18, changing
for (var j = i; j > 0; j -= 1)
to
for (var j = i; j >= 0; j -= 1);
fixed the issue.
Thanks once again.

Running the command git clone [email protected]:mgechev/javascript-algorithms.git javascript-algorithms-docs from readme.md results in the following output-

git clone [email protected]:mgechev/javascript-algorithms.git javascript-algorithms-docs
Cloning into 'javascript-algorithms-docs'...
Warning: Permanently added the RSA host key for IP address '192.30.252.130' to the list of known hosts.
Permission denied (publickey).
fatal: Could not read from remote repository.

Please make sure you have the correct access rights
and the repository exists.

I tried changing the git clone URL to https://github.com/mgechev/javascript-algorithms.git and it worked.
Should I send a pull request to change the clone URL?

Looks like we have a problem with @param and @return
All was OK in JSDoc 3.3.0-alpha13: http://andreygeonya.github.io/javascript-algorithms/docs/module-graphs_others_topological-sort.html
But gulp-jsdoc uses JSDoc 3.3.0-alpha5 and doesn't generate Parameters and Returns sections: https://mgechev.github.io/javascript-algorithms/topological-sort.html

https://camo.githubusercontent.com/50d06cb4de159eb546690745bfb0ff01e3cd22c4/68747470733a2f2f7472617669732d63692e6f72672f6d6765636865762f6a6176617363726970742d616c676f726974686d732e7376673f6272616e63683d6d6173746572

Really great work here! Just wondering whether this is likely to be published at some point soon?

Some algorithms, obviously, are inspired by or ported from Robert Sedgewick Java implementations (e.g: unionfind, LLRBT).

Would it not be more appropriate to add a comment mentioning this.

Hey,

can someone clarify this for me? I'm just trying to run the test file. I copied over the gulpfile.js into my project and did an npm install. I then did the gulp test and I'm getting the following result (which clearly didn't run the tests). Am I missing a step? Thanks in advance

➜ algorithms gulp test
[17:03:09] Using gulpfile ~/node_modules/algorithms/gulpfile.js
[17:03:09] Starting 'test'...
0 specs, 0 failures
Finished in 0 seconds
[17:03:09] Finished 'test' after 53 ms

Dependent on #66

Would you be interested by having an interactive documentation for javascript-algorithms?

You could use my klipse plugin

In case of generation of the same hash code for two different keys the collisions should be handled (using list?).

Knuth-morris-pratt algorithm freezes and doesn't return any result. My code:

var indexOf = require('../src/searching/knuth-morris-pratt').kmp;
console.log(indexOf('hello', 'll'));

It looks like the same methods, which is not correct.

https://github.com/mgechev/javascript-algorithms/blob/master/src/data-structures/binary-search-tree.js

http://rosettacode.org/wiki/Tree_traversal#JavaScript shows the proper pre and post order traversal.

I think it's better to remove the hash table from master until #66 is resolved.

Hi @secrettriangle

It looks like after your pull-request #39 documentation for the mergesort has been broken: https://mgechev.github.io/javascript-algorithms/ See: http://usejsdoc.org/howto-commonjs-modules.html#properties-of-the-exports-object

Can you fix it?

This test from searching/ binarysearch.spec.js has two issues:

it('should find the eleent in position arr.length', function () {
    expect(binarySearch([1, 2, 3, 4, 6, 8], 1)).toBe(0);
 });

• There can never be an element in position arr.length
• The value found parameter should be 8 instead of 1, assuming its testing for the last element.

noted here - #49

#74

Great library, but I think there's a bug in the IntervalTree implementation. Consider the following snippet:

it = new IntervalTree()
it.add([10383734, 10594186])
it.add([9495571, 9677853])

it.add([9303743, 9404967])
it.intersects([9303743, 9303744])

This should logically return true, right? The intersection test clearly overlaps the last added interval. Running this, however, yields false. If either of the first two add statements are removed, the intersection check at the end returns true as expected.

I would like to implement algorithm which finds longest common subsequence.

Now I can see in repository longest-subsequence.js file, which refers to longest increasing subsequence problem.

I suggest renaming longest-subsequence.js to "longest-increasing-subsequence.js" and add new longest-common-subsequence.js file.

What do You think about this idea? Of course I would make pull request with those changes.